树的基本概念

树的定义

树是 n（$n\ge 0$）个结点的有限集。当 n = 0 时，称为空树，在任意一棵非空树中应满足：

1. 有且仅有一个特定的称为根的结点

2. 当 n > 1 时，其余结点可分为 m（m > 0）个互不相交的有限集 $T_1,\cdots ,T_m$，其中每个集合本身又是一棵树，并称为根的子树

树的定义是递归的，在树的定义中又用到了其自身，树作为一种逻辑结构，同时也是一种分层结构，有以下特定：

1. 树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱

2. 树中所有结点可以有零个或多个后继

树适合表示具有层次结构的数据，树中除根结点外的某个结点最多只和上一层的一个结点有直接关系

根结点没有直接上层结点，因此在 n 个结点的树中有 n - 1 条边，而树中每个结点与其下一层的零个或多个结点有直接关系

基本术语

1. 根 A 到结点 K 的唯一路径上的任意结点，称为结点 K 的祖先；相对 K 就是它们的子孙，如 B 是 K 的祖先，K 是 B 的子孙

2. 祖先中最接近 K 的结点 E 称为 K 的双亲，而 K 称为 K 的孩子，根结点是唯一没有双亲的结点

3. 有相同双亲的结点称为兄弟，如结点 K 和结点 L 有相同的双亲，即 K 和 L 为兄弟

4. 树中一个结点的孩子个数称为该结点的度，树中结点的最大度数称为树的度，如 B 的度 2，树的度 3

5. 度大于 0 的结点称为分支结点或非终端结点；度为 0 的结点称为叶子结点或终端结点，每个结点的分支数就是该结点的度

6. 结点的层次从树根开始定义，根结点为第 1 层，它的子结点为 2 层，它的子结点的子结点在 3 层，以此类推

7. 结点的深度是从根结点开始自顶向下逐层累加的；结点的高度是从叶结点开始自低向上逐层累加的

8. 双亲在同一层的结点，也就是在同一层的结点，互为堂兄弟，如 G 与 E、F、H、I、J 互为堂兄弟

9. 树的高度或深度是树中结点最大的层数，如图中树的高度或深度为 4

10. 有序树是指树中结点的各子树从左到右是有次序的，不能互换，若可互换就称为无序树

11. 树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上经过的边的个数

12. 树的路径长度是从树根到每个结点的路径长度的总和，相同结点个数下，完全二叉树就是这种路径长度最短的二叉树

13. 森林是 m（$m\ge 0$）棵互不相交的树的集合，把树的根结点删去就成了森林，给森林加个根结点就成了树

注意：树的分支是有向的，即从双亲指向孩子，所以树中路径是从上向下的，同一双亲的两个孩子之间不存在路径

树的性质

考点追踪：树中结点数、度数和高度的关系分析（2010、2016、2022）

这是统考高频考点，多以选择题出现，尤其是指定结点数的 m 叉树最小/最大高度的分析。

1. 树中的结点数等于所有结点的度数之和加 1，因为结点的度数和等于边数和，而结点数等于边数加 1

2. 度为 m 的树中第 i 层上至多有 $m^{i-1}$ 个结点（$i\ge 1$）

3. 高度为 h 的 m 叉树至多有 $(m^h-1)/(m-1)$ 个结点，根据 $1+m+m^2+\cdots +m^{h-1}=(m^h-1)/(m-1)$

4. 具有 n 个结点的 m 叉树的最小高度为 $\lceil {\log }_m(n(m-1)+1)\rceil$

   $1+m+\cdots +m^{h-2}<n\le 1+m+\cdots +m^{h-1}$

   $(m^{h-1}-1)/(m-1)<n\le (m^h-1)/(m-1)$

   $m^{h-1}<n(m-1)+1\le m^h$

   拆开分别求解就有：$h<{\log }_m[n(m-1)+1]+1$，$h\ge {\log }_m[n(m-1)+1]$

   由于 h 只能是正整数，故 $h=\lceil {\log }_m(n(m-1)+1)\rceil$

5. 具有 n 个结点，度为 m 的树，它的高度至多是 n - m + 1

6. 度为 m、高度为 h 的树，至少有 h + m - 1 个结点

核心结论：m 叉树与度为 m 的树的对比 (2025 陷阱)

| 特性 | m 叉树 | 度为 m 的树 |

| :--- | :--- | :--- |

| 度限制 | 任意节点度 $\le m$ | 至少一个节点度 $=m$ |

| 空树情况 | 可以为空 | 不能为空 (至少 m+1 个节点才有度 m) |

| 次序性 | 有序 | 也是有序的 |

二叉树的概念

二叉树的定义及其主要特征

二叉树的定义

二叉树是另一种树形结构，其特点是每个结点至多只有两棵子树，并且二叉树的子树有左右之分，其次序不能任意颠倒

二叉树也以递归的形式定义，二叉树是 n（$n\ge 0$）点的有限集合：

1. 当 n = 0 时，为空二叉树

2. 当 n > 0 时，由一个根结点和两个互不相交的左子树和右子树组成，左子树和右子树分别是一棵二叉树

二叉树有 5 种基本形态：空二叉树、只有根结点、只有左子树、左右子树都有、只有右子树

二叉树与度为 2 的有序树的区别：

1. 度为 2 的树至少有 3 个结点，而二叉树可以为空

2. 若度为 2 的树某个结点只有一个孩子，则这个孩子无需区分左右次序，而二叉树必须区分

几个特殊的二叉树

满二叉树

一棵高度为 h，且含有 $2^h-1$ 个结点的二叉树称为满二叉树

即树中每层都含有最多的结点，且叶子结点都集中在最下一层，并且除叶子结点外每个结点的度均为 2

对满二叉树按层序编号：从根结点 1 起，自上而下，自左向右，这样每个结点都对应一个编号

对于编号为 i 的结点，若有双亲则为 $\lfloor i/2\rfloor$；若有左孩子则为 2i；若有有孩子则为 2i + 1

完全二叉树

考点追踪：完全二叉树的特性与结点数的关系（2009、2011、2018、2025）

务必掌握完全二叉树叶子结点与分支结点、深度的对应规律。若完全二叉树有 $n$ 个结点，则其高度必为 $\lceil {\log }_2(n+1)\rceil$ 或 $\lfloor {\log }_{2}n\rfloor +1$。

高度为 h、有 n 个结点的二叉树，当且仅当其每个结点都与高度为 h 的满二叉树种编号为 1 ~ n 的结点一一对应时，称为完全二叉树

高度为 h、有 n 个结点的完全二叉树具有以下特点：

1. 若 $i\le \lfloor n/2\rfloor$，则结点 i 为分支结点，否则为叶子结点

2. 叶子结点只可能在层次最大的两层上出现，对于最大层次中的叶子结点，都一次排序在该层最左边位置上

3. 若有度为 1 的结点，则只可能有一个，且该结点只有左孩子而无右孩子

4. 按层序编号后，一旦出现某结点为叶子结点或只有左孩子，则编号大于它的结点均为叶子结点

5. 若 n 为奇数，则每个分支结点都有左孩子和右孩子；若 n 为偶数，最大的分支结点只有左孩子，其余的左右都有

二叉排序树

1. 左子树上所有子结点的关键字均小于根结点的关键字

2. 右子树上的所有结点的关键字均大于根结点的关键字

3. 左子树和右子树右各是一棵二叉排序树

平衡二叉树

平衡二叉树是一棵二叉排序树

树上任意结点的左子树和右子树的深度插不超过 1

二叉树的性质

1. 非空二叉树上的叶子结点树等于度为 2 的结点数加 1，即 $n_0=n_2+1$

   结点总数：$n=n_0+n_1+n_2$，分支数：$B=n_1+2n_2$ 又 $n=B+1=n_1+2n_2+1$

   合并就解出方程 $n_0+n_1+n_2=n_1+2n_2+1\to n_0=n_2+1$

2. 非空二叉树上第 k 层上至多有 $2^{k-1}$ 个结点（$k\ge 1$）

3. 高度为 h 的二叉树至多有 $2^h-1$ 个结点（$h\ge 1$）

4. 对完全二叉树按从上到下、从左到右的顺序依次编号 1,2,...,n 则有以下关系：

   1. 当 i > 1 时，结点 i 的双亲编号为 $\lfloor i/2\rfloor$；当 i 为偶数时，是左孩子；为奇数时，是右孩子

   2. 当 $2i\le n$ 时，结点 i 的左孩子编号为 2i，否则无左孩子

   3. 当 $2i+1\le n$ 时，结点 i 的右孩子编号为 2i + 1，否则无右孩子

   4. 结点 i 所在层次或深度为 $\lfloor {\log }_{2}i\rfloor +1$

5. 具有 n 个（n > 0）结点的完全二叉树的高度为 $\lceil {\log }_2(n+1)\rceil$ 或 $\lfloor {\log }_{2}n\rfloor +1$

   根据 $1+2+\cdots +2^{h-2}<n\le 1+2+\cdots +2^{h-1}$ 推出 $h=\lceil {\log }_2(n+1)\rceil$

   根据 $1+2+\cdots +2^{h-2}+1\le n<1+2+\cdots +2^{h-1}+1$ 推出 $h=\lfloor {\log }_{2}n\rfloor +1$

   具体的推导方法与 树的性质 类似

核心结论：二叉树结点与高度究极公式

1. 结点数关系：$n=n_0+n_1+n_2=B+1$；且 $n_0=n_2+1$。

2. 完全二叉树：

• $n$ 为奇数，则 $n_1=0$；$n$ 为偶数，则 $n_1=1$。

• 最后一个分支结点的编号为 $\lfloor n/2\rfloor$。

• 叶子结点可能分布在倒数第一层和倒数第二层。

3. 节点与高度：

• $n$ 个结点的二叉树最小高度为 $\lceil {\log }_2(n+1)\rceil$。

• 高度为 $h$ 的二叉树最多有 $2^h-1$ 个结点。

二叉树的存储结构

顺序存储结构

二叉树的顺序存储是指用一组的地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素

将完全二叉树上编号为 i 的结点元素存储在一维数组下标为 i - 1 的分量中

根据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，它们可以最大可能地节省存储空间，又方便从数组中查找结点，以及结点之间的关系

对于一般的二叉树，为了让数组反应结点之间的关系，只能添加空结点，让它在数组中看似完全二叉树

但这样的话会出现浪费空间的情况，最坏情况下一个高度为 h 且只有 h 结点的单支树需要 $2^h-1$ 个存储单元

注意：数组是从 0 开始的，所以不能直接使用性质 4，需要一些变通

链式存储结构

为了解决顺序存储的空间浪费问题，所以二叉树一般都采用链式存储结构，用链表结点来存储二叉树中的每个结点

二叉链表至少包含 3 个域：数据域、左指针域、右指针域

在实际的不同应用中，还可以增加某些指针域，如增加指向父结点的指针

二叉树的链式存储结构描述如下：

typedef struct BiTNode {

    ElemType data;  // 数据域

    struct BiTNode *lchild, *rchild;  // 左右孩子指针

} BiTNode, *BiTree;

使用不同存储结构时，实现二叉树操作的算法也会不同，依次要根据实际应用场合来选择合适的存储结构

在含有 n 个结点的二叉链表中，含有 n + 1 个空链域

核心结论：二叉链表空指针计算

• 总指针数：$2n$ (每个节点 2 个指针)。

• 非空指针数：$n-1$ (除了根节点，每个节点都有一个指针指向它)。

• 空指针数：$2n-(n-1)=n+1$。

• 线索化后：这 $n+1$ 个空指针被利用为前驱/后继线索。

精选试题

1. 设二叉树有 2n 个结点，且 0 < m < n，则不可能存在 2m 个度为 1 的结点

   因为 $2n=n_0+n_1+n_2=n_1+2n_2+1$ 由于 2n 是偶数，$2n_2$ 是偶数，所以 $n_1$ 必定是奇数

2. 若一个完全二叉树的第 h 层有 k 个叶结点，则该完全二叉树的结点个数最多为 $2^h-1+(2^{h-1}-k)\ast 2$

   当 h 和 h + 1 层有叶结点时结点数最大，逻辑是计算 1 ~ h 层的结点加上 h + 1 层的结点

   1 ~ h 层结点个数是 $2^h-1$ 而 h + 1 层结点个数是 $(2^{h-1}-k)\ast 2$

3. 若一棵深度为 h 的完全二叉树的第 h 层有 k 个叶子结点，则该二叉树共有 $k+2^{h-2}-\lceil k/2\rceil$

   思路是第 h 层的叶子结点加上 h - 1 层的叶子结点

4. 若一棵完全二叉树有 i 个结点，则该二叉树中叶子结点的个数是 $i-\lfloor i/2\rfloor$

   思路是利用完全二叉树的特性，最后一个分支的序号是 $\lfloor i/2\rfloor$

5. 一棵有 n 个叶子结点的完全二叉树，最多有 $h=\lceil {\log }_{2}n\rceil ;(n-2^{h-1})\ast 2+2^h$

   拿到二叉树的高，使用 1 ~ h - 1 的结点加上 h 层的叶子结点

做题思路：

• 可以利用 $n=n_0+n_1+n_2$，$n_0=n_2+1$，$n=n_1+2n_2$ 这三条公式

• 可以利用完全二叉树的性质，如高为 h，它的 h - 1 层的结点有 $2^{h-2}$，1 ~ h - 1 的结点有 $2^{h-1}-1$

• 可以直接在脑袋里面画出二叉树，用空间思维硬刚

二叉树的遍历和线索二叉树

二叉树的遍历

二叉树的遍历是指按某条搜索路径访问树中每个结点，，使得每个结点均被访问一次，而且仅被访问一次

按照先遍历左子树再遍历右子树的原则，常见的遍历次序有：先序遍历、中序遍历、后续遍历，其中序是指根结点何时访问

先序遍历

先序遍历（PreOrder）的操作过程如下：

若二叉树为空，则什么都不做；否则（NLR）：

1. 访问根结点

2. 先序遍历左子树

3. 先序遍历右子树

对于的递归算法代码如下：

void PreOrder(BiTree T){

    if(T == NULL) return ;

    visit(T);  // 访问根结点

    PreOrder(T -> lchild);  // 递归遍历左子树

    PreOrder(T -> rchild);  // 递归遍历右子树

}

中序遍历

中序遍历（InOrder）操作和先序遍历差不多，只是把访问根结点调整到第二步，先左再自己再右（LNR）

void InOrder(BiTree T){

    if(T == NULL) return ;

    InOrder(T -> lchild);

    visit(T);

    InOrder(T -> rchild);

}

后序遍历

后序遍历（PostOrder）操作和先序遍历差不多，只是把访问根结点调整到第三步，先左右再自己（LRN）

void PostOrder(BiTree T){

    if(T == NULL) return ;

    PostOrder(T -> lchild);

    PostOrder(T -> rchild);

    visit(T);

}

每个结点都访问一次且访问一次，故时间复杂度是 O(n)

递归遍历中，最坏情况下有 n 个结点的二叉树是深度为 n 的单支树，空间复杂度为 O(n)

当栈出一个结点 p 后，栈内的元素是 p 的全部祖先，从栈低到栈顶加上 p 是根结点到 p 的路径

很多算法设计中都可以利用这一思路求解，如求根到某结点的路径、求两结点的最近公共祖先等

---

注意：考研很多题是基于这三个遍历模板延申出来的，要对它有很好的领会

递归算法和非递归算法的转换

栈实现中序遍历

使用栈实现中序遍历，考虑到中序遍历就是左中右遍历（对每个结点都进行左中右），就可以得到下面思路：

1. 拿到该结点最左子树，因为中序遍历第一步是做左操作，左又做左操作，所以就拿最左结点

2. 因为是最左子树根据左中右原则，左没有了，自己就是中，先访问自己，然后把右子树做 1 操作

3. 到了这里左右子树都没有了，考虑到父结点是做左操作到自己的，这时应该轮到父结点做中操作了，访问父结点，然后父结点做右操作，对父结点的右子树做 1 操作

根据思路可以得到操作：

1. 如果当前结点不为空，把当前结点和一路左边结点压入栈；相当于第一步，使用栈是为了可以拿到父结点

2. 弹栈访问，并对结点的右子树执行操作 1；这里就相当于把上面思路的 2，3 步合在一起

原理讲完了下面是实现代码：

void InOrder(BiTree T) {

    LiStack S;

    InitStack(S);

    BiTree p = T;

    while(p || !StackEmpty(S)) {

        if(p) {  // 第 1 步把左一路的压入栈

            Push(S, p);

            p = p -> lchild;

        }else {

            Pop(S, p);

            visit(p);  // 第 2 步访问自己，然后对右子树执行 1

            p = p -> rchild;

        }

    }

}

栈实现前序遍历

使用栈实现前序遍历的思考和中序遍历差不多，区别在于前序遍历的逻辑是中左右

前序遍历的结点使用顺序和前序一样，就是访问的位置不一样，只需要调整一下就可以了

void PreOrder(BiTree T){

    LiStack S;

    InitStack(S);

    BiTree p = T;

    while(p || !StackEmpty(S)){

        if(p){

            visit(p);  // 把访问调整为前序遍历的先访问

            Push(S, p);

            p = p -> lchild;

        }else{

            Pop(S, p);

            p = p -> rchild;

        }

    }

}

栈实现后序遍历

使用栈实现后序遍历思考也差不多，后序遍历的核心逻辑是左右中，但操作变得不一样了：

1. 首先和中序一样，先拿到最左的结点

2. 然后直接对右子树做操作 1，因为左右中，现在进行右操作

3. 到了这里左右操作都做完了，现在就可以做中操作，对结点进行访问了

但在代码里面，无法知道右操作是否有做，所以要做个判断，判断不过就要乖乖做右操作：

• 如果没有右子树，就相当于光速做了右操作，就可以中操作了

• 如果上一个做中的结点是右子树结点，那么就是以前做了右操作，可以做中操作

void PostOrder(BiTree T) {

    LiStack S;

    InitStack(S);

    BiTree p = T;

    BiTNode *r = NULL;

    while(p || !StackEmpty(S)) {

        if(p) {  // 做第一步操作，左边直入栈

            Push(S, p);

            p = p -> lchild;

        }else{

            GetTop(S, p);  // p 是 r 的父结点

            if(p -> rchild && p -> rchild != r){  // 判断不过做第二步操作

                p = p -> rchild;

            }else {  // 判断过了做第三步操作

                Pop(S, p);

                visit(p);

                r = p;

                p = NULL;  // 重置 p 指针省的第一步操作了

            }

        }

    }

}

层次遍历

层次遍历是指按树的层从左到右访问结点，进行层次遍历要借助一个队列：

1. 初始化把根结点入队

2. 队列不空，从队列取出一个元素，并访问它

3. 有左子树把左子树入队

4. 有右子树把右子树入队，回第二步

void LevelOrder(BiTree T) {

    LinkQueue Q;

    InitQueue(Q);

    BiTree p;

    EnQueue(Q, T);  // 第一步，根结点入队

    while(!QueueEmpty(Q)) {

        DeQueue(Q, p);  // 第二步，出列并访问

        visit(p);

        if(p -> lchild != NULL) {  // 第三步

            EnQueue(Q, p -> lchild);

        }

        if(p -> rchild != NULL) {  // 第四步

            EnQueue(Q, p -> rchild);

        }

    }

}

注意：这些代码作为一个模板需要达到熟练手写的程度，这样才能将层次遍历模板应用于各种题目之中

由遍历序列构造二叉树

考点追踪：由遍历序列构造二叉树及序列分析（2015、2017、2020、2021、2023）

先序+中序、后序+中序均可唯一确定二叉树（也是大题常考构造算法）。先序+后序无法唯一确定二叉树。

由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树：

1. 先序序列的第一个是二叉树的根结点；拿它去中序序列可以把中序序列分成两半，变成左子树的中序和右子树的中序

2. 然后在先序序列中找到对应的左子序列和右子序列

3. 在先序序列中，左子序列的第一位就是左子树的根部；右子序列的第一位就是右子序列的根部

4. 依次递归下去，就能找到唯一的二叉树了

例子：求先序序列（ABCDEFGHI）和中序序列（BCAEDGHFI）所确定的二叉树

同理，也可以求后序序列和中序序列的二叉树，后序序列的最后一个结点就是根结点

同理，也可以求层序序列和中序序列的二叉树，第一个为根结点，若中序左右子树都有，第二个是左子树根结点，以此类推

注意：只知道二叉树的先序序列和后序序列，是无法确定唯一的二叉树的

选择题得到的理论

• 如果前序序列是后序序列的反转设长度为 n，那么一共可以构成 $2^{n-1}$ 棵二叉树，因为它们只会有一个叶结点

• 当两个结点的前序序列为 XY、后序序列为 YX 时，则 X 为 Y 的祖先，XZY 这时不能确定 X 和 Y 的关系

• 先序序列为 1...n 的不同二叉树的个数是其出栈元素不同排列的个数 ${\displaystyle \frac{1}{n+1}}{C}_{2n}^n$

  先序序列输出的是入栈的元素，而中序序列输出的是出栈的元素

  而先序和中序能确定一棵树，也就是有多少种中序就有多少棵树，也就是栈的出栈序列的个数

  如何保证先序序列和中序序列真的能构成一棵树？

  根据前序和后序思想，要进左子树必须先进其父结点，要进右子树必须前出其父结点，就有对于一个结点：

  • 当它在栈中时，往后入栈的元素都是它的左子树

  • 出栈之后，往后入栈的元素都是它的右子树

  所以出栈的前后只会影响左右性，不会对是否构成一棵树构成影响

先中序列形成二叉树代码

思路：

1. 根据先序序列第一位确定树的根结点

2. 根据根结点在中序序列中划分出二叉树的左右子树包含那些结点

3. 根据左右子树结点在先序序列中的次序确定子树的根结点，即递归回步骤 1

/**

 * A: 前序序列

 * B: 中序序列

 * l1: A 的第一个结点的下标

 * h1: A 的最后一个结点的下标

 * l2: B 的第一个结点的下标

 * h2: B 的最后一个结点的下标

 */

BiTree PreInCreat(ElemType A[], ElemType B[], int l1, int h1, int l2, int h2) {

    int i, llen, rlen;

    root = (BiTNode*)malloc(sizeof(BiTNode));  // 建立根结点

    root -> data = A[l1];

    for (i = l2; B[i] != root -> data;  i++);  // 在中序找出该结点的位置

    llen = i - 12;  // 左子树序列的长度

    rlen = h2 - i;  // 右子树序列的长度

    

    if (llen)  // 如果左子树序列不为空，递归建立；否则设左子树为空

        root -> lchild = PreInCreat(A, B, l1 + 1, l1 + llen, l2, l2 + llen - 1);

    else

        root -> lchild = NULL;

    

    if (rlen)

        root -> rchild = PreInCreat(A, B, h1 - rlen + 1, h1, h2 - rlen + 1, h2);

    else

        root -> rchild = NULL;

    

    return root;  // 返回局部二叉树的根结点

}

线索二叉树

线索二叉树的基本概念

考点追踪：线索的指向及后序线索二叉树的特点（2010、2013、2014）

线索二叉树的判定条件（特别是 lchild 或 rchild 为空时才作为线索）和在后序线索二叉树中找后继的需要知道双亲的问题，经常设置陷阱。

线索二叉树就是把二叉表的 n + 1 个空指针利用起来，分别指向前驱和后继

规定：若无左子树，令 lchild 指向其前序结点；若无右子树，令 rchild 指向其后继结点；此外还增加两个标志域来表示指针域指向的是孩子还是前序或后继

引用线索二叉树是为了加快查找结点前驱和后继的速度，线索二叉树是一种物理结构

typedef struct ThreadNode{

    ElemType data;  // 数据域

    struct ThreadNode *lchild, *rchild;  // 左右孩子指针

    int ltag, rtag;  // 左右线索标志

}ThreadNode, *ThreadTree;

ltag 为 1 时指向前驱，为 0 时指向左孩子；rtag 为 1 时指向后继，为 0 时指向右孩子

以这种结构构成的二叉链表来存储二叉树叫做线索链表，其中指向前驱和后继的指针叫做线索，加上线索的二叉树称为线索二叉树

中序线索二叉树的构造

二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索，通过遍历一次二叉树来实现

中序线索二叉树的前驱就是中序遍历时结点的前驱，前序、后序线索二叉树类似

附设 pre 指针指向前驱结点（刚刚访问的结点），指针 p 是正在访问的结点，在中序遍历中，调整它们的关系，代码如下：

// 中序遍历线索化二叉树，

void InThread(ThreadTree &p, ThreadTree &pre){

    if(p != NULL){

        InThread(p -> lchild, pre);  // 线索化左边的二叉树

        if(p -> lchild == NULL){  // 当前结点左子树为空，指向前驱

            p -> lchild = pre;

            p -> ltag = 1;

        }

        if(pre != NULL && pre -> rchild == NULL){  // 前驱的右子树为空，指向后继

            pre -> rchild = p;

            pre -> rtag = 1;

        }

        pre = p;  // 更新前驱，注意这个是引用类型

        InThread(p -> rchild, pre);  // 线索化右边的二叉树

    }

}

 

// 建立中序线索化二叉树

void CreatInThread(ThreadTree T){

    ThreadTree pre = NULL;

    if(T != NULL){

        InThread(T, pre);  // 线索化

        pre -> rchild = NULL;  // 处理遍历的最后一个结点

        pre -> rtag = 1;

    }

}

二叉树的线索链表上添加一个头结点，令其 lchild 指向二叉树的根结点，rchild 指向中序遍历的最后一个结点

令中序遍历的第一个结点的 lchild 和最后一个结点的 rchild 均指向头结点

这就好比为二叉树建立了一个双向线索链表，方便从前往后或从后往前对线索二叉树进行遍历

中序线索二叉树的遍历

线索二叉树的结点中隐含了线索二叉树的前驱与后继的信息

遍历时只要找到序列中的第一个结点，然后依次找结点的后继，直至后继为空

当右标志为 1 时，后继为右线索；当右标志为 0 时，后继为右子树的最左子树

// 找中序线索二叉树中中序序列下的第一个结点

ThreadNode *Firstnode(ThreadNode *p){

    while(p -> ltag == 0) p = p -> lchild; // 最左下结点（不一定是叶结点）

    return p;

}

 

// 找中序线索二叉树中结点 p 在中序序列下的后继

ThreadNode *Nextnode(ThreadNode *p){

    if(p -> rtag == 0) return Firstnode(p -> rchild);

    return p -> rchild;  // rtag == 1直接返回后继线索

}

 

// 遍历线索二叉树

void Inorder(ThreadNode *T){

    for(ThreadNode *p = Firstnode(T); p != NULL; p = Nextnode(p))

        visit(p);

}

先序和后序线索二叉树

先序线索二叉树和后序线索二叉树的代码类似，只需变动线索化的代码与线索化左右子树递归的位置

// 先序线索化

void PreThread(ThreadTree T){

    if(T!=NULL){

        ......;  // 线索化，与中序先序化一样

        if(T -> ltag != 1)  // 因为上面进行了线索化，所以需要判断一下

            PreThread(T -> lchild);

        if(T -> rtag != 1)  // 避免回溯回来造成死循环，当父结点的后继是自己时，只有一个左结点时

            PreThread(T -> rchild);

    }

}



// 后序线索化，与中序先序化一样

void PostThread(ThreadTree T){

    if(T != NULL){

        PostThread(T -> lchild);

        PostThread(T -> rchild);

        ......;  // 线索化

    }

}

先序线索二叉树中找后继结点：

• 如果有左孩子，则其就是后继

• 如果只有右孩子，则其就是后继

• 如果为叶结点，右索引指向的就是后继

后序线索二叉树中找后继结点：

• 如果是二叉树的根，则没有后继

• 如果是双亲的左孩子，且双亲有右孩子，后继为双亲的右孩子按后序遍历列出的第一个结点

• 如果是双亲的右孩子，或是左孩子且没有右孩子，后继为双亲

后序线索二叉树在找后继的时候需要知道双亲，所以在遍历的时候仍需要栈支持，或者采用带标志域的三叉链作为存储结构，先序线索二叉树找其前驱时也不能直接找到

// 先序线索二叉树的后继

ThreadNode *Nextnode(ThreadNode* p){

    if(p -> rtag == 0){

        if(p -> lchild != NULL) return p -> lchild;  // 有左孩子

        return p -> rchild;  // 只有右孩子

    }

    return p -> rchild;  // 叶结点返回线索

}





// 遍历先序线索二叉树

void Preorder(ThreadTree T){

    for(ThreadNode *p = T; p != NULL; p = Nextnode(p))

        visit(p);

}



// 后序线索二叉树的前驱

ThreadNode *Prenode(ThreadNode* p){

    // 后序线索二叉树的前驱刚好就是先序线索二叉树的后继的反转

    if(p -> ltag == 0){

        if(p -> rchild != NULL) return p -> rchild;

        return p -> lchild;

    }

    return p -> lchild;

}



// 逆向遍历线索二叉树

void RevPostorder(ThreadTree T){

    // 如果想要正向遍历可以使用栈来辅助

    for(ThreadNode *p = T; p != NULL; p = Prenode(p))

        visit(p);

}

综合应用题

非递归求二叉树高度

问题：假设二叉树采用二叉链表存储，设计一个非递归算法求二叉树的高度

思路：

使用层次遍历，记录当前层的最后一个元素，当出列的是当前层的最后一个元素时，记录下一层的最后元素，层数加一

因为出列到当前层的最后一个元素时，下一层的所有元素已经入队了，所有这时记录队尾就是下一层最后一个元素

int Btdepth(BiTree T) {

    if (!T) return 0;

    int front = -1, rear = -1;

    int last = 0, level = 0;

    BiTree Q[MaxSize];

    Q[++rear] = T;  // 根入列

    BiTree p;

    while (front < rear) {

        p = Q[++front];  // 出队

        if (p->lchild)  // 左孩子入队

            Q[++rear] = p->lchild;

        if (p->rchild)  // 右孩子入队

            Q[++rear] = p->rchild;

        if (front == last) {  // 当出队的是当前层最后一个时

            level++;  // 层数加一

            last = rear;  // 指向下一层的最后一个

        }

    }

    return level;

}

访问 x 的所有祖先

问题：在二叉树中查找值为 x 的结点，试编写算法打印值为 x 的结点的所有祖先，假设值为 x 的结点不多于一个

思路：使用带栈的后序遍历，当访问到值为 x 的结点时，栈中所有元素均为该结点的祖先

后序遍历是指，访问可以任何时候访问，但入栈要先左后右，出栈要在左右入栈之后

typedef struct {

    BiTree t;

    int tag;  // 0 表示左孩子被访问；1 表示右孩子被访问

} stack;



void Search(BiTree bt, ElemType x) {

    stack s[];  // 假设栈足够大

    int top = 0;

    while (bt != NULL || top > 0) {

        // 访问该结点，访问在左之前，而出栈在右之后，中操作其实就是出栈操作

        while (bt != NULL && bt -> data != x) {

            s[++top].t = bt;

            s[top].tag = 0;

            bt = bt -> lchild;

        }

        if (bt != NULL && bt -> data == x) {  // 找到 x

            printf("所查结点的所有祖先结点的值为：\n");

            for (i = 1; i <= top; i++)

                printf("%d", s[i].t -> data);

            exit(1);

        }

        // 退栈，右结点都被访问了的结点已经遍历完了，退到右结点没被访问的结点

        // 感觉可以把判断操作放在出栈之后，而不是在入栈的时候直接判断，可能是为了节省性能才先访问吧

        while (top != 0 && s[top].tag == 1)

            top--;

        // 来到这里 bt 已经是 NULL，且栈顶只有右结点未被访问

        if (top != 0) {

            s[top].tag = 1;  // 设置为访问它的右结点

            bt = s[top].t -> rchild;  // 开始访问右结点

        }

    }

}

感觉这种递归没有栈实现后序遍历的代码好用，思维也没它清晰

访问 p、q 的最近共同祖先

问题：设一棵二叉树的结点结构为 (LLINK, INFO, RLINK)，ROOT为指向该二叉树根结点的指针，p 和 q 分别指向该二叉树中任意两个结点的指针，试编写算法 ANCESTOR(ROOT, p, q, r)，找到 p 和 q 的最近公共祖先结点 r

思路：使用后序遍历加辅助栈，把第一个找到的结点的所有祖先放入辅助栈中，找到第二个时把辅助栈与当前栈比较

typedef struct {

    BiTree t;

    int tag;  // 0 表示左孩子被访问；1 表示右孩子被访问

} stack;



BiTree Ancestor(BiTree ROOT, BiTNode *p, BiTNode *q) {

    stack s[], s1[];  // 假设栈足够大

    int top = 0, top1;

    BiTree bt = ROOT;

    bool find = false;

    while (bt != NULL || top > 0) {

        // 访问该结点，访问在左之前，而出栈在右之后，中操作其实就是出栈操作

        while (bt != NULL) {

            s[++top].t = bt;

            s[top].tag = 0;

            bt = bt -> lchild;

        }

        // 右结点都被访问了的结点已经遍历完了，出栈执行操作了

        while (top != 0 && s[top].tag == 1) {

            if (s[top].t == p || s[top].t == q)  // 是要找的两结点之一

                if (!find) {  // 找到第一个

                    for (int i = 1; i <= top; i++)  // 把栈拷贝到辅助中保存

                        s1[i] = s[i];

                    top1 = top;

                    find = true;

                } else {  // 找到第二个

                    for (int i = 2; i <= top; i++)  // 第一个不相等的结点的父结点就是最近的共同祖先

                        if (s1[i].t != s[i].t)

                            return s[i - 1].t;

                }

            top--;

        }

        // 来到这里 bt 已经是 NULL，且栈顶只有右结点未被访问

        if (top != 0) {

            s[top].tag = 1;  // 设置为访问它的右结点

            bt = s[top].t -> rchild;  // 开始访问右结点

        }

    }

}

我看见答案的时候很失望，居然是这种简单普遍的解法，代码也有点问题，修改了一下不一定能执行

树的最大宽度

题目：假设二叉树采用二叉链表存储结构，设计一个算法，求非空二叉树 b 的宽度（结点最多的那层的结点个数）

思路：使用队列层序遍历，队列中不仅带结点，还带结点所在的层数

根部层数为 1，入队时左子树的层数是自己层数加一，右子树也是一样

最后扫描队列求出各层的结点的总数，最大的层结点总数就是树的宽度了

满二叉树的先序转后序

题目：设有一棵满二叉树，所有结点值均不同，已知其先序序列为 pre，设计一个算法求其后序序列 post

思考：对于先序和后序有一条规则，先序的第一位等于后序的最后一位，那么我们根据这条规则就可以想出：

1. 取出先序序列的第一个放入后序序列的最后一个

2. 除掉第一位的先序序列从中间拆开，左半是左子树，右半是右子树；左 1 就时左根，右 1 就是右根

3. 后序序列是左右中，现在反过来就是中右左了，第二步时中放完了，现在放右，对右子树根结点递归到 1

4. 根据中右左，右子树的信息放完了就该放左子树，从左子树开始，对左子树根结点递归到 1

/**

 * pre: 前序序列

 * l1: pre 的第一个结点的下标

 * h1: pre 的最后一个结点的下标

 * post: 后序序列

 * l2: post 的第一个结点的下标

 * h2: post 的最后一个结点的下标

 */

void PreToPost(char pre[], int l1, int r1, char post[], int l2, int r2) {

    int mid;

    if (r1 >= l1) {

        post[r2] = pre[l1];  // 中

        mid = (r1 - l1) / 2;

        PreToPost(pre, l1 + 1, l1 + mid, post, l2, l2 + mid - 1);  // 左，前半段放左

        PreToPost(pre, l1 + mid + 1, r1, post, l2 + mid, r2 - 1);  // 右，后半段放右

    }

}

中序结点找后序前驱

题目：写出在中序线索二叉树里查找指定结点在后序的前驱结点的算法

思路：结合中序和后序线索二叉树，思考各种情况，得到以下规律：

1. 若结点 p 有右孩子，则右孩子是其前驱

2. 若无右孩子但有左孩子，则左孩子是其前驱

3. 拿其中序左线索，为空就没有前驱

4. 中序左线索指向的祖先 f，它有左子树，则前驱就是 f 的左子树

5. 若 f 的左子树为空，就取其中序左线索，循环直到它左子树不为空，前驱就是左子树

6. 若循环时 f 的左子树为空了（没有线索了）就没有前驱

BiThrTree InPostPre(BiThrTree t, BiThrTree p) {

    BiThrTree q;

    if (p -> rtag == 0)  // 第一步，有右返回右

        q = p -> rchild;

    else if (p - > ltag == 0)  // 第二部，无右有左返回左

        q =  p -> lchild;

    else if (p -> lchild == NULL)  // 第三步，无线索无前驱

        q = NULL;

    else {

        while (p -> ltag == 1 && p -> lchild != NULL)  // 循环直到有左子树

            p = p -> lchild;

        if (p -> ltag == 0)  // 有左子树，前驱是左子树

            q = p -> lchild;

        else  // 没有无前驱

            q = NULL;

    }

    return q;

}

树、森林

树的存储结构

双亲表示法

采用一组连续的空间存储每个结点，并在每个结点中记录其父结点的索引，它的存储结构描述：

#define MAX_TREE_SIZE 100



typedef struct {

    ElemType data;  // 数据元素

    int parent;  // 双亲的索引

} PTNode;



typedef struct {

    PTNode nodes[MAX_TREE_SIZE];  // 结点信息

    int n;  // 结点数

}

该存储结构利用了每个结点只有一个双亲的性质，可以很快得到结点的双亲，但获取结点的孩子需要遍历整个结构

注意：注意树和二叉树的最大的区别是，它的儿子数量不是固定的，所以才需要记录双亲的索引

孩子表示法

将每个结点的孩子都用单链表连接起来形成一个线性结构，此时 n 个结点就有 n 个孩子链表

该存储结构寻找子女操作很简单，但是寻找双亲就要迭代全部整个孩子链表了

孩子兄弟表示法

孩子兄弟表示法又称二叉树表示法，以二叉链表作为树的存储结构

其中左指针指向结点的第一个孩子结点，右指针指向该结点的下一个兄弟结点

typedef struct CSNode {

    ElemType data;

    struct CSNode *firstchild, *nextsibling;

} CSNode, *CSTree;

该存储结构可以方便地实现树转换为二叉树的操作，易于找结点的孩子，但找其双亲比较麻烦

若为每个结点增设一个 parent 域指向其父结点，则查找结点的父结点也很方便

树、森林与二叉树的转换

给定一森林，可以找到唯一的二叉树与之对应；同样的给定一棵二叉树，可以找到唯一的森林与它对应

二叉树与森林从物理结构上看它们的二叉链表是相同的，但解释不一样

以下都是逻辑上的转换（考试画图，或选择题逻辑），因为在计算机内二叉树本就是森林的存储结构，不用转换

选择题：将森林 F 转换为对应的二叉树 T，F 中叶结点的个数等于 T 中左孩子指针为空的结点个数；F 中的非终端结点个数等于 T 中右孩子指针为空的结点个数减一

1. 根据左孩子右兄弟，T 中左指针为空意味着森林的某个结点没有孩子，所以左指针空的个数是 F 中叶结点的个数

2. 根据左孩子右兄弟，T 中右指针为空意味着森林中某个结点没有右兄弟

   首先非终端结点肯定有孩子，那么它的孩子中肯定就会有一个没有右兄弟

   就有 T 中右指针为空的个数至少为 F 中非终端的个数

   其次对于根结点来说，除了它的孩子会没有右兄弟外它自己也没有右兄弟

   把根结点算上，就有 T 的右指针为空的个数就是 F 的非终端的个数加一

树转换成二叉树

每个结点的左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟，这是左孩子右兄弟

树转换成二叉树的画法：

1. 在兄弟结点之间加一连线

2. 仅保留指向第一个孩子的指针

3. 以树根为中心顺时针旋转 45°

森林转换成二叉树

森林转换成二叉树与树类似，只要把第二棵树看成第一棵树的右兄弟，依次类推就好了

森林转换成二叉树的画法：

1. 将森林的没课树转换成相应的二叉树

2. 每棵树的根视为兄弟关系，在每棵树的根间加一条连线

3. 以第一棵树的根为中心顺时针旋转 45°

二叉树转换成树、森林

• 若二叉树非空，二叉树的根及其左子树为第一棵树的二叉树形式

• 将根的右链断开，它的右子树视为一个森林来处理，如此反复，直到没有右子树

• 最后将每课二叉树依次转换成树，就得到原森林

树和森林的遍历

树的遍历

• 先根遍历：若树非空，先访问根结点，再依次遍历根结点的每个子树，遍历时仍采用先根遍历

  其遍历序列与这棵树相应二叉树的先序遍历相同

• 后根遍历：若树非空，先依次遍历根结点的每个子树，再访问根结点，遍历时仍采用后根遍历

  其遍历序列与这棵树相应的二叉树的中序遍历相同

• 层次遍历：与二叉树的层次遍历一样，使用队列，先入根结点，出列一个结点时把其子树全部入列

森林的遍历

1. 先序遍历森林，若森林非空，就执行遍历：

   • 访问森林中第一棵树的根结点

   • 先序遍历第一棵树种根结点的子树森林（这两步相当于前根遍历，先自己，再遍历子结点）

   • 先序遍历除去第一棵树之后剩余的树构成的森林（对第二棵树，第三棵等递归使用前根遍历）

2. 中序遍历森林（也可以叫后序遍历），若森林非空，就执行遍历：

   • 中序遍历森林中第一棵树的根结点的子树森林

   • 访问第一棵树的根结点（这两步相当于后根遍历，先遍历子结点，再自己）

   • 中序遍历除去第一棵树之后剩余的树构成的森林（对第二棵树，第三棵等递归使用后根遍历）

先序遍历森林就相当于先序遍历其相应的二叉树；中序遍历森林就相当于中序遍历其相应的二叉树

注意：中序遍历森林，也可以叫中根遍历因为对于其二叉树是中根遍历，也可以叫后根遍历因为对于树是后根遍历的

*树的应用——并查集

考点追踪：并查集的森林与存储（与图的应用密切结合）

并查集是 Kruskal 最小生成树算法的核心组件。考试多以判断题、选择题形式考查它的双亲数组存储方式、初始化及路径优化后的合并查找过程。

并查集是一种简单的集合表示，它支持以下三种操作：

Union(S, Root1, Root2);  // 把集合 S 的子集合 Root2 并入子集合 Root1，要求它们不能相交

Find(S, x);  // 查找集合 S 中单元素 x 所在的子集合，返回子集合名字

Initial(S);  // 将集合 S 中的每个元素都初始化为只有一个单元的集合

通常用森林的双亲表示作为并查集的存储结构，每个子集以一棵树表示

通常以数组的下标表示元素名，用根结点的下标代表子集合名，根结点的双亲结点为负数

合并两个子集，只需将其中一个子集合根结点的双亲指针指向另一个集合的根结点

使用双亲指针数组作为并查集存储表示时，集合元素编号从 0 到 size - 1，其中 size 是最大元素的个数

#defind SIZE 100

int UFSets[SIZE];  // 集合元素（双亲数组）



// 初始化并查集，所有初始化为 -1，即各自都是一棵树

void Initial(int s[]) {

    for (int i = 0; i < SIZE - 1; i++)

        s[i] = -1;

}



// 查找 S 中包含 x 的树的根结点

int Find(int S[], int x) {

    while (S[x] >= 0)

        x = S[x];

    return x;

}



// 合并两个不相交的子集，即求并集

void Union(int S[], int Root1, int Root2) {

    S[Root2] = Root1;

}

考点追踪：并查集优化（2025 高频：路径压缩）

1. 按大小合并（Union）：小树挂在大树下。使得构造的森林深度不超过 $\lfloor {\log }_{2}n\rfloor +1$。

2. 路径压缩（Find）：在查找时，将路径上所有结点直接指向根。使后续查找接近 $O(1)$。

3. 复杂度：采用优化后，平均操作时间为 $O(\alpha (n))$（反阿克曼函数，增长极慢）。

4. 应用：Kruskal 算法判环、连通分量统计。

层次序列及度构成孩子兄弟链表

问题：已知一棵树的层次序列及每个结点的度，编写算法构成此树的孩子兄弟链表

思路：由于有结点的度，我们可以拿到结点的子结点并链到结点上，只需要使用遍历记录子结点的位置合父结点的位置

#define maxNodes 15



void createCSTreeDegree(CSTree &T, DataType e[], int degree[], int n) {

    CSTree *pointer = new CSTree[maxNodes];

    int i, j, d, k = 0;

    for (i = 0; i < n; i++) {  // 初始化数组

        pointer[i] = new CSNode;

        pointer[i] -> data = e[i];

        pointer[i] -> lchild = pointer[i] -> rsibling = NULL;

    }

    for (i = 0; i < n; i++) {  // 调整树的关系

        d = degree[i];  // 当前结点的度数

        if (d) {

            k++;

            pointer[i] -> lchild = pointer[k];

            for (j = 2; j <= d; j++) {  // 把该结点的子结点链入

                k++;

                pointer[k - 1] -> rsibling = pointer[k];

            }

        }

    }

    T = pointer[0];

    delete [] pointer;

}

书上采用的是辅助数组直接初始化，然后分别链上去，而我更想用队列，下面是我使用队列写的

// 创建新的结点

CSNode *createCSNode(int data) {

	CSNode *r = new CSNode;

	r->data = data;

	r->rchild = r->lchild = NULL;

	return r;

}



void createCSTreeDegree(CSTree &T, int e[], int degree[]) {

	LinkQueue Q;

	int i = -1, j, k = 0, d;

	CSNode *p, *q;

	InitQueue(Q);

	T = createCSNode(e[0]);  // 创建根部结点

	EnQueue(Q, T);

	while (!IsEmpty(Q)) {

		DeQueue(Q, p);

		i++;

		if (d = degree[i]) {  // 如果有度就是有儿子，把儿子链入然后入队列

			k++;

			q = p->lchild = createCSNode(e[k]);

			EnQueue(Q, q);

			for (j = 2; j <= d; j++) {

				k++;

				q->rchild = createCSNode(e[k]);

				q = q->rchild;

				EnQueue(Q, q);

			}

		}

	}

}

树与二叉树的应用

二叉排序树

二叉排序树的定义

二叉排序树也称二叉查找树，是一棵空树，或者是具有以下特性的二叉树：

1. 若左子树非空，则左子树上所有结点的值均小于根结点的值

2. 若右子树非空，则右子树上所有结点的值均大于根结点的值

3. 左、右子树也分配时一棵二叉排序树

根据二叉树的定义有左子树的值 < 根结点值 < 右子树的值，所以对二叉排序树进行中序遍历就会得到一个递增序列

二叉排序树的查找

二叉排序树从根结点开始查找，先和根结点的值进行比较，相等则查找成功；小于就递归左子树；大于就递归右子树

BSTNode *BST_Search(BSTree T, int key) {

    while(T != NULL && key != T -> key) {

        if(key > T -> key) T = T -> rchild;

        else T = T -> lchild;

    }

    return T;

}

二叉排序树的插入

二叉排序树作为一种动态树表，特点是树的结构不是一次生成的，而是在查找过程中发现值不存在后的插入

插入过程如下：

• 若原二叉树为空则直接插入结点

• 若关键字 k 小于根结点值，则插入左子树；否则插入到右子树

插入的点一定是一个新添加的叶结点，而且是查找失败时的查找路径上最后访问结点的子结点

int BST_Insert(BSTree &T, int k){

    if (T == NULL) {

        T = (BSTNode*)malloc(sizeof(BSTNode));

        T -> key = k;

        T -> lchild = T -> rchild = NULL;

        return 1;  // 插入成功

    } else if (T -> key == k)

        return 0;  // 插入失败

    else if(key > T -> key)

        return BST_Insert(T -> rchild, key);  // key 比根结点的大插到右边

    else

        return BST_Insert(T -> lchild, key);  // key 比根结点的小插到左边

}

二叉排序树的构造

二叉排序树的构造就是从一棵空树出发，一次输入元素，将它们插入二叉排序树中的合适位置

void Creat_BST(BSTree &T, int str[], int n) {

    T = NULL;

    for(int i = 0; i < n; i++)

        BST_Insert(T, str[i]);

}

二叉排序树的删除

二叉排序树的删除不是把以该结点为根的子树都删除，而是仅删除该结点，然后调整二叉排序树，使他仍是二叉排序树

删除操作的实现过程按 3 种情况来处理：

1. 若被删除结点 z 是叶结点，则直接删除，因为不会破开二叉排序树的性质

2. 若结点 z 只有一棵子树，则让 z 的子树称为 z 的父结点的子树，代替 z 的位置

3. 若结点 z 有左右两棵子树，则令它的直接后继（或直接前驱）与 z 交换位置，这时再删除 z 情况就是第一步或第二步了

思考：二叉排序树种删除后再插入某结点，的到的二叉树取决于删除的位置，若删除的是叶结点那么相同，否则不相同

二叉排序树的查找效率

二叉排序树的查找效率，主要取决于树的高度。二叉树的结点分布比较均匀像平衡二叉树那样，平均查找长度为 $O({\log }_{2}n)$；但如果是一个单支树，则平均查找长度为 O(n)

在最坏情况下，即构造二叉排序树的输入序列是有序的，则会形成一个倾斜的单支树

在等概率情况下，查找成功的平均查找长度为 $({\displaystyle \sum _{i=1}^{deep}i\times nu{m}_i)/n}$ 其中 deep 是总深度，$nu{m}_i$ 是第 i 层的结点数，n 是结点总数

在等概率情况下，查找失败的平均查找长度为 “(${\displaystyle \sum }$ NULL 的父亲的层数) / NULL 的个数”

从查找过程看，二叉排序树与二分查找相似，其平均时间性能差不多，但二分查找的判定树唯一，而二叉排序树的查找不唯一，相同的关键字其插入顺序不同可能生成不同的二叉排序树

维护表的有序性而言，插入和删除元素时，二叉排序树平均执行时间为 $O({\log }_{2}n)$，而有序顺序表则需要 O(n)

所以，当有序表是静态查找表时，宜用顺序表作为存储结构；若有序表是动态查找表，则选择二叉排序树作为逻辑结构

平衡二叉树

平衡二叉树的定义

避免树的高度增长过快，降低二叉排序树的性能，定义平衡二叉树，简称平衡树，它的左右子树高度差的绝对值不超过 1

结点左子树与右子树的高度差称为该结点的平衡因子，则平衡二叉树的平衡因子只可能是 -1、0、1

平衡二叉树可以定义为一棵空树，或具有以下性质的树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度差的绝对值不超过 1

平衡二叉树的旋转

左旋转

左旋是在保持二叉排序树的规则下，令左边层数加一，右边层数减一，步骤为：

1. 设 r 是根，p 为根的右子树

2. r 的右子树变成 p 的左子树

3. p 的左子树变成 r

4. 根结点变成 p

右旋转

右旋是在保持二叉排序树的规则下，令右边层数加一，左边层数减一，步骤为：

1. 设 r 是根，p 是根的左子树

2. r 的左子树变成 p 的右子树

3. p 的右子树变成 r

4. 根结点变成 p

平衡二叉树的插入

在插入或删除后，检查是否导致了平衡二叉树失衡，若失衡就找到距离插入点最近的失衡树，对它进行调整，使之平衡

调整是递归的，从最小失衡树，即距离插入点最近的不平衡树，一直向上调整，直到整棵树没有失衡点为止

平衡二叉树的插入部分和二叉查找树相同，若插入后不平衡需要调整，则有以下 4 条规律：

1. LL 平衡旋转，当插入的点在失衡点的左子树的左子树内，以失衡点为轴进行右旋

2. RR 平衡旋转，当插入的点在失衡点的右子树的右子树内，以失衡点为轴进行左旋

3. LR 平衡旋转，当插入的点在失衡点的左子树的右子树内，以失衡点的左子树为轴进行左旋，旋转后变成情况 1

4. RL 平衡旋转，当插入的点在失衡点的右子树的左子树内，以失衡点的右子树为轴进行右旋，旋转后变成情况 2

/**

 * 插入后进行调整

 * root : 根结点

 * p : 要调整的结点

 * d : 插入的数据

 */

void fixAfterInsert(btlink &root, btlink p, int d) {

    if (d < p -> element) {

        // 情况 3，在左边的右边

        if (d > p -> left -> element) rotateLeft(root, p -> left);

        // 情况 1，在左边的左边

        rotateRight(root, p);

    } else {

        // 情况 4，在右边的左边

        if (d < p -> right -> element) rotateRight(root, p -> right);

        // 情况 2，在右边的右边

        rotateLeft(root, p);

    }

}

插入点在哪里就意味着哪里的层数多加了一层导致失衡，所以要使用旋转把插入点的层数分一层给它兄弟，以达到平衡

LR 时左旋把左边的右边多出的一层给到左边的左边，这样就是左边的左边多层数，就是 LL 了；RL 同理

旋转只会让这个被旋转的最小失衡树平衡起来，但这个树的祖先仍然有可能会失衡，所以要递归上去检查和调整

平衡二叉树的查找

平衡二叉树的查找过程与二叉排序树的相同，因此关键字比较的次数不超过树的深度

假设以 $n_h$ 表示深度为 h 的平衡树中含有的最少结点数，有 $n_0=0,n_1=1,n_2=2$ 并且有 $n_h=n_{k-1}+n_{k-2}+1$

那么就有平衡二叉树的最大深度为 $O({\log }_{2}n)$，因此平衡二叉树的平均查找长度为 $O({\log }_{2}n)$，注意这里是有 O 的

平衡二叉树的最少结点数

根据平衡二叉树的定义，它的左右子树都是平衡二叉树

自己是含有最少结点数，当且仅当左右子树也是含有最小结点的情况下

那么自己的结点数是左子树的结点 + 右子树的结点 + 1（根结点）

含有最小结点数，那么左右子树的高度差必然为一

综上就得出：

1. $n_h=n_{k-1}+n_{k-2}+1$，一个子树结点 + 另一个子树结点 + 1（根结点）

2. 非叶子结点的平衡叶子的绝对值都为一，那么这棵树是含结点最少的平衡二叉树

哈夫曼树和哈夫曼编码

哈夫曼树的定义

在许多应用中，树中结点常常被赋予一个表示某种意义的数值，称为该结点的权

该结点的带权路径长度，是从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积

树的带权路径长度，记为 $WPL={\displaystyle \sum _{i=1}^n{w}_i{l}_i}$ 其中 $w_i$ 是第 i 个叶结点所带的权值，$l_i$ 是该也结点到根结点的路径长度，即所有叶结点的带权路径长度的和

哈夫曼树是相同的权叶结点，但 WPL 最小的树，如上面 c 是一棵哈夫曼树

哈夫曼树的构造

考点追踪：哈夫曼树的特性及构造（高频：2010、2012、2018、2019、2021、2023）

哈夫曼树相关的带权路径长度计算、结点数关系（双分支结点与叶结点的固定数学关系 $N=2n_0-1$）及路径上权值序列的合法性非常重要。

给定 n 个权值分别为 $w_1,\cdots ,w_n$ 的结点，构造哈夫曼树的算法描述如下：

1. 将这 n 个结点分别作为 n 棵仅含一个结点的二叉树，构成森林 F

2. 构造一个新结点，从 F 中取两棵根结点权重最小的树，合并在一起，根结点的权重是这两个权重的和

3. 从 F 中删除刚刚选出的两棵树，并加入它们的合并树

4. 重复 2、3 步骤，直至 F 中只剩下一棵树为止

从上述构造过程中可以看出哈夫曼树具有以下特点：

1. 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大

2. 构造过程中共新建了 n - 1 个结点，因此哈夫曼树的结点总数为 2n - 1，n 是叶结点的数量

3. 每次构造都选择 2 棵树作为新结点的孩子，因此哈夫曼树中不存在度为 1 的结点

哈夫曼编码

考点追踪：哈夫曼编码与定长编码的区别及译码（2017、2022）

考试常将哈夫曼变长编码和定长编码进行对比。同时须熟练前缀码的设计和由 0/1 序列逆向译码的过程。

在数据通信中，对每个字符用相等长度的二进制位表示，则称为固定长度编码；若对不同字符用不等长的二进制位表示，则称为可变长度编码

可变长度编码的特点是，对频率高的字符赋以短编码，对频率低的字符赋以较长一点的编码，从而缩短字符的平均编码长度，起到压缩数据的作用

若没有一个编码是另一个编码的前缀，那么称这样的编码为前缀编码，如 {0, 00} 不是前缀码，{0, 10} 是前缀码

前缀编码的解码：因为没有一个编码是其他编码的前缀，解码时只需识别每一个编码，将它翻译成原码

哈夫曼编码的构造：

1. 将每个出现的字符作为哈夫曼树的结点，其权值为字符出现的频率

2. 拿这些字符结点构成一棵哈夫曼树

3. 将哈夫曼树的左边标记 0，右边标记 1

4. 每个字符的编码就是哈夫曼树的根到它所经过边的标记的集合

注意：0 和 1 是左边还是右边没有明确规定，且左右结点的顺序是任意的，所有构造出的哈夫曼树不唯一，但每个哈夫曼树的 WPL 相同且为最优

核心结论：哈夫曼树的“必杀”考点（2021、2023、2025）

1. 结点数：若有 $n$ 个权值（叶子），则总结点数为 $2n-1$，非叶结点数为 $n-1$。

2. 度数：哈夫曼树只有度为 0 和 2 的结点，没有度为 1 的结点。

3. WPL 计算：$WPL=\sum (\mathrm{叶}\mathrm{子}\mathrm{权}\mathrm{值}\times \mathrm{路}\mathrm{径}\mathrm{长}\mathrm{度})$。

4. 前缀性：哈夫曼编码是前缀码，任何编码都不是其他编码的前缀。

5. 层级：权值越小的结点，离根越远（层级越深）。

综合应用题

检验是否为二叉排序树

题目：试编写一个算法，判断给定的二叉树是否为二叉排序树

思路：利用二叉排序树的中序会大于它的前驱，只要存储前驱的变量就好了

int pre = 0x80000000;



int JudgeBST(BiTree bt) {

    if (bt == NULL)

        return 1;

    if (JudgeBST(bt -> lchild) == 0 || pre >= bt -> data)

        return 0;

    pre = bt -> data;

    return JudgeBST(bt -> rchild);

}

最小代价合并多个有序表

问题：设有 6 个有序表 A，B，C，D，E，F，分别含有 10，35，40，50，60，200 个数据元素，各表中的元素按升序排序。要求通过 5 次两两合并，将 6 个表最终合并为 1 个升序表，并使最坏情况下比较的总次数达到最小

思路：先合并的表中元素在后序的每次合并中都会再次参与比较，因此求最小合并次数类似于求最小带权路径长度，所以就考虑使用哈夫曼树进行运算

求最坏情况下的比较次数，利用两个有序表合并的最坏情况需要比较 m + n - 1 次来求

注意

二叉树是极其重要的考点，关于二叉树的有关操作，出现了树的算法设计题

遍历时各种操作的基础，统考时会考查遍历过程对结点的各种操作

需要重点掌握各种遍历方法的手写，如递归算法和利用栈或队列的非递归算法