树与二叉树

【考纲内容】

树的基本概念
二叉树的定义及其主要特征
二叉树的顺序存储结构和链式存储结构
二叉树的遍历
线索二叉树的基本概念和构造
树的存储结构
森林与二叉树的转换
树和森林的遍历
二叉排序树
平衡二叉树
哈夫曼树和哈夫曼编码

【知识框架】

TODO 完成树与二叉树章节的知识框架

【复习提示】

本章内容多以选择题的形式考查，但也会出涉及树遍历相关的算法题。树和二叉树的性质、遍历操作、转换、存储结构和操作特性等，满二叉树、完全二叉树、线索二叉树、哈夫曼树的定义和性质，二叉排序树和二叉平衡树的性质和操作等，都是选择题必然会涉及的内容。

树的基本概念

树的定义

树是 $n \ (n\ge 0)$ 个节点的有限集。当 $n=0$ 时，称为空树。在任意一颗非空树中应满足：

有且仅有一个特定的称为根的结点。
当 $n>1$ 时，其余节点可分为 $m\ (m>0)$ 个互不相交的有限集 $T_1,T_2,\dots ,T_m$，其中每个集合本身又是一棵树，并称为根的子树。

显然，树的定义是递归的，即在树的定义中又用到了其自身，树是一种递归的数据结构。树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：

树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。
树中所有结点可以有零个或多个后继。

树适合于表示具有层次结构的数据。树中的某个结点（除根结点外）最多只和上一层的一个结点（即其父结点）有直接关系，根结点没有直接上层结点，因此在 $n$ 个结点的树中有 $n-1$ 条边。而树中每个结点与其下一层的零个或多个结点（即其子女结点）有直接关系。

基本术语

树的树形表示

考虑结点 K 。根 A 到结点 K 的唯一路径上的任意结点，称为结点 K 的祖先。如结点 B 是结点 K 的祖先，而结点 K 是结点 B 的子孙。路径上最接近结点 K 的结点 E 称为 K 的双亲，而 K 为结点 E 的孩子。根 A 是树中唯一没有双亲的结点。有相同双亲的结点称为兄弟，如结点 K 和结点 L 有相同的双亲 E，即 K 和 L 为兄弟。
树中一个结点的孩子个数称为该结点的度，树中结点的最大度数称为树的度。如结点 B 的度为 2，结点 D 的度为 3，树的度为 3。
度大于 0 的结点称为分支结点（又称非终端结点）；度为 0 （没有子女结点）的结点称为叶子结点（又称终端结点）。在分支结点中，每个结点的分支数就是该结点的度。
结点的层次从树根开始定义，根结点为第 1 层，它的子结点为第 2 层，以此类推。双亲在同一层的结点互为堂兄弟，图中结点 G 与 E，F，H，I，J 互为堂兄弟。
结点的深度是从根结点开始自顶向下逐层累加的。
结点的高度是从叶结点开始自底向上逐层累加的。
树的高度（或深度）是树中结点的最大层数。图中树的高度为4。
有序树和无序树。树中结点的各子树从左到右是有次序的，不能互换，称该树为有序树，否则称为无序树。假设图为有序树，若将子结点位置互换，则变成一棵不同的树。
路径和路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。注意：由于树中的分支是有向的，即从双亲指向孩子，所以树中的路径是从上向下的，同一双亲的两个孩子之间不存在路径。
森林是 $m\ (m \ge 0)$ 棵互不相交的树的集合。森林的概念与树的概念十分相近，因为只要把树的根结点删去就成了森林。反之，只要给 $m$ 棵独立的树加上一个结点，并把这 $m$ 棵树作为该结点的子树，则森林就变成了树。

度为 $m$ 的树与 $m$ 叉树：前者表示树中各节点最少存在一个最大为 $m$ 度的结点，而 $m$ 叉树表示每个结点最多只能有 $m$ 个孩子的树

树的性质

树具有如下最基本的性质：

树中的结点数等于所有结点的度数加 1 。
度为 $m$ 的树中第 $i$ 层上至多有 $m^{i-1}$ 个结点 $(i\ge 1)$。
高度为 $h$ 的 $m$ 叉树至多有 $\frac{m^h-1}{m-1} $ 个结点。
具有 $n$ 个结点的 $m$ 叉树的最小高度为 $\left \lceil \log_{m}{(n(m-1)+1) } \right \rceil $。^[1]

二叉树的概念

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

二叉树的定义

二叉树是另一种树形结构，其特点是每个结点至多只有两棵子树（即二叉树中不存在度大于 2 的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。

与树相似，二叉树也以递归的形式定义。二叉树是 $n\ (n\ge 0)$个结点的有限集合：

或者为空二叉树，即 $n=0$ 。
或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

二叉树是有序树，若将其左、右子树颠倒，则成为另一棵不同的二叉树。即使树中结点只有一颗子树，也要区分它是左子树还是右子树。

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

度为 2 的树至少有 3 个结点，而二叉树可以为空。
度为 2 的有序树的孩子的左右次序是相对于另一孩子而言的，若某个结点只有一个孩子，则这个孩子就无须区分其左右次序，而二叉树无论其孩子数是否为 2，均需确定其左右次序，即二叉树的结点次序不是相对于另一结点而言，而是确定的。

几个特殊的二叉树

