Avatar mrlxl的知识库
关于我
搜索文章...

文档

数据结构之树与二叉树

2026-02-16

数据结构之树与二叉树

第五章_树与二叉树

5.1 树

5.1.1 树的定义

树是 n (n>=0) 个结点的有限集。当 n 等于 0 时，称作空树

树属于数据结构三要素中：逻辑结构 → 非线性结构 → 树形结构。在任意一棵非空树中必须满足：

  • 有且仅有一个特定的结点称作根结点。
  • 当 n > 1 时，除根结点的其余结点可分为 m（m>0）个互不相交的有限集，其中每个集合本身又是一棵树，称为根的子树。

显然非空树是递归定义的。（每个子树本身又是一棵树，用树来定义树，典型的递归定义），而更具以上定义我们能推出以下两个特征：

  • 根结点没有前驱，除根结点外的每个结点都有且仅有一个前驱
  • 每个结点都可能有零个或者多个后继结点。

错误示意如下： 树的错误示意

5.1.2 树的基本术语

  • 祖先，子孙，双亲，孩子，兄弟和堂兄弟结点： 从根结点到该结点路径上的所有结点（不包括该结点本身），称为该结点的祖先结点。某结点的所有后代结点，称为该结点的子孙结点。

    兄弟结点

  • 结点的层次，深度和高度： 结点的层次从根开始定义，根为第一层，其孩子结点为第二层，以此类推。结点的深度即为其所在的层次。结点的高度是以其为根的子树的高度，如上图树的高度为。

  • 路径和路径长度： 路径是指从一个结点到另一个结点，沿父子关系依次经过的结点序列（包括起始和结束结点）。路径长度是路径上边的数目。（路径是没有方向的，但是涉及到层次，深度，高度等概念时，默认是从上到下，而此时不考虑从下到上的路径）

  • 结点的度和树的度： 树中一个结点的孩子结点的个数称为结点的度。树中所有结点的度的最大值称为树的度。结点的度为 0 的结点为叶结点，结点的度 >0 的结点为分支结点（包括根结点）

  • 有序树和无序树： 具体要看用树来存储些什么，各结点的子树从左到右是否存在逻辑次序关系，存在即为有序树，反之则为无序树。

  • 森林： 森林是 m（m >= 0）个不相交的树的集合。m = 0 时的情况叫做空森林。与树的概念密切相关。把树的根结点移除，其子树构成森林；给森林加一个根结点，森林便转化为一棵树。

5.1.3 树的性质（常考点）

下面介绍几个在考研中常考的性质：

  • 树的结点的个数 = 树的总度数 + 1 （根结点）
  • 树的度为 m 和 m 叉树的区别（m >= 1)：树的度为 m 代表至少有 m+1 个结点（一定非空树），且至少有一个结点的度为 m 所有结点的度都 <= m；m 叉树代表可以为空树，允许所有结点的度 <= m。
  • m 叉树和树的度为 m 的第 i 层都最多有 m i-1 个结点。
  • 高度为 h 的 m 叉树的最多有 (m h - 1) / (m - 1) 个结点（等比数列求和）
  • 高度为 h 的 m 叉树至少有 h 个结点，高度为 h 的度为 m 的树至少有 h + m - 1个结点。
  • 具有 n 个结点的 m 叉树的最小高度为 $$ h = \left\lceil \log_{m}\bigl(n(m-1)+1\bigr) \right\rceil $$ 即要求最小的整数 ( h )，使得
    $$ \frac{m^{,h-1}-1}{m-1} < n \le \frac{m^{,h}-1}{m-1} $$

5.2 二叉树

5.2.1 二叉树的概念

二叉树是一种特殊的树形结构，是包含 n （n >= 0）个结点的有限集合，其核心特征在于：每个结点至多拥有两棵子树。

关于二叉树的概念很好理解，但是值得注意的是：两棵子树有明确的左右之分，其次序固定，是一棵有序树。

下面介绍几种特殊的二叉树：

  • 满二叉树和完全二叉树（形态特殊）： 满二叉树也是一种完全二叉树，如下图所示： 满二叉树和完全二叉树
  • 二叉排序树和平衡二叉树（用途特殊）： 二叉排序树主要就用于中序遍历方便排序。 二叉排序树 平衡二叉树相比非平衡二叉树搜索效率更高，如下图所示的两棵二叉排序树，平衡二叉树搜索更快。 平衡二叉树

5.2.2 二叉树的性质（常考点）

  • 设非空二叉树中度为0、1和2的结点分别为 n0、n1 和 n2，则 n0 = n2 + 1 （叶结点比二分支结点多一个）。结点总数 n = n0 + n1 + n2 = n1 + 2n2 + 1（树的结点数 = 总度数 + 1）

  • 具有 n 个结点的高度为 h 的完全二叉树的性质。 最大结点个数为： 2h - 1 。 对于当前结点 i 其左孩子为 2i 右孩子为 2i + 1。 最小高度为（m = 2 带入上面讲的树的性质）： $$ h = \lceil \log_2(n + 1) \rceil $$ 即对于 h 是最小的整数，使得： $$ 2^{h-1} - 1 < n \le 2^{h} - 1 $$

  • 如果给出一个结点数为 n 的完全二叉树，完全可以根据上面的第一个性质推出度为0、1和2的结点分别为多少。因为 n0 + n2 必定是奇数，所以若 n 为偶数，必定有 n1 = 1， n0 = k， n2 = k - 1；若 n 为奇数，必定有 n1 = 0， n0 = k， n2 = k - 1

5.2.3 二叉树的存储结构

这里仅介绍二叉树的链式存储和顺序存储。

5.2.3.1 二叉树的顺序存储

按照从上到下，从左到右的顺序将每个结点依次存储进数组。即将第 i 个结点存进下标为 i - 1 的数组中，

# define MaxSize 50
typedef struct TreeNode {
    ElemType value; //结点中的数据元素
    bool isEmpty; //判断结点是否存在
}TreeNode;

int main() {
    TreeNode t[MaxSize];
    for (int i = 0; i < MaxSize; i++) {
        t[i].isEmpty = true;   //开始时将所有结点全部置空
    }
}

值得注意的是，根据完全二叉树的性质，完全二叉树的顺序存储中，能有如下的利用方法： 完全二叉树的顺序存储 那对于非完全二叉树顺序存储，数组下标无法反映其逻辑结构，怎么利用呢。可以将非完全二叉树按照完全二叉树的璐姐结构进行存储，但是相比完全二叉树有些性质不能用，如下图所示： 非完全二叉树顺序存储

那其实相比较下，能够得出结论：顺序存储只适合完二叉树的存储，所以通常也不用顺序存储来存储二叉树

5.2.3.2 二叉树的链式存储

二叉树的链式存储（二叉链表）的构建过程的代码如下：

# include<stdlib.h>
typedef struct Elemtype {
    int value;
}Elemtype;

typedef struct BitNode {
    Elemtype data;
    struct BitNode* lchild, * rchild;
}BitNode,*BiTree;

int  main() {
    BiTree T;  //定义一棵树

    //插入根结点
    T = (BiTree)malloc(sizeof(BitNode));
    T->data = { 1 };  //这是C++的聚合初始化写法
    T->lchild = NULL;
    T->rchild = NULL;

    //插入结点
    BitNode* p = (BitNode*)malloc(sizeof(BitNode));
    p->data = { 2 };  //这是C++的聚合初始化写法
    p->lchild = NULL;
    p->rchild = NULL;
    T->lchild = p;  //作为根结点的左孩子
}

普通的线性链表（单链表 / 双链表），在“不知道位置”的情况下，查找只能从头到尾挨个遍历。这是由它的结构决定的。 而这里的树形链表则不再只能“挨个遍历”。 比如为了方便查找可在结点定义中定义一个指向双亲结点的指针，即三叉链表（不常考），如下：

typedef struct BitNode {
    Elemtype data;
    struct BitNode* lchild, * rchild;
    struct BitNode* parent; //三叉链表
}BitNode,*BiTree;

值得注意的是：在结点数为 n 的二叉链表中存在 n + 1 个空链域，因为总共 2n 个链域，除根结点外的每个结点都被一个链域指向，故总共使用 n - 1 个链域，剩余 n + 1 个。而这些空链域可用来实现线索二叉树。 线索二叉树的引出

5.2.4 二叉树的遍历

5.2.4.1 二叉树的前中后序遍历

手算二叉树的前中后序遍历较为简单，在考研中，给定一棵二叉树求取其前中后序遍历序列，也是常考的题目。这里仅给出题目示意(分支结点逐层展开法）： 前序（根）遍历： 根左右 中序（根）遍历： 左根右 后序（根）遍历： 左右根 二叉树的前中后序遍历 使用代码实现二叉树的前中后序遍历也不难，还记得我们提过非空树是递归定义的，同样，使用递归就能实现二叉树的前中后序遍历：

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

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

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

5.2.4.2 二叉树的层次遍历

树的层次遍历，即一层一层的对树进行遍历，其示意图如下： 树的层次遍历 实现该遍历的算法会在之后的章节中介绍，这里介绍使用队列进行树的层次遍历思想：从根节点开始，将其入队；每次出队一个节点并访问它，然后按顺序将该节点的左右孩子（若存在）入队，直到队列为空。 以上图为题，过程如下：

1  //根节点入队
2 3  
3 4 5  //2出队，插入子节点
4 5 6 7
5 6 7  //4没有子节点，出队不必插入
6 7 8 9
7 8 9
8 9 10 11
9 10 11
10 11
11
空

5.2.5 由遍历序列构造二叉树

对于同一遍历序列，其对应的二叉树可能是不同的；但对于同一二叉树，其对应的遍历序列是唯一的。类比高数中的函数（遍历序列 -> 值域，二叉树 -> 定义域）。如图所示： 同一序列不同二叉树 所以如果仅给出一个遍历序列（前/中/后/层序）中的一种，无法确定唯一的一棵二叉树，但如果给出中序（一定要有） + 其他三种任意一种遍历序列的话，就能够推出唯一一棵二叉树。对应的三种题型如下：

  • 前序 + 中序： 前序和中序
  • 后序 + 中序： 后序和中序
  • 层序 + 中序： 层序和中序

5.2.6 线索二叉树

前面已经引出过一个概念，具有 n 个结点的二叉链表空余出来的 n + 1 个空链域能够用来实现线索二叉树，那么什么是线索二叉树？

在线索二叉树被创造之前，为了能够访问前驱结点，土方法通常采用两个指针（当前结点 p 与其前驱 pre） 对二叉树进行遍历，当 pre == q 时找到目标点，遍历结束。如图所示： 土方法

5.2.6.1 线索二叉树的概念

基本二叉链表每个结点通常有三个部分：

  • data：存储结点数据
  • lchild：左孩子指针
  • rchild：右孩子指针

线索二叉树在线索化之后也被称为线索链表，每个结点的指针可能有两种用途：

  • 指向孩子结点（正常的左/右子树）
  • 如果没有左孩子或右孩子，就把指针“穿线”指向 前驱或后继结点（根据中序、前序或后序线索化方式），这种指针称为线索（前驱线索，后继线索）。

所以线索二叉树结点通常需要额外标记来区分指针是指向孩子还是指向前驱/后继。常见写法是：

typedef struct ThreadNode {
    int data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag; // 0 表示指向孩子，1 表示指向前驱/后继
} ThreadNode;

以中序线索二叉树为例，其图示如下： 中序线索二叉树

5.2.6.2 二叉树的线索化

将土方法的思想带入二叉树的线索化实现中，通过遍历实现每个结点前后继线索，当 pre == q 时遍历结束。 假设现在已经有一个普通二叉树且所有结点的标志位为 0 ，那么二叉树中序线索化代码如下：

#include<stdio.h>

typedef struct ThreadNode {
    int data;
    struct ThreadNode* lchild, * rchild;
    int ltag, rtag; // 0 表示指向孩子，1 表示指向前驱/后继
} ThreadNode,*ThreadTree;

ThreadNode* pre = NULL;  //前驱指针初始化为空

//访问这个结点干的事
void visit(ThreadNode* q) {
    if (q->lchild == NULL) {  //建立当前结点的前驱线索
        q->lchild = pre;
        q->ltag = 1;
    }
    if (pre != NULL && pre->rchild == NULL) {  //建立前驱结点的后继线索
        pre->rchild = q;
        pre->rtag = 1;
    }
    pre = q; //pre指针向前移动一位
}

//中序遍历二叉树，一边遍历一边初始化
void InThread(ThreadTree q) {
    if (q != NULL) {
        InThread(q->lchild);
        visit(q);
        InThread(q->rchild);
    }
}

//中序线索化已经初步建成的二叉树
void CreateInThread(ThreadTree T) {
    pre = NULL;
    if (T != NULL) {
        InThread(T);
        if (pre->rchild == NULL) {  //处理最后一个结点（记得处理！！！）
            pre->rtag = 1;
        }
    }
}

二叉树后序线索化和二叉树中序线索化是差不多的，把遍历函数 InThread() 换一下就行。但是对于二叉树先序线索化这样处理就会出现 “爱的魔力转圈圈” 问题，如图所示： 爱的魔力转圈圈 解决方法也很简单，利用标志位，将遍历代码改成这样即可：

void PreThread(ThreadTree q) {
    if (q != NULL) {
        visit(q);
        if (q->lchild == 0) {
            PreThread(q->lchild);
        }
        PreThread(q->rchild);
    }
}

5.2.6.3 在线索二叉树中找前驱和后继

对于已经线索化的二叉树结点，可以根据其线索指针及标志位，直接确定该结点在相应遍历序列中的前驱和后继结点。 但对于存在没有线索化指针的结点，该如何确定其在相应遍历序列中的前驱和后继结点？如何实现相应遍历？对应不同遍历，有以下三种情况： 线索二叉树找前驱和后继 1. 中序遍历和中序线索二叉树找前驱和后继： 对于中序线索二叉树： 其前驱结点一定是左子树最右下结点或者第一个把该结点当作右孩子的祖先。 其后继结点一定是右子树最左下结点或者第一个把该结点当作左孩子的祖先。 实现中序遍历和找中序线索二叉树的后继结点的代码如下：

//找到以P为根的子树中，第一个被中序遍历的结点
ThreadNode *Firstnode(ThreadNode *p) {
    //循环找到最左下结点(不一定是叶结点)
    while(p->ltag==0) p=p->lchild; //一旦 ltag == 1，说明左边已经没有子树可走了
    return p;
}

//在中序线索二叉树中找到结点p的后继结点
ThreadNode *Nextnode(ThreadNode *p) {
    //右子树中最左下结点
    if(p->rtag==0) return Firstnode(p->rchild);
    else return p->rchild;   //rtag==1直接返回后继线索
}

//对中序线索二叉树进行中序遍历 (利用线索实现的非递归算法)
void Inorder(ThreadNode *T) {
    for(ThreadNode *p=Firstnode(T); p!=NULL; p=Nextnode(p))
        visit(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 return p->lchild;   //ltag==1直接返回前驱线索
}

//对中序线索二叉树进行逆向中序遍历
void RevInorder(ThreadNode *T) {
    for(ThreadNode *p=Lastnode(T); p!=NULL; p=Prenode(p))
        visit(p);
}

2. 先序遍历和先序线索二叉树找前驱和后继： 对于先序线索二叉树： 其前驱结点对于没有线索化的结点无法直接找到其前驱结点，除非采用额外的辅助结构（如三叉链表，土方法重新遍历，线索等）。
其后继结点一定是其左孩子（左孩子存在）、右孩子（只存在右孩子) 或 后继线索（无孩子结点）。

3. 后序遍历和后序线索二叉树找前驱和后继： 对于后序线索二叉树： 其前驱结点一定是其右孩子（右孩子存在）、左孩子（只存在左孩子）或 前驱线索（无孩子结点）。 其后继结点对于没有线索化的结点无法直接找到其后继结点，除非采用额外的辅助结构（如三叉链表，土方法重新遍历，线索等）。

5.3 树的存储结构

5.3.1 双亲表示法

前面介绍过顺序存储适用于完全二叉树，但是显然脱离 “二叉” 这个语境之后就不存在 “满树” 和 “二叉树” 这样的说法。那么如何使用顺序存储存储树？ 于是双亲表示法应运而生，这是一种顺序存储结构，对每个结点增设伪指针，用来指示双亲结点在数组中的下标（根结点指向 -1）。如图所示： 双亲表示法 同理这种方法也能用来表示森林，但是只适用于 “找父亲” 多，“找孩子” 少的情况，例如并查集。

5.3.2 孩子表示法

孩子表示法是一种结合顺序存储和链式存储的方法，将所有孩子视做一个线性表，用单链表存储，整棵树由 n 个这样的孩子链表组成（叶结点对应空链表）。 孩子表示法 同理这种方法也能用来表示森林，但与双亲表示法相反的是孩子表示法便于查找结点的孩子，但若要查找某结点的双亲，则需遍历所有孩子链表，效率较低。 孩子表示法

5.3.3 孩子兄弟表示法

是一种链式存储方法，与二叉树类似，都采用二叉链表进行存储。每个结点的指针域一个指向第一个孩子，一个指向下一个兄弟，如图所示： 孩子兄弟表示法 同理也能用来表示森林，注意：森林中的每一棵树视为平级的兄弟关系： 森林孩子兄弟表示法

5.4 树、森林和二叉树的转换

本小节介绍树、森林和二叉树的转换，其实很简单，其核心在于孩子兄弟表示法的正逆使用，如图所示： 树、森林和二叉树的转换 核心在于理解，使用也较为简单，最好按照层序进行转化，这样不容易出错，这里贴出下面四个例子： 树 -> 二叉树 二叉树 -> 树 森林 -> 二叉树 二叉树 -> 森林

5.5 树和森林的遍历

在前面学习了线索二叉树的遍历之后，我们接着来了解树和森林的遍历：

  • 树的遍历： 先根遍历，后根遍历，层序遍历。
  • 森林的遍历： 先序遍历，中序遍历。

5.5.1 树的遍历

树的先根遍历和后根遍历也能称作树的深度优先遍历，树的层次遍历也能称为树的广度优先遍历。

5.5.1.1 树的先根遍历

先根遍历就是先访问根，再按顺序从左到右访问各棵子树，与二叉树的先序遍历类似，实际上，二叉树的先序遍历就是树的先根遍历的一个特例。树的先根遍历与其对应的二叉树的先序遍历相同（别对应着记，只是恰好相同），示例如下： 树的先根遍历

5.5.1.2 树的后根遍历

后根遍历就是先从左到右访问各棵子树，再访问根，同理，二叉树的后序遍历其实也是树的后根遍历的一个特例。树的后根遍历与其对应的二叉树的中序遍历相同，示例如下： 树的后根遍历

5.5.1.3 树的层序遍历

就是从上到下，一层一层访问。也称为树的广度优先遍历实现思路和二叉树的层序遍历是一样的，都是通过队列进行实现，规则如下：

  1. 若树非空，将根结点入队。
  2. 若队列非空，将队头元素出队并访问，同时将该元素的孩子结点依次入队。
  3. 重复步骤二直到队列为空。

5.5.2 森林的遍历

5.5.2.1 森林的先序遍历

就是等价于从第一棵树开始挨个对每棵树进行树的先根遍历，也等价于森林转化成的二叉树的先序遍历，示例如下： 森林的先序遍历

5.5.2.2 森林的中序遍历

同理，等价于从第一棵树开始挨个对每棵树进行树的后根遍历，也等价于森林转化成的二叉树的中序遍历，示例如下： 森林的中序遍历

5.6 哈夫曼树

哈夫曼树也被称为最优二叉树，在考研中的重点就是怎么构造哈夫曼树以及哈夫曼编码。下面先要介绍几个相关概念：

5.6.1 哈夫曼树的概念

  • 结点的权： 树的结点被赋予的一个具有特定意义的值。
  • 结点的带权路径长度： 从树的根结点到某一结点的路径长度与该结点权值的乘积。
  • 树的带权路径长度（WPL）： 树中所有叶结点的带权路径长度之和

在含有 n 个带权叶结点的二叉树中（注意带权叶结点个数要相同哦！！），WPL最小的二叉树被称为哈夫曼树，也被称为最优二叉树。下面以图示说明： 哈夫曼树示意

5.6.2 哈夫曼树的构造

给出 n 个带权结点构造一棵哈夫曼树，构造过程很简单，不停地结合权值最小的两个结点，每次结合之后结点放回进行下一次循环。值得注意的是结合之后的性质，其图示如下： 哈夫曼树的构造

5.6.3 哈夫曼编码

在数据通信中，将固定长度编码转换成可变长度编码（如哈夫曼编码） 对出现频率较高的字符赋予较短编码，起到压缩数据的效果。即以节点频度作为结点的权值，对其进行哈夫曼树的构造。 哈夫曼编码 但是请注意，所有的字符集中的字符，对应到编码树中，只能做叶子结点（无前缀编码），不然就会出现翻译的歧义错误，如图所示： 哈夫曼编码注意

5.7 并查集

5.7.1 并查集的概念

并查集是一种处理不相交集合的合并与查询问题的树状数据结构（并查集在语义上是集合，在实现上使用树结构），就名字而言，并查集当然最主要的两个早操作就是 “并” 和 “查” 啦。

将所有集合抽象成的树全部放到同一个数组，并查集主要采用双亲表示法（顺序存储）实现：

  • 并： 将不同集合（树）合并，将一棵树的根结点的 parent 指针指向另一棵树的根结点即可。
  • 查： 查询一个元素属于哪个集合，将这个元素一直向上查询，看他属于哪个根结点即可。

下面是实现代码，由于 “并” 操作代码涉及到优化，这里表示一下 “查” 操作的代码和未优化的 “并” 操作的代码：

#define MaxSize 13
//初始化并查集
void Initial(int S[]) {
    for (int i = 0; i < MaxSize; i++) {
        s[i] = -1;
    }
}

//“并”操作（未优化）
void Union(int* S, int root1, int root2) {
    //要求root1与root2是不同的集合
    if (root1 == root2) {
        return;
    }
    S[root1] = root2;
}

//“查”操作
int Find(int* S, int x) {
    while (S[x] >= 0) {
        x = S[x];
    }
    return x;
}

5.7.2 并查集的进阶以及高阶优化

显而易见，上面的代码 Find 函数的时间复杂度为 O(n)，Union 函数的时间复杂度为 O(1)。类比之前提过的平衡二叉树的搜索效率更高，我们很轻易能想到树越 “平衡” Find 函数的时间复杂度越低。

进阶优化方法将数组中根结点对应的数组元素不再为 -1 而是为 -当前树的深度，采用只将小树（深度小的树）接入大树（深度大的树）思想，Find 函数的时间复杂度变为 O(log2n) （数学归纳法证明），其代码和示意图如下：

//“并”操作（进阶优化）
void Union(int* S, int root1, int root2) {
    if (S[root1] <= root2) { //root1这棵树的高度大于等于root2这棵树，注意是负数！！
        S[root1] += S[root2];
        S[root2] = root1;
    }
    else {
        S[root2] += S[root1];
        S[root1] = root2;
    }
    return;
}

并查集的进阶优化

高阶优化方法是在进阶优化方法的基础上对 Find 函数进行优化，将其查询路径压平以方便更快查找，其代码和示意图如下：

int Find(int* S, int x) {
    int root = x;
    while (S[x] >= 0) {
        root = S[root];  //循环先找到根节点
    }
    while (x != root) {
        int t = S[x];
        S[x] = root;
        x = t;
    }
    return root;
}

高阶优化并查集

附言

本章不难，但是内容有点繁多，稍微乱了点，让我想起以前打算法比赛的时候。

总是在探索未知

大纲

ESC 关闭 ↑↓ 选择 Enter 跳转