DSA - 树和二叉树

发表于 2026-04-13 更新于 2026-04-15 分类于数据结构阅读次数：本文字数： 2.6k 阅读时长 ≈ 9 分钟

准备数据结构期中的复习笔记，第五章树和二叉树

树和二叉树

树

指定某一节点为根后，即是有根树。零度节点称叶子，其余为内部节点。

兄弟之间依据 ${r_1,r_2,…,r_d}$ 排序就是有序树

深度，层次：

从任意祖先 r 出发，沿边逐代下溯可以抵达各级后代 v。路径的边数为路径长度。若 r 为全树的根，路径长度为 v 的深度。依照深度可以划分为 h + 1 类节点。所有节点的最大深度称为树的高度。空树高度 =-1。

节点高度 = 后代最大深度 - 自己深度 = 子树高度。

ADT 和实现

父节点 + 孩子节点实现，对每个节点都存储所有孩子的链表，以及父亲的下标。

二叉树性质

节点度数不超过 2。

对 lc、rc 来说 p 是左父亲和右父亲，对 p 来说 lc、rc 是左儿子和右儿子。

不含单分支节点的二叉树称为真二叉树。可以引入虚构外部节点实现真二叉树

描述多叉树：长子弟弟表示法。长子放左孩子，最大的弟弟放右孩子，递归处理

二叉树实现

0009    BinNode( T e, BNP<T> _p = nullptr, BNP<T> lc = nullptr,
0010             BNP<T> rc = nullptr, int h = 0, bool c = RBT_RED )
0011       : data(e), parent(_p), lc(lc), rc(rc), height(h), color(c)
0012       { if (lc) lc->parent = this; if (rc) rc->parent = this; }

更新高度

0003 template <typename T> int BinNode<T>::updateHeight() //更新当前节点高度
0004    { return height = 1 + max( Height( lc ), Height( rc ) ); }
0005 template <typename T> void BinNode<T>::updateHeightAbove() //更新当前节点及其祖先的高度
0006    { for ( BNP<T> x = this; x; x = x->parent ) x->updateHeight(); } //可优化

优化：如果当前高度和更新之后的一样就退出循环，最好情况优化到 O (1)

接入和取出：

0001 template <typename T> //将S当作节点x的右子树接入，再将S置空
0002 BNP<T> BinTree<T>::attach( BNP<T> x, BinTree<T> S ) { //x->rc == nullptr
0003    if ( ! ( x->rc = S._root ) ) return nullptr; //空树无需费事
0004    x->rc->parent = x; //接入
0005    _size += S._size; x->updateHeightAbove(); //更新全树规模与x所有祖先的高度
0006    S._root = nullptr; S._size = 0; return x; //释放原树，返回接入位置
0007 }

0001 template <typename T> BinTree<T> BinTree<T>::secede( BNP<T> x ) { //子树分离
0002    FromParentTo( x ) = nullptr; //切断来自父节点的指针
0003    if ( x->parent ) x->parent->updateHeightAbove(); //更新原祖先们的高度
0004    BinTree<T> S; S._root = x; x->parent = nullptr; //新树以x为根
0005    S._size = x->size(); _size -= S._size; return S; //更新规模，返回子树
0006 }

遍历

前序、中序、后序遍历。

深复制

0001 template <typename T> BNP<T> clone( BNP<T> p, BNP<T> t ) { //深复制
0002    if ( !t ) return nullptr;
0003    BNP<T> x = new BinNode<T>( t->data, p, nullptr, nullptr, t->height, t->color ); //先序
0004    x->lc = clone( x, t->lc ); x->rc = clone( x, t->rc );
0005    return x; //由t复制出x
0006 }

迭代实现先序遍历：观察先序遍历的行走顺序

藤：起始于根的左侧通路，长子通路

先序遍历相当于自上而下访问藤上节点，再自下而上遍历各右子树。

在访问藤的时候暂时不能访问右子树，需要暂存起来；右子树的遍历顺序和藤的访问顺序恰好相反。

0001 template <typename T, typename V> void preorder1( BNP<T> x, V& visit ) {
0002    Stack<BNP<T>> S; S.push( x ); //从当前节点出发
0003    while ( !S.empty() ) //以右子树为单位，依次访问每一条藤
0004       for ( x = S.pop(); x; x = x->lc ) //自x出发，沿着藤依次
0005          { visit( x->data ); S.push( x->rc ); } //访问各节点，并令右孩子（或空）入栈
0006 }

单循环写法：每次弹出一个节点，先压左孩子，再压右孩子

摊还分析：只有右孩子才能且必须进栈。摊还至每个节点不超过 O (1)。

空间和高度相关。

迭代实现中序遍历：

沿藤分解，自底向上访问藤上节点，没有左节点就转向右孩子。继续遍历右子树。

0001 template <typename T, typename V> void inorder1( BNP<T> x, V& visit ) {
0002    Stack<BNP<T>> S;
0003    while ( x || !S.empty() ) { //只要x非nullptr，或S仍非空
0004       for ( ; x; x = x->lc ) S.push( x ); //藤上节点便自顶而下入栈
0005       visit( ( x = S.pop() )->data );  x = x->rc; //取出并访问栈顶节点，再转向右子树
0006    } //while
0007 }

数学归纳：假设对规模不超过 n 的树成立，考查 n + 1, 根 = x，藤终点 = t，t 的右孩子 = y

先走到藤终点 t，访问，转向右子树 y，递归；返回再转向藤的右子树串，递归。对每个递归都能正确进行，且整个过程正确。

均摊分析：记账法

每个节点 3 块钱，分别支付 push (x) 和 pop (x)。尝试转向右子树的时候，如果右子树不是空树可以让右孩子支付；如果是空树这部分判断开销由 x 的第三块钱支付。

中序后继：

取决于是否有右子树：

有右子树，直接后继是右子树中藤的终点；

没有右子树，直接后继是 x 最低的左祖先（寻找以 x 为前驱的节点）

（前序后继：有左孩子就是左孩子；没左孩子有右孩子就是右孩子；叶子节点找 x 最低的有右孩子的左祖先）

0001 template <typename T> BNP<T> eov( BNP<T> x ) { //End Of Vine
0002    if ( x ) //从x出发
0003       for ( ; x->lc; x = x->lc ); //顺藤下行
0004    return x; //直至终点
0005 } //eov
0006 template <typename T> BNP<T> lla( BNP<T> x ) { //Lowest Left Ancestor
0007    while ( x->parent && x == x->parent->rc ) //右父亲的...右父亲的
0008       x = x->parent; //右父亲的
0009    return x->parent; //左父亲（可能是nullptr）
0010 } //lla
0011 template <typename T> BNP<T> BinNode<T>::succ() //中序后继
0012    { return rc ? eov(rc) : lla(this); } //若有右孩子，则是右子树中藤之终点；否则是最低左祖先

统计所有遍历中 x 被赋值的次数记作 T (n)：把所有的 eov 和 lla 操作打碎到每次递归
根节点 x 转向左子树，统计一次赋值
完成左子树的中序遍历
经过 lla 的最后一步回到 x，算在左子树里面。
访问 x
为查找 eov 转入右子树，算在右子树里面
完成右子树的中序遍历
最后一次 lla 的最后一步回到 x，统计一次赋值
T (n)=T (m)+T (n-m-1)+2, 线性

后序遍历迭代实现：

尽可能向左，左到不能再左才向右，直到全树最左的节点开始遍历。这样的路径设置为藤。

需要用栈记录藤。栈实际存储的是所有的藤。

变量实际记录刚刚访问的上一个节点，要考查下一步访问哪一个节点

右孩子也要被记录到栈里，而且先进后出。

0001 template <typename T> void gotoLeftmostLeaf( Stack<BNP<T>>& S ) {
0002    for ( BNP<T> x = S.top(); x;  ) { //自顶而下，反复考查当前节点
0003       if ( x->rc ) S.push( x->rc ); //右孩子先进后出
0004       if ( x->lc ) { S.push( x->lc ); x = x->lc; } //若有左孩子，则优先左转
0005       else x = x->rc; //实不得已，才向右
0006    } //for
0007 } //gotoLeftmostLeaf
0008 template <typename T, typename V> void postorder1( BNP<T> x, V& visit ) {
0009    Stack<BNP<T>> S; if ( x ) S.push( x ); //辅助栈
0010    while ( !S.empty() ) { //x始终为当前节点
0011       if ( S.top() != x->parent ) //若栈顶非x之父（而为右兄）
0012          gotoLeftmostLeaf( S ); //则在右兄子树中理出对应的藤
0013       x = S.pop(); visit( x->data ); //弹出并访问栈顶（即前一节点之后继）
0014    } //while
0015 }