满二叉树。一棵高度为 $h$，且含有 $2^h-1$ 个结点的二叉树称为满二叉树，即树中的每层都含有最多的结点。满二叉树的叶子结点都集中在二叉树的最下一层，并且除叶子结点之外的每个结点度数均为 2 （不存在度为 1 的结点）。可以对满二叉树按层序编号：约定编号从根结点（根结点编号为 1 ）起，自上而下，自左向右。这样，每个结点对应一个编号，对于编号为 $i$ 的结点，若有双亲，则其双亲为 $\left \lfloor \frac{i}{2} \right \rfloor$，若有左孩子，则左孩子为 $2i$ ；若有右孩子，则右孩子为 $2i+1$。

完全二叉树。高度为 $h$、有 $n$ 个结点的二叉树，当且仅当其每个结点都与高度为 $h$ 的满二叉树中编号为 $1\sim n$ 的结点一一对应时，称为完全二叉树。就是对应相同高度的满二叉树缺失最下层最右边的一些连续叶子结点。其特点如下：

若 $ i \le \left \lfloor \frac{n}{2} \right \rfloor$，则结点 $i$ 为分支结点，否则为叶子结点。
叶子结点只可能在层次最大的两层上出现。对于最大层次中的叶子结点，都依次排列在该层最左边的位置上。
若有度为 1 的结点，则只可能有一个，且该结点只有左孩子而无右孩子（重要特征）。
按层序编号后，一旦出现某结点（编号为 $i$ ）为叶子结点或只有左孩子，则编号大于 $i$ 的结点均为叶子结点。
若 $n$ 为奇数，则每个分支结点都有左孩子和右孩子；若 $n$ 为偶数，则编号最大的分支结点（编号为 $\frac{n}{2}$ ）只有左孩子，没有右孩子，其余分支结点左、右孩子都有。

二叉排序树。一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：

左子树上所有结点的关键字均小于根结点的关键字；
右子树上的所有结点的关键字均大于根结点的关键字；
左子树和右子树又各是一棵二叉排序树。

平衡二叉树。树上任一结点的左子树和右子树的深度之差不超过 1 。

二叉树的性质

（1）非空二叉树上的叶子结点数等于度为 2 的结点数加 1，即 $n_{0}=n_{2}+1$ 。

证明：设度为 0，1 和 2 的结点个数分别为 $n_{0}$，$n_{1}$ 和 $n_{2}$，结点总数 $n=n_{0}+n_{1}+n_{2}$。再看二叉树中的分支树，除根结点外，其余结点都有一个分支进入，设 $B$ 为分支总数，则 $n=B+1$ 。由于这些分支是由度为 1 或 2 的结点射出的，所以又有 $B=n_{1}+2n_{2}$。于是得 $n_{0}+n_{1}+n_{2}=n_{1}+2n_{2}+1$ ，则 $n_{0}=n_{2}+1$。

拓展到任意一棵树，若结点数量为 $n$，则边的数量为 $n-1$。

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

（3）高度为 $h$ 的二叉树至多有 $2^h-1$ 个结点（ $h \ge 1$ ）。高度为 $h$ 的 $m$ 叉树至多有 $\frac{m^h-1}{m-1} $ 个结点，推出。

（4）具有 $n$ 个（$n>0$）结点的完全二叉树的高度 $h$ 为 $\left \lceil \log_{2}{(n+1)} \right \rceil $ 或 $\left \lfloor \log_{2}{n} \right \rfloor +1$

证明：高度为 $h$ 的满二叉树共有 $2^h-1$ 个结点，高度为 $h-1$ 的满二叉树共有 $2^{h-1}-1$ 个结点，可得：$$2^{h-1}-1<n\le 2^{h}-1$$ $$2^{h-1}<n+1\le 2^{h}$$ $$h-1<\log{2}{(n+1)} \le h$$ $$h=\left \lceil \log_{2}{(n+1)} \right \rceil $$

高度为 $h-1$ 的满二叉树共有 $2^{h-1}-1$ 个结点，高为 $h$ 的完全二叉树至少有 $2^{h-1}$ 个结点，至多有 $2^{h}-1$ 个结点，可得：$$2^{h-1} \le n < 2^{h}$$ $$h-1 \le \log{2}{n} < h$$ $$h= \left \lfloor \log_{2}{n} \right \rfloor +1$$

（5）对于完全二叉树，可以由的结点数 $n$ 推出度为 0、1 和 2 的结点个数为 $n_0$、$n_1$和 $n_2$。

完全二叉树最多只有一个度为 1 1 的结点，即：$n_{1}=0或1$ ；
$n_{0}=n_{2}+1$，两边各加上 $n_2$ 可得： $n_0+n_2=2n_2+1$ 可推出 $n_0+n_2$ 一定为奇数；

根据上两个推论得：

若完全二叉树有 $2k$ （偶数）个结点，则必有 $n_1=1,\ n_0=k , \ n_2=k-1$
若完全二叉树有 $2k-1$ （奇数）个结点，则必有 $n_1=0,\ n_0=k , \ n_2=k-1$

二叉树的存储结构

顺序存储结构

二叉树的顺序存储是指用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为 $i$ 的结点元素存储在一维数组下标为 $i-1$ 的分量中。（这种存储结构建议从数组下标 1 开始存储树中的结点）

#define MaxSize 100
struct TreeNode {
    int value;
    bool isEmpty;
};

void InitTree() {
    TreeNode t[MaxSize];
    for (int i = 0; i < MaxSize; i++) {
        t[i].isEmpty = true;
    }
}

依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映结点之间的逻辑关系，这样既能最大可能地节省存储空间，又能利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。

但对于一般的二叉树，为了让数组下标能反映二叉树中结点之间的逻辑关系，只能添加一些并不存在的空结点，让其每个结点与完全二叉树上的结点相对照，再存储到一维数组的相应分量中。然而，在最坏情况下，一个高度为 $h$ 且只有 $h$ 个结点的单支树却需要占据近 $2^h-1$ 个存储单元。

链式存储结构

由于顺序存储的空间利用率较低，因此二叉树一般都采用链式存储结构，用链表结点来存储二叉树中的每个结点。在二叉树中，结点结构通常包括若干数据域和若干指针域，二叉链表至少包含3个域：数据域 data、左指针域 lchild 和右指针域 rchild。$n$ 个节点的二叉链表共有 $n+1$ 个空链域。

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;  // 左右孩子指针
    // struct BiTNode *parent;  // 根据实际需求决定是否加父指针
} BiTNode, *BiTree;

int main() {
    // 定义一棵空树
    BiTree root = nullptr;

    // 插入根节点
    root = (BiTree)malloc(sizeof(BiTNode));
    root->data = {1};
    root->lchild = nullptr;
    root->rchild = nullptr;

    // 插入新结点
    BiTNode *p = (BiTNode *)malloc(sizeof(BiTNode));
    p->data = {2};
    p->lchild = nullptr;
    p->rchild = nullptr;
    root->lchild = p;
}

找到指定结点的左右孩子结点十分容易，但如果要寻找父节点只能从根结点开始遍历寻找。可以在结构体中额外定义父节点指针（三叉链表）。

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

二叉树的遍历

二叉树的遍历是指按某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。由于二叉树是一种非线性结构，每个结点都可能有两棵子树，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，进而便于遍历。

由二叉树的递归定义可知，遍历一棵二叉树便要决定对根结点 N、左子树 L 和右子树 R 的访问顺序。按照先遍历左子树再遍历右子树的原则，常见的遍历次序有先序（NLR）、中序（LNR）和后序（LRN）三种遍历算法，其中“序”指的是根结点在何时被访问。

先序遍历

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

若二叉树为空，则什么也不做；否则，

访问根结点；
先序遍历左子树；
先序遍历右子树。

对应的递归算法如下:

void PreOrder(BiTree T) {
    if (T != nullptr) {
        visit(T);             // 访问根节点
        PreOrder(T->lchild);  // 递归遍历左子树
        PreOrder(T->rchild);  // 递归遍历右子树
    }
}

中序遍历

中序遍历（ InOrder ）的操作过程如下：

若二叉树为空，则什么也不做；否则，

中序遍历左子树；
访问根结点；
中序遍历右子树。

对应的递归算法如下：

void InOrder(BiTree T) {
    if (T != nullptr) {
        InOrder(T->lchild);  // 递归遍历左子树
        visit(T);            // 访问根节点
        InOrder(T->rchild);  // 递归遍历右子树
    }
}

后序遍历

后序遍历（ PostOrder ）的操作过程如下：

若二叉树为空，则什么也不做；否则，

后序遍历左子树；
后序遍历右子树；
访问根结点。

对应的递归算法如下：

void PostOrder(BiTree T) {
    if (T != nullptr) {
        PostOrder(T->lchild);  // 递归遍历左子树
        PostOrder(T->rchild);  // 递归遍历右子树
        visit(T);              // 访问根节点
    }
}

三种遍历算法中，递归遍历左、右子树的顺序都是固定的，只是访问根结点的顺序不同。不管采用哪种遍历算法，每个结点都访问一次且仅访问一次，故时间复杂度都是 $O(n)$ 。在递归遍历中，递归工作栈的栈深恰好为树的深度，所以在最坏情况下，二叉树是有 $n$ 个结点且深度为 $n$ 的单支树，遍历算法的空间复杂度为 $O(n)$。

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

层次遍历

要进行层次遍历，需要借助一个队列。先将二叉树根结点入队，然后出队，访问出队结点，若它有左子树，则将左子树根结点入队；若它有右子树，则将右子树根结点入队。然后出队，访问出队结点…如此反复，直至队列为空。

二叉树的层次遍历算法如下：

void LevelOrder(BiTree T) {
    LinkQueue Q;
    InirQueue(Q);  // 初始化辅助队列
    BiTree p;
    EnQueue(Q, T);  // 将根结点入队
    while (!isEmpty(Q)) {
        DeQueue(Q, p);  // 对头结点出队
        visit(p);       // 访问出队结点
        if (p->lchild != nullptr) {
            EnQueue(Q, p->lchild);  // 左孩子入队,入队指针
        }
        if (p->rchild != nullptr) {
            EnQueue(Q, p->rchild);  // 右孩子入队
        }
    }
}

由遍历序列构造二又树

若只给出一棵二叉树的前/中/后/层序遍历序列中的一种，不能唯一确定一棵二叉树。必须有中序遍历和其他任意一种遍历序列才能确定唯一一种二叉树。

先序序列和中序序列：在先序遍历序列中，第一个结点一定是二叉树的根结点；而在中序遍历中，根结点必然将中序序列分割成两个子序列，前一个子序列是根结点的左子树的中序序列，后一个子序列是根结点的右子树的中序序列。根据这两个子序列，在先序序列中找到对应的左子序列和右子序列。在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点。如此递归地进行下去，便能唯一地确定这棵二叉树。

类似，由二叉树的后序序列和中序序列，层序序列和中序序列也可以唯一地确定一棵二叉树。找到树的根节点，并根据
中序序列划分左右子树，再找至左右子树根节点。

线索二叉树

线索二叉树的基本概念

遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到几种遍历序列，使得该序列中的每个结点（第一个和最后一个结点除外）都有一个直接前驱和直接后继。

传统的二叉链表存储仅能体现一种父子关系，不能直接得到结点在遍历中的前驱或后继。前面提到，在含 $n$ 个结点的二叉树中，有 $n+1$ 个空指针。这是因为每个叶结点有 2 个空指针，每个度为 1 的结点有 1 个空指针，空指针总数为 $2n_{0} + n_1$ ，又 $n_{0}=n_{2}+ 1$，所以空指针总数为 $n_0+n_1+n_2+1=n+1$ 。由此设想能否利用这些空指针来存放指向其前驱或后继的指针？这样就可以像遍历单链表那样方便地遍历二叉树。引入线索二叉树正是为了加快查找结点前驱和后继的速度。

规定：若无左子树，令 lchild 指向其前驱结点；若无右子树，令 rchild 指向其后继结点。还需增加两个标志域（ltag、rtag）标识指针域是指向左（右）孩子还是指向前驱（后继）。当 tag 值等于 0 时，表示指针指向孩子，等于 1 时，表示指针指向线索。

中序线索二叉树

线索二叉树的存储结构描述如下：

typedef struct ThreadNode {
    int data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;  // 左右线索标志，0指向孩子，1指向线索
} ThreadNode, *ThreadTree;

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

中序线索二叉树的构造

// 全局遍历 pre 指向当前访问结点的前驱
ThreadNode *pre = nullptr;

// 中序遍历二叉树并进行线索化
void InThread(ThreadTree T) {
    if (T != nullptr) {
        InThread(T->lchild);  // 中序遍历左子树
        visit(T);             // 访问根节点并线索化
        InThread(T->rchild);  // 中序遍历右子树
    }
}

void visit(ThreadNode *q) {
    if (q->lchild == nullptr) {  // 左子树为空，建立前驱线索
        q->lchild = pre;
        q->ltag = 1;
    }
    if (pre != nullptr && pre->rchild == nullptr) {
        pre->rchild = q;  // 建立前驱结点的后继线索
        pre->rtag = 1;
    }
    pre = q;  // 将 pre 指针指向当前结点（即下一个访问结点的前驱结点）
}

// 中序线索化二叉树
void CreateInThread(ThreadTree T) {
    pre = nullptr;
    if (T != nullptr) {
        InThread(T);  // 中序线索化除最后一个结点的其他结点
        if (pre->rchild == nullptr) {
            pre->rtag = 1;  // 注意：处理最后一个结点
        }
    }
}

先序线索二叉树的构造

当 ltag == 0 时，才能对左子树先序线索化

// 全局遍历 pre 指向当前访问结点的前驱
ThreadNode *pre = nullptr;

// 先序遍历二叉树并进行线索化
void PreThread(ThreadTree T) {
    if (T != nullptr) {
        visit(T);                  // 访问根节点并线索化
        if (T->ltag == 0) {        // 注意：需要判断lchild不是前驱线索
            PreThread(T->lchild);  // 先序遍历左子树
        }
        PreThread(T->rchild);  // 先序遍历右子树
    }
}

void visit(ThreadNode *q) {
    if (q->lchild == nullptr) {  // 左子树为空，建立前驱线索
        q->lchild = pre;
        q->ltag = 1;
    }
    if (pre != nullptr && pre->rchild == nullptr) {
        pre->rchild = q;  // 建立前驱结点的后继线索
        pre->rtag = 1;
    }
    pre = q;  // 将 pre 指针指向当前结点（即下一个访问结点的前驱结点）
}

// 先序线索化二叉树
void CreateInThread(ThreadTree T) {
    pre = nullptr;
    if (T != nullptr) {
        PreThread(T);  // 先序线索化除最后一个结点的其他结点
        if (pre->rchild == nullptr) {
            pre->rtag = 1;  // 处理最后一个结点
        }
    }
}

后序线索二叉树的构造

// 全局遍历 pre 指向当前访问结点的前驱
ThreadNode *pre = nullptr;

// 后序遍历二叉树并进行线索化
void PostThread(ThreadTree T) {
    if (T != nullptr) {
        PostThread(T->lchild);  // 后序遍历左子树
        PostThread(T->rchild);  // 后序遍历右子树
        visit(T);               // 访问根节点并线索化
    }
}

void visit(ThreadNode *q) {
    if (q->lchild == nullptr) {  // 左子树为空，建立前驱线索
        q->lchild = pre;
        q->ltag = 1;
    }
    if (pre != nullptr && pre->rchild == nullptr) {
        pre->rchild = q;  // 建立前驱结点的后继线索
        pre->rtag = 1;
    }
    pre = q;  // 将 pre 指针指向当前结点（即下一个访问结点的前驱结点）
}

// 后序线索化二叉树
void CreateInThread(ThreadTree T) {
    pre = nullptr;
    if (T != nullptr) {
        PostThread(T);  // 后序线索化除最后一个结点的其他结点
        if (pre->rchild == nullptr) {
            pre->rtag = 1;  // 注意：处理最后一个结点
        }
    }
}

线索二叉树的遍历

在中序线索二叉树中找到指定结点 *p 的中序后继 next：

若 p->rtag == 1，则 next = p->rchild
若 p->rtag == 0，则 next 等于 p 的右子树中最左下的结点

// 找到以 p 为根的子树中，第一个被中序遍历的结点
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);
    }else { // rtag==1 直接返回后继线索
        return p->rchild; 
    }
}

// 对中序线索二叉树进行中序遍历
// 利用线索实现的非递归算法 空间复杂度 O(1)
void InOrder(ThreadNode *T){
    for(ThreadNode *p = FirstNode(T);p != nullptr;p = NextNode(p)){
        visit(p);
    }
}

在中序线索二叉树中找到指定结点 *p 的中序前驱 pre：

若 p->ltag == 1，则 pre = p->lchild
若 p->ltag == 0，则 pre 等于 p 的左子树中最右下的结点

// 找到以 p 为根的子树中，最后一个被中序遍历的结点
ThreadNode *LastNode(ThreadNode *p){
    // 循环找到最右下结点(不一定是叶结点)
    while(p->rtag == 0){
        p = p->rchild;
    }
    return p;
}

// 在中序线索二叉树中找到结点 p 的前驱结点
ThreadNode *PreNode(ThreadNode *p){
    // 左子树中最右下结点
    if(p->ltag == 0){
        return LastNode(p->lchild);
    }else { // ltag==1 直接返回前驱线索
        return p->lchild; 
    }
}

// 对中序线索二叉树进行逆向中序遍历
void RevInOrder(ThreadNode *T){
    for(ThreadNode *p = LastNode(T);p != nullptr;p = PreNode(p)){
        visit(p);
    }
}

先序线索二叉树找指定结点 *p 的先序后继 next

若 p->rtag == 1，则 next = p->rchild；
若 p->rtag == 0，则 p 必有右孩子，分成两种情况考虑：
- 若 p 有左孩子则先序后继为左孩子；
- 若没有左孩子则先序后继为右孩子

TODO 代码实现先序线索二叉树的后继遍历

在先序线索二叉树中找到指定结点 *p 的先序前驱 pre

若 p->ltag == 1，则 next = p-> lchild；
若 p->ltag == 0，则 p 必有左孩子。二叉链表在先序遍历中，左右子树中的结点只可能是根的后继，不可能是前驱，故找不到先序前驱。三叉链表在先序遍历中，如果能找到 p 的父节点：
- p 为左孩子，p 的父节点即为其前驱结点；
- p 是右孩子，其左兄弟为空，p 的父节点即为其前驱结点；
- p 是右孩子，其左兄弟非空，p 的前驱为左兄弟子树中最后一个被先序遍历的结点；
- 如果 p 是根结点，则 p 没有先序前驱。

在后序线索二叉树找到指定结点 *p 的后序前驱 pre：

若 p->ltag == 1，则 pre = p->lchild
若 p->ltag == 0，则 p 必有左孩子，若 p 有右孩子，则后序前驱为右孩子；若 p 没有右孩子，则后序前驱为左孩子

TODO 后序前驱遍历代码实现

在后序线索二叉树中找到指定结点 *p 的后序后继 next：

若 p->rtag == 1，则 next = p->rchild
若 p->rtag == 0，则 p 必有右孩子。二叉链表在后序遍历中，左右子树中的结点只可能是根的前驱，不可能是后继。三叉链表在后序遍历中，如果能找到 p 的父节点：
- p 是右孩子，p 的父节点即为其后继结点；
- p 是左孩子，其右兄弟为空，p 的父节点即为其后继结点；
- p 是左孩子，其右兄弟非空，p 的后继为右兄弟子树中第一个被后序遍历的结点；
- 如果 p 是根节点，则 p 没有后继结点

树、森林

树的存储结构

树的存储方式有多种，既可采用顺序存储结构，又可采用链式存储结构，但无论采用何种存储方式，都要求能唯一地反映树中各结点之间的逻辑关系，这里介绍 3 种常用的存储结构。

双亲表示法（顺序存储）

这种存储方式采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。根结点下标为 0，其伪指针域为 -1。

树的双亲表示法

双亲表示法的存储结构描述如下：

#define MAX_TREE_SIZE 100
typedef struct {
    int data;     // 数据元素
    int partent;  // 双亲位置域
} PTNode;
typedef struct {
    PTNode nodoes[MAX_TREE_SIZE];  // 双亲表示
    int n;                         // 结点数
} PTree；

孩子表示法（顺序+链式存储）

孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时 $n$ 个结点就有 $n$ 个孩子链表（叶子结点的孩子链表为空表）。这种存储方式寻找子女的操作非常直接，而寻找双亲的操作需要遍历 $n$ 个结点中孩子链表指针域所指向的 $n$ 个孩子链表。

#define MAX_TREE_SIZE 100
struct CTNode {
    int child;            // 孩子结点在数组中的位置
    struct CTNode *next;  // 下一个孩子
};

typedef struct {
    int data;
    struct CTNode *firstChild;  // 第一个孩子
} CTBox;

typedef struct {
    CTBox nodes[MAX_TREE_SIZE];
    int n, r;  // 结点数和根的位置
} CTree;

孩子和孩子兄弟表示法

孩子兄弟表示法（链式存储）

孩子兄弟表示法又称二叉树表示法，即以二叉链表作为树的存储结构。孩子兄弟表示法使每个结点包括三部分内容：结点值、指向结点第一个孩子结点的指针，及指向结点下一个兄弟结点的指针（沿此域可以找到结点的所有兄弟结点）。

typedef struct CSNode {
    int data;
    struct CSNode *firstchild, *nextsibling;  // 第一个孩子和右兄弟指针
} CSNode, *CSTree;

这种存储表示法比较灵活，其最大的优点是可以方便地实现树转换为二叉树的操作，易于查找结点的孩子等，但缺点是从当前结点查找其双亲结点比较麻烦。若为每个结点增设一个 parent 域指向其父结点，则查找结点的父结点也很方便。

树、森林与二叉树的转换

由于二叉树和树都可以用二叉链表作为存储结构，因此以二叉链表作为媒介可以导出树与二叉树的一个对应关系，即给定一棵树，可以找到唯一的一棵二叉树与之对应。从物理结构上看，它们的二叉链表是相同的，只是解释不同而已。

树转换为二叉树的规则：每个结点左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟，这个规则又称“左孩子右兄弟”。由于根结点没有兄弟，所以对应的二叉树没有右子树。

树与二叉树的对应关系

树转换成二叉树的画法：

在兄弟结点之间加一连线；
对每个结点，只保留它与第一个孩子的连线，而与其他孩子的连线全部抹掉；
以树根为轴心，顺时针旋转45°。

将森林转换为二叉树的规则与树类似。先将森林中的每棵树转换为二叉树，由于任何一棵和树对应的二叉树的右子树必空，若把森林中第二棵树根视为第一棵树根的右兄弟，即将第二棵树对应的二叉树当作第一棵二叉树根的右子树，将第三棵树对应的二叉树当作第二棵二叉树根的右子…以此类推，就可以将森林转换为二叉树。

森林与二叉树的对应关系

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

将森林中的每棵树转换成相应的二叉树
每棵树的根也可视为兄弟关系，在每棵树的根之间加一根连线；
以第一棵树的根为轴心顺时针旋转45°。

二叉树转换为森林的规则：若二叉树非空，则二叉树的根及其左子树为第一棵树的二叉树形式，故将根的右链断开。二叉树根的右子树又可视为一个由除第一棵树外的森林转换后的二叉树，应用同样的方法，直到最后只剩一棵没有右子树的二叉树为止，最后再将每棵二叉树依次转换成树，就得到了原森林。二叉树转换为树或森林是唯一的。

树和森林的遍历

树的遍历是指用某种方式访问树中的每个结点，且仅访问一次。主要有两种方式（深度优先遍历）：

先根遍历。若树非空，先访问根结点，再依次遍历根结点的每棵子树，遍历子树时仍遵循先根后子树的规则。其遍历序列与这棵树相应二叉树的先序序列相同。
后根遍历。若树非空，先依次遍历根结点的每棵子树，再访问根结点，遍历子树时仍遵循先子树后根的规则。其遍历序列与这棵树相应二叉树的中序序列相同。

另外，树也有层次遍历（广度优先遍历），与二叉树的层次遍历思想基本相同，即按层序依次访问各结点。

按照森林和树相互递归的定义，可得到森林的两种遍历方法。

先序遍历森林。若森林为非空，则按如下规则进行遍历（效果等同于依次对各个树进行先根遍历）：
- 访问森林中第一棵树的根结点。
- 先序遍历第一棵树中根结点的子树森林。
- 先序遍历除去第一棵树之后剩余的树构成的森林。
中序遍历森林。森林为非空时，按如下规则进行遍历（效果等同于依次对各个树进行后根遍历）：
- 中序遍历森林中第一棵树的根结点的子树森林。
- 访问第一棵树的根结点。
- 中序遍历除去第一棵树之后剩余的树构成的森林。

树与二叉树的应用

二叉排序树（BST）

二叉排序树的定义

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

若左子树非空，则左子树上所有结点的值均小于根结点的值。
若右子树非空，则右子树上所有结点的值均大于根结点的值。
左、右子树也分别是一棵二叉排序树。

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

二叉排序树的查找

二叉排序树的查找是从根结点开始，沿某个分支逐层向下比较的过程。若二叉排序树非空，先将给定值与根结点的关键字比较，若相等，则查找成功；若不等，如果小于根结点的关键字，则在根结点的左子树上查找，否则在根结点的右子树上查找。这显然是一个递归的过程。

二叉排序树的非递归查找算法，最坏空间复杂度 $O(1)$ ：

// 二叉排序树的结点
typedef struct BSTNode {
    int key;
    struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;

// 在二叉排序树中查找值为 key 的结点
BSTNode *BST_Search(BSTree T, int key) {
    while (T != nullptr && key != T->key) {
        if (key < T->key) {
            T = T->lchild;  // 小于 在左子树上查找
        } else {
            T = T->rchild;  // 大于 在右子树上查找
        }
    }
    return T;
}

二叉排序树的递归查找算法实现，最坏空间复杂度 $O(h)$ ：

BSTNode *BST_Search(BSTree T, int key) {
    if (T == nullptr) {
        return nullptr;  // 查找失败
    }
    if (key == T->key) {
        return T;  // 查找成功
    } else if (key < T->key) {
        return BST_Search(T->lchild, key);  // 在左子树中查找
    } else {
        return BST_Search(T->rchild, key);  // 在右子树中找
    }
}

二叉排序树的插入

二叉排序树作为一种动态树表，其特点是树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字值等于给定值的结点时再进行插入的。

插入结点的过程如下：若原二叉排序树为空，则直接插入结点；否则，若关键字 key 小于根结点值，则插入到左子树，若关键字 key 大于根结点值，则插入到右子树。插入的结点一定是一个新添加的叶结点，且是查找失败时的查找路径上访问的最后一个结点的左孩子或右孩子。

二叉排序树插入操作的算法描述如下：

// 在二叉排序树插入关键字为 k 的新结点（递归实现）
int BST_Insert(BSTree &T, int k) {
    if (T == nullptr) {  // 树为空，新插入的结点为根结点
        T = (BSTree)malloc(sizeof(BSTNode));
        T->key = k;
        T->lchild = T->rchild = nullptr;
        return 1;
    } else if (k == T->key) {  // 树中存在相同关键字结点。插入失败
        return 0;
    } else if (k < T->key) {  // 插入到T的左子树
        return BST_Insert(T->lchild, k);
    } else {  // 插入到T的右子树
        return BST_Insert(T->rchild, k);
    }
}

TODO 实现二叉排序树插入操作的非递归实现

二叉排序树的构造

构造二叉排序树的算法描述如下：

void Creat_BST(BSTree &T, int str[], int n) {
    T = nullptr;  // 初始时T为空树
    int i = 0;
    while (i < n) { // 依次将每个关键字插入到二叉排序树中
        BST_Insert(T, str[i]);
    }
}

二叉排序树的删除

在二叉排序树中删除一个结点时，不能把以该结点为根的子树上的结点都删除，必须先把被删除结点从存储二叉排序树的链表上摘下，将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会丢失。删除操作的实现过程按 3 种情况来处理：

若被删除结点是叶结点，则直接删除，不会破坏二叉排序树的性质。
若结点 z 只有一棵左子树或右子树，则让 z 的子树成为 z 父结点的子树，替代 z 的位置。
若结点 z 有左、右两棵子树，则令 z 的直接后继（或直接前驱）替代 z，然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。

二叉排序树的查找效率分析

二叉排序树的查找效率，主要取决于树的高度。

若二叉排序树的左、右子树的高度之差的绝对值不超过 1，则这样的二叉排序树称为平衡二叉树，它的平均查找长度为 $O(\log_{2}{n})$ 。

若二叉排序树是一个只有右（左）孩子的单支树（类似于有序的单链表），则其平均查找长度为 $O(n)$。在最坏情况下，即构造二叉排序树的输入序列是有序的，则会形成一个倾斜的单支树，此时二叉排序树的性能显著变坏，树的高度也增加为元素个数 $n$ 。

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

平衡二叉树⭐

平衡二叉树的定义

为避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除二叉树结点时，要保证任意结点的左、右子树高度差的绝对值不超过 1，将这样的二叉树称为平衡二叉树（Balanced Binary Tree），简称平衡树（ AVL 树）。定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是 -1、0 或 1。

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

// 平衡二叉树结点
typedef struct AVLNode {
    int key;
    int balance;
    struct AVLNode *lchild, *rchild;
} AVLNode, *AVLTree;

平衡二叉树的插入

二叉排序树保证平衡的基本思想如下：每当在二叉排序树中插入（或删除）一个结点时，首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于 1 的结点 A，再对以 A 为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。

注意：每次调整的对象都是最小不平衡子树，即以插入路径上离插入结点最近的平衡因子的绝对值大于 1 的结点作为根的子树。

最小不平衡子树示意图

平衡二叉树的插入过程的前半部分与二叉排序树相同，但在新结点插入后，若造成查找路径上的某个结点不再平衡，则需要做出相应的调整。可将调整的规律归纳为下列 4 种情况：

LL 平衡旋转（右单旋转）。由于在结点 A 的左孩子（L）的左子树（L）上插入了新结点，A 的平衡因子由 1 增至 2，导致以 A 为根的子树失去平衡，需要一次向右的旋转操作。将 A 的左孩子 B 向右上旋转代替 A 成为根结点，将 A 结点向右下旋转成为 B 的右子树的根结点，而 B 的原右子树则作为 A 结点的左子树。如下图所示，其中结点旁的数值代表结点的平衡因子，而用方块表示相应结点的子树，下方数值代表该子树的高度。

LL平衡旋转

RR 平衡旋转（左单旋转）。由于在结点 A 的右孩子（ R ）的右子树（ R ）。上插入了新结点，A 的平衡因子由 -1 减至 -2，导致以 A 为根的子树失去平衡，需要一次向左的旋转操作。将 A 的右孩子 B 向左，上旋转代替 A 成为根结点，将 A 结点向左下旋转成为 B 的左子树的根结点，而 B 的原左子树则作为 A 结点的右子树。

RR平衡旋转

LR 平衡旋转（先左后右双旋转）。由于在 A 的左孩子（L）的右子树（R）。上插入新结点，A 的平衡因子由 1 增至 2，导致以 A 为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将 A 结点的左孩子 B 的右子树的根结点 C 向左上旋转提升到 B 结点的位置，然后再把该 C 结点向右上旋转提升到 A 结点的位置。

LR平衡旋转

RL 平衡旋转（先右后左双旋转）。由于在 A 的右孩子（R）的左子树（L）。上插入新结点，A 的平衡因子由 -1 减至 -2，导致以 A 为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将 A 结点的右孩子 B 的左子树的根结点 C 向右上旋转提升到 B 结点的位置，然后再把该 C 结点向左上旋转提升到 A 结点的位置。

RL平衡旋转

假设关键字序列为 {15, 3, 7, 10, 9, 8}，通过该序列生成平衡二叉树的过程如下图所示。(d) 插入 7 后导致不平衡，最小不平衡子树的根为 15，插入位置为其左孩子的右子树，故执行 LR 旋转，先左后右双旋转，调整后的结果如图 (e) 所示。图 (g) 插入 9 后导致不平衡，最小不平衡子树的根为 15，插入位置为其左孩子的左子树，故执行 LL 旋转，右单旋转，调整后的结果如图 (h) 所示。图 (i) 插入 8 后导致不平衡，最小不平衡子树的根为 7，插入位置为其右孩子的左子树，故执行 RL 旋转，先右后左双旋转，调整后的结果如图 (j) 所示。

平衡二叉树的生成过程

平衡二叉树的查找

在平衡二叉树上进行查找的过程与二叉排序树的相同。因此，在查找过程中，与给定值进行比较的关键字个数不超过树的深度。假设以 $n_h$ 表示深度为 $h$ 的平衡树中含有的最少结点数。显然，有 $n_0=0,n_1=1,n_2=2$ ，并且有 $n_h=n_{h-1}+n_{h-2}+1$ 。可以证明，含有 $n$ 个结点的平衡二叉树的最大深度为 $O(\log_{2}{n})$，因此平衡二叉树的平均查找长度为 $O(\log_{2}{n})$ 。

哈夫曼树和哈夫曼编码

哈夫曼树的定义

在许多应用中，树中结点常常被赋予一个表示某种意义的数值，称为该结点的权（如：表示结点的重要性）。

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

树中所有叶结点的带权路径长度之和称为该树的带权路径长度，记为 $$WPL=\sum_{i=1}^{n} w_il_i$$ 式中，$w_i$ 是第 $i$ 个叶结点所带的权值，$l_i$ 是该叶结点到根结点的路径长度。

在含有 $n$ 个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树。

哈夫曼树的构造

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

将这 $n$ 个结点分别作为 $n$ 棵仅含一个结点的二叉树，构成森林 $F$。
构造一个新结点，从 $F$ 中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
从 $F$ 中删除刚才选出的两棵树，同时将新得到的树加入 $F$ 中。
重复步骤 2 和 3，直至 $F$ 中只剩下一棵树为止。

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

每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。
构造过程中共新建了$n-1$个结点（双分支结点），因此哈夫曼树的结点总数为 $2n-1$ 。
每次构造都选择 2 棵树作为新结点的孩子，因此哈夫曼树中不存在度为 1 的结点。

哈夫曼编码

在数据通信中：

若对每个字符用相等长度的二进制位表示，称这种编码方式为固定长度编码。
若允许对不同字符用不等长的二进制位表示，则这种编码方式称为可变长度编码。

可变长度编码比固定长度编码要好得多，其特点是对频率高的字符赋以短编码，而对频率较低的字符则赋以较长一些的编码，从而可以使字符的平均编码长度减短，起到压缩数据的效果。哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码。

若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。举例:设计字符 A，B 和 C 对应的编码 0，101 和 100 是前缀编码。对前缀编码的解码很简单，因为没有一个编码是其他编码的前缀。所以识别出第一个编码，将它翻译为原码，再对余下的编码文件重复同样的解码操作。例如，码串 00101100 可被唯一地翻译为0，0，101 和 100。另举反例：如果再将字符 D 的编码设计为 00，此时 0 是 00 的前缀，那么这样的码串的前两位就无法唯一翻译。

由哈夫曼树得到哈夫曼编码是很自然的过程。首先，将每个出现的字符当作一个独立的结点，其权值为它出现的频度（或次数），构造出对应的哈夫曼树。显然，所有字符结点都出现在叶结点中。我们可将字符的编码解释为从根至该字符的路径上边标记的序列，其中边标记为 0 表示“转向左孩子”，标记为 1 表示“转向右孩子”。

注意：0 和 1 究竟是表示左子树还是右子树没有明确规定。左、右孩子结点的顺序是任意的，所以构造出的哈夫曼树并不唯一，但各哈夫曼树的带权路径长度 WPL 相同且为最优。此外，如有若干权值相同的结点，则构造出的哈夫曼树更可能不同，但 WPL 必然相同且是最优的。

推导过程：$$\frac{m^{h-1}-1}{m-1}<n\le \frac{m^h-1}{m-1}$$ $$m^{h-1}<n(m-1)+1\le m^h $$ $$ h-1 < \log_{m}{(n(m-1)+1)} \le h $$ $$h_{min}= \left \lceil \log_{m}{(n(m-1)+1) } \right \rceil $$ ↩︎