树

阿杰 like coding bug ❥约 6545 字大约 22 分钟

树的定义

定义：是n( $n \geq 0$ )个节点的有限集。当n = 0时，称为空树。在任意一颗非空树中应满足：
有且仅有一个特定的称为根的结点。
当n > 1时，其余节点可分为m(m > 0)个互不相交的树，并称其为子树。

根据上面树的定义可以知道：树是递归的，树中有包含树；树是一种逻辑结构和分层结构。

并且树的根节点是没有前驱的，除根节点外，其余所有节点有且仅有一个前驱（双亲），但是树中的每个节点可以有0个或多个后继（孩子）。

基本术语

我们需要知道关于树的一些专业术语。

祖先：使用D节点举例，A到D的唯一路径上除了D的所有的节点全为D的祖先节点。
子孙：一个节点下的所有子树上的节点都为其子孙，如：D、E、F为C的子孙。
双亲：根节点到该节点路径上离该节点最近的节点，如：C就为D的双亲，也为E、F的双亲。
孩子：和双亲类似，D、E、F都为C的孩子，只有根节点没有双亲。
兄弟：有相同双亲的节点称为兄弟节点。
堂兄弟：双亲在同一层的结点称为堂兄弟，如：C、G、I为堂兄弟。
节点的层次：如上面的图，根节点在第一层，往下层数依次增加。
节点的深度：就是节点的层次。
树的高度（深度）：树中节点的最大层数。
节点的高度：是以该节点为根节点的子树高度。
节点的度：有几个孩子节点，度就为多少。
树的度：树中节点的最大的度为树的度。
分支节点：度大于0的节点。
叶节点：度为0的节点。
有序树：树中节点的各子树从做到右是有次序的，不能互换。
无序树：就和上面相反呗，无序并可以相互交换（仅在有一个以上孩子节点时成立）。
路径：树中两个节点之间的路径是由这两个节点之间所经过的节点序列组成的。
路径长度：是整个路径上边的条数。

森林

定义：是m( $m \geq 0$ )颗互不相交的树的集合。

树和森林在现实生活中是包含关系。在数据结构中也很类似，给m颗树形成的森林加上一个节点，并把这m颗树作为该节点的子树，则森林就变为了树；而树去掉根节点又可以变为森林。

树的性质

在树中最重要的就是节点、度数、高度之间的关系了，所以我们来学习这些性质。

1. 树的节点数n等于所有节点的度数之和加一：所有的度数之和就是除了根节点之外所有节点之和，所以在此基础上加一就可以得到树的节点数n了。

2. 度为m的树中第i层上之多有 $m^{i - 1}$ 个节点(i $\geq 1$ )：因为条件是之多，故只要每个节点的度都为m，这样在在第i层的结点数就最多。

3. 高度为h的m叉树至多有 $\frac{m^h - 1}{m - 1}$ 个节点：根据等比数列的前n项和公式可以轻松得到这个结论。

4. 度为m、具有n个节点的树的最小高度h为 $[log_m(n(m - 1)) + 1]$ (注意是需要向上取整的)：因为要求是最小的高度，所以在最后一层之上的每个节点的度都要为m，设树的高度为h，前h - 1层最多有 $\frac{m^{h - 1}}{m - 1}$ 个节点，前n层最多有 $\frac{m^h}{m - 1}$ 个节点，并且要满足 $\frac{m^{h - 1}}{m - 1} < n \leq \frac{m^h}{m - 1}$ ，根据这个不等式可得最终结果。

5. 度为m、具有n个节点的树的最大高度h为 $n - m + 1$ ：条件为h最高，则满足在上部分为两两节点连接，只在两两节点相连的最后一个节点实现度为m。

树的存储结构

树的存储可以采用顺序存储结构也可以采用链式存储结构。但无论采用的是什么结构，都要能唯一地反映树中各个节点之间的逻辑关系。（哪个节点是哪个节点的双亲，哪个节点是哪个节点的孩子）

我们学习三种表示方式：

1. 双亲表示法

这种表示的方法整体上是采用的顺序存储，但补充了一些细节。顺序存储中的每个节点中增加一个伪指针parent，用于指向双亲在数组中的索引，根节点的伪指针指向-1则可。

显而易见的，这种方式可以轻松地获取到双亲节点，但要获取孩子节点就不容易了，需要遍历整个数组才能得到。（要找双亲节点索引为2的节点就得遍历整个数组去找伪指针为2的节点）。

节点C语言结构体表示为：

#define MAX_SIZE 100
//声明节点结构
typedef struct PTreeNode{
    int data;
    int parent;
}PTreeNode;
//一棵树
typedef struct PTree{
    PTreeNode nodes[MAX_SIZE];
    int num; //树中节点的个数
}PTree;

2. 孩子表示法

在整体上采用的是链式存储结构（单链表），一颗树有n个节点那么这个单链表就会有n个孩子链表。每个孩子链表的头指针一起组成了一个线性表，为了便于查找，这些头指针采用顺序存储结构。

每条孩子链表中节点都为顺序表中对应节点在树中的孩子节点。

这个虽然可以很好地获取到孩子节点，但是找双亲就困难了，需要遍历所有节点中的链表。

C语言定义结构体为（我直接定义数据类型为int）：

// 定义孩子节点的结构体
typedef struct ChildNode {
    int childIndex;                // 孩子节点的索引
    struct ChildNode* next;        // 指向下一个孩子节点的指针
} ChildNode;

// 定义树节点的结构体
typedef struct TreeNode {
    int data;                      // 节点的数据
    ChildNode* children;           // 指向孩子链表的头指针
} TreeNode;

// 定义树的结构体
typedef struct Tree {
    TreeNode* nodes;               // 节点数组
    int size;                      // 节点总数
} Tree;

3. 孩子兄弟表示法

这个方法又可以被称为二叉树表示法，因为其可以将树转换为二叉链表树。每个节点包含3个值，分别为指向孩子的指针、节点值、指向下一个兄弟的指针。

这样转化的二叉树中的一个非叶子节点A的左孩子B就为在原树中A的第一个孩子B，二叉树中B的右孩子就为原树B的相邻右兄弟，以此类推。这就是所谓的左孩子右兄弟。

此方法最大的优点就是可以方便地将树转换为二叉树，轻松地得到节点的孩子，但是不容易查找到当前节点的双亲，解决方式也很简单，增加一个parent指针指向双亲则可。

C语言表示的结构体为：

typedef struct CSNode{
    int data;
    struct CSNode *firstchild, *nextsibling;
}CSNode;

树、森林和二叉树的相互转换

树转换为二叉树就是使用上面的二叉树表示法则可。需要注意的是根节点没有兄弟故没有右孩子（也就是转换后的二叉树没有右子树）。

一些画法我觉得没什么用，只要清晰地理解了这个原理便可轻松地画出。

森林转换为二叉树和上面的树转换类似，因为森林就是多棵树嘛！那具体怎样转化呢？

森林中的树的根节点相互视为兄弟节点。将每颗树单独的转换为二叉树，然后从第二颗树开始依次作为前一棵树根节点的右孩子则可。

二叉树转换为森林上面的逆运算，将一颗二叉树分离为多颗二叉树，再使用左孩子右兄弟的原理得到每颗二叉树对应的树，这些树就构成了最终的森林。

掌握好基本概念是容易理解和作图的，以下是示意图：

树和森林的遍历

树的遍历可以分为先根遍历、后根遍历、层序遍历，这和二叉树的遍历有所不同，因为树可以有多个孩子，所以无法使用中根遍历。

先根遍历

若树非空，则先访问根节点，在依次先根遍历根节点的每颗子树。其遍历序列和这颗树对应二叉树的先序序列相同。

后根遍历

若树非空，则依次后根遍历根节点的每颗子树。其遍历序列和这颗树对应二叉树的中序序列相同。 有时也称后根遍历为中序遍历，这是对于树对应的二叉树而言的。

层序遍历

若树非空，按层序依次访问每个节点，和二叉树的层序遍历思想类似（使用一个辅助队列）。

二叉树的定义

定义：是一种特殊的树形结构。

其每个节点至多只有两颗子树，并且二叉树的子树有左右之分，其次序是不能进行交换的。

因为二叉树也是树的一种，所以在许多地方的性质都是树性质的特殊化。

二叉树和有序树的区别

度为2的树至少要3个节点，而二叉树可以为空。
度为2的有序树的孩子的左右次序是相对的，如果该有序树的孩子节点只有一个则不用分左右，但是二叉树中的节点就算只有一个孩子节点都要区分是左还是右。

几种特殊的二叉树

满二叉树（FBT）：一颗高为h的二叉树，节点数有 $2^{n} - 1$ ，则称其为满二叉树，将树装“满”了。

完全二叉树（CBT）：高度为h、有n个节点的二叉树，并且每个节点都与高度为h的满二叉树中编号一一对应时，称其为完全二叉树。也就是说完全二叉树是满二叉树在叶子节点那一层减少一些右侧连续的节点。

二叉排序树（BST）：左子树上的所有节点全部都小于根节点的值；右子树的所有节点全部都大于根节点的值；左右子树又分别为一颗二叉排序树。

平衡二叉树（AVL）：树中的任意一个节点的左子树和右子树的高度只差的绝对值不超过1。

正则二叉树（RBT）：树中的每个分支节点都有两个节点，也就是说树中节点的度只有0和2两种。

二叉树的性质

二叉树的性质就是树性质一种特殊化。

非空二叉树上的叶节点数等于度为2的节点数加1，即 $n_0 = n_2 + 1$ 。
非空二叉树的第k层最多有 $2^k - 1$ 个节点。
高度为h的二叉树最多有 $2^h - 1$ 个节点。
将完全二叉树按从上到下，从左至右的顺序依次编号1,2,3,4...,n。则有以下特性：

最后一个分支节点编号为[ $\frac {n}{2}$ ]，若 $i \leq [\frac {n}{2}]$ 则为分支节点，否则为叶子节点。
叶子节点只可以出现在最底层或者倒数第二层。
若有度为1的节点，该类节点只能有一个，并且该节点只能是左孩子。
编号之后，若出现编号i的节点为叶子节点或只有左孩子，则编号大于i的节点均为叶子节点。
若n为奇数，则每个分支节点都有左、右孩子；若n为偶数，则编号最大的分支节点（i= $\frac {n}{2}$ ）只有左孩子，其余分支节点都有左、右孩子。
当i>1时，节点i的双亲节点编号为[ $\frac {n}{2}$ ]。
若节点i有左、右孩子，则左孩子编号为2i，右孩子编号为2i + 1。
节点i所在层次为[ $log_2i$ ] + 1。

具有n（n > 0）个节点的完全二叉树的高度为[ $log_2(n + 1)$ ]（向上取整）或[ $log_2(n)$ ] + 1。

二叉树的存储结构

顺序存储结构

可以将完全二叉树从左到右每个节点进行编号。但是这里有个问题，对于完全二叉树和满二叉树可以将每个存储单元利用起来，如果是普通的二叉树，则要注意在某些没有节点的位置上补0，这样是很浪费存储空间的。

链式存储结构

二叉树一般都采用链式存储结构，使用链表节点来存储二叉树中的每一个节点。一个节点包括 左指针域、值、右指针域。

使用C语言表示的结构体为：

typedef struct TreeNode{
    struct TreeNode *lchild;
    int data;
    struct TreeNode *rchild;
}TreeNode;

其中的左右指针分别指向孩子节点地址；我们可以看到二叉树有n个节点的话，则会有2n个域，其中只有n - 1个域用于指向孩子节点，会有n + 1个空域。而这个空域在后面就是用于存放 “线索” 的。

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

二叉树的遍历

定义：按某条搜索路径访问树中每个节点，使得每个节点有且仅被访问一次。

由二叉树的递归定义，我们可以知道通过递归的手段对二叉树遍历是非常容易的。

进行递归遍历时，就有不同的选择了，我们以根被访问的次序可以将递归遍历分为：NLR、LNR、LRM。（分别为先序遍历、中序遍历、后序遍历）

四种遍历方式

先序遍历
判断二叉树是否为空，为空什么都不做，否则：

访问根节点
先序遍历左子树
先序遍历右子树

C语言代码实现：

void preOrder(TreeNode *root){
    if(root == NULL){
        return ;
    }
    printf("%d ", root->data);
    preOrder(root->lchild);
    preOrder(root->rchild);
}

中序遍历
判断二叉树是否为空，为空什么都不做，否则：

中序遍历左子树
访问根节点
中序遍历右子树

C语言代码实现：

void inOrder(TreeNode *root){
    if(root == NULL){
        return ;
    }
    inOrder(root->lchild);
    printf("%d ", root->data);
    inOrder(root->rchild);
}

后序遍历
判断二叉树是否为空，为空什么都不做，否则：

后序遍历左子树
后序遍历右子树
访问根节点

C语言代码实现：

void postOrder(TreeNode *root){
    if(root == NULL){
        return ;
    }
    postOrder(root->lchild);
    postOrder(root->rchild);
    printf("%d ", root->data);
}

除了递归遍历外，还有层序遍历，一层一层的遍历，也就是之前在队列应用那说的方法。忘记了可以点击队列在层序遍历中的应用进行复习。

C语言代码实现：

void levelOrder(TreeNode *root){
    Queue *queue = initQueue();
    TreeNode *node;
    //将根节点入队
    inQueue(queue, root);
    //核心操作
    whille(!isEmpty(queue)){
        deQueue(queue, node);
        printf("%d ", node->data);
        if(node->lchild != NULL){
            inQueue(queue, node->lchild);
        }
        if(node->rchild != NULL){
            inQueue(queue, node->rchild);
        }
    }
}

遍历构造二叉树

如果给出一个中序序列和任意一个其他序列则可以得出唯一的二叉树结构。但是如果两个序列中没有中序序列就不能确定唯一结构了。

思路都是类似的，举个例子：前序序列为：ABDECF，中序序列为：DBEACF

我们可以进行分析：

前序序列是以A开头的，说明二叉树的根节点为A，然后在中序序列中可以得到左子树有DBE，右子树有CF。

然后分析左子树，在前序序列中B在前则说明其作为子树的根，再根据中序序列知道D、E分别为左右孩子节点。

最后分析右子树，在前序序列中C在前显然为子树的根，根据中序序列可知F为右孩子。故可得最后的二叉树结构：

带有中序序列和其他任意序列的分析都如上。需要注意的是在不带中序序列的任意两个序列的分析。

线索二叉树

采用一种序列方式遍历二叉树可以得到一种遍历序列，该序列是一种线性序列，故可以使得除第一个和最后一个节点外都有一个直接前驱和直接后继节点。

但是传统的二叉链表只能表示父子关系，而不能表示前驱和后继关系。为了实现这个目的，可以将二叉树中的还剩余的n + 1个空链域利用起来。这样就可以像遍历单链表那样遍历二叉树了，引入线索二叉树的目的也是为了加快查找节点前驱和后继节点的速度。

因为二叉树节点中的左右指针是不确定指向孩子节点还是前驱、后继，所以要增加两个标志位（ltag、rtag），用以表示指向的具体是什么！

使用C语言表示的节点结构体为：

typedef struct ThreadNode{
    int data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;
}ThreadNode;

规定

若节点无左子树，则lchild指向该节点的前驱节点，ltag为1，否则lchild指向该节点的左孩子节点，ltag为0；

若节点无右子树，则rchild指向该节点的后继节点，rtag为1，否则rchild指向该节点的右孩子节点，rtag为0；

线索化

二叉树的 线索化 是将二叉链表中的空指针改为指向前驱或者后继的线索（地址）。但是前驱或后继的信息只有在遍历时才能得到，故 线索化 的实质就是遍历一次二叉树。

以中序线索二叉树的建立举例：

因为我们要在遍历的过程中将节点的空链域指向前驱和后继，所以需要两个指针 pre、p，分别是指向刚刚访问过的节点和正在访问的节点。在这里pre为p的前驱，p为pre的后继。

那么在遍历的过程中，要检查p的左指针是否为空，为空则指向pre（不为空就不用管了，因为是有孩子节点的）；要检查pre的右指针是否为空，为空则指向p。

中序线索化二叉树

这样遍历一遍后就完成了线索化了。下面是具体的C语言代码：

void inThread(ThreadNode **pre, ThreadNode *p) {
    if (p != NULL) {
        // 递归线索化左子树
        inThread(pre, p->lchild);

        // 处理当前节点
        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(pre, p->rchild);
    }
}


void createThreadTree(ThreadNode **root){
    ThreadNode *pre = NULL;
    if(root != NULL){
        inThread(&pre, root);
        pre->rchild = NULL;
        pre->rtag = 1;
    }
}

先序线索化二叉树

先序线索化二叉树C语言表示：

void preThread(ThreadNode **pre, ThreadNode *p) {
    if (p != NULL) {
        // 处理当前节点
        if (p->lchild == NULL) { // 如果左孩子为空，设置前驱线索
            p->lchild = *pre;
            p->ltag = 1;
        }
        if (*pre != NULL && (*pre)->rchild == NULL) { // 如果前驱的右孩子为空，设置后继线索
            (*pre)->rchild = p;
            (*pre)->rtag = 1;
        }

        // 更新前驱节点为当前节点
        *pre = p;

        // 递归线索化左子树
        if (p->ltag == 0) { // 如果左孩子是普通孩子，递归线索化左子树
            preThread(pre, p->lchild);
        }

        // 递归线索化右子树
        if (p->rtag == 0) { // 如果右孩子是普通孩子，递归线索化右子树
            preThread(pre, p->rchild);
        }
    }
}

后序线索化二叉树

后序线索化化二叉树C语言表示：

void postThread(ThreadNode **pre, ThreadNode *p) {
    if (p != NULL) {
        // 递归线索化左子树
        postThread(pre, p->lchild);

        // 递归线索化右子树
        postThread(pre, p->rchild);

        // 处理当前节点
        if (p->lchild == NULL) { // 如果左孩子为空，设置前驱线索
            p->lchild = *pre;
            p->ltag = 1;
        }
        if (*pre != NULL && (*pre)->rchild == NULL) { // 如果前驱的右孩子为空，设置后继线索
            (*pre)->rchild = p;
            (*pre)->rtag = 1;
        }

        // 更新前驱节点为当前节点
        *pre = p;
    }
}