数据结构——树与二叉树

这一篇主要介绍了数据结构中树的知识点

---

文章目录

一、树的基本概念1. 树的定义2. 基本术语3. 树的性质 二、二叉树的概念1. 二叉树的定义及主要特性（1）满二叉树（2）完全二叉树（3）二叉排序树（4）平衡二叉树（5）二叉树的性质 2. 二叉树的存储结构（1）顺序存储（2）链式存储 三、 二叉树的遍历1. 先序遍历2. 中序遍历3. 后序遍历4. 递归和非递归的转换5. 层次遍历6. 由遍历构造二叉树 四、线索二叉树1. 线索二叉树的基本概念2. 线索二叉树的构造3. 线索二叉树的遍历 五、树和森林1. 树的存储结构（1）双亲表示法（2）孩子表示法（3）孩子兄弟表示法 2. 树、森林、二叉树的转换3. 树和森林的遍历 六、 树的应用——并查集七、 二叉树的应用1. 二叉排序树（1）二叉排序树定义（2）二叉排序树查找（3）二叉排序树插入（4）二叉排序树构造（5）二叉排序树删除（6）二叉排序树的查找效率分析 2. 平衡二叉树（1）平衡二叉树定义（2）平衡二叉树插入（3）平衡二叉树查找 3. 哈夫曼树（1）哈夫曼树定义（2）哈夫曼树构造（3）哈夫曼编码

---

|- 二叉树-------|- 概念 | |- 操作：三种遍历（先序、中序、后序）；线索二叉树 | |- 应用：排序二叉树；平衡二叉树；哈夫曼树 树形结构-----| | |- 概念 |- 与二叉树的转换 | |- 操作：---|- 树遍历（先根、后根）；森林遍历（先序、中序） |- 树和森林-----|- 应用：并查集

---

一、树的基本概念

1. 树的定义

是一种递归的数据结构 根节点没有前驱，其他节点只有一个前驱；所有节点有零个或多个后继。

2. 基本术语

节点的度：树中一个节点的子节点个数； 树的度：树中节点的最大度数； 节点的深度：从根节点自顶向下逐层累加； 节点的高度：从叶子节点自底向上逐层累加；

3. 树的性质

（1）树中节点数等于所有节点的度数加1； （2）度为m的树第 i 层至多有 m^(i-1) 个节点； （3）高度为h的m叉树 至多有 (m^h-1)/(m-1) 个节点；

二、二叉树的概念

1. 二叉树的定义及主要特性

二叉树是有序树，二叉树可以是空树

（1）满二叉树

（2）完全二叉树

特点如下：

叶子节点只可能在层次最大的两层，且最大层次的叶子节点都在左边。如果有度为1的节点，只可能有一个，且该节点只有左孩子没有右孩子。节点个数为n，若n为奇数，则每个分支节点都有左孩子和右孩子；若n为偶数，则编号最大的节点只有左孩子没有右孩子，其余节点左右孩子都有。

（3）二叉排序树

左子树上所有节点的关键字 < 根节点的关键字 < 右子树上所有节点的关键字

（4）平衡二叉树

任一节点的左右子树深度之差不超过1.

（5）二叉树的性质

非空二叉树叶子上节点数 N0 等于度为2的节点数 N1 加1，即 N0 = N1 +1；

2. 二叉树的存储结构

（1）顺序存储

用一组地址连续的存储单元依次自上而下、自左至右 存储完全二叉树的节点；完全二叉树和满二叉树适合采用顺序存储，既能最大可能的节省存储空间，又可以利用数组元素的下标值确定节点在二叉树的位置，以及节点之间的位置关系；

（2）链式存储

由于顺序存储的空间利用率第，所以通常采用链式存储；有 n 个节点的二叉链表中含有 n+1 个空链域； 链式存储结构如下： typedef struct BiTNode{ ElemType data; //数据域 struct BiTNode *lchild, *rchild; //左、右孩子域 } BiTNode, *BiTree;

三、 二叉树的遍历

1. 先序遍历

时间复杂度O(n)，空间复杂度O(n)

void PreOrder(BiTree T){ if(T != NULL){ visit(T); PreOrder(T->lchild); PreOrder(T->rchild); } }

2. 中序遍历

时间复杂度O(n)，空间复杂度O(n)

void InOrder(BiTree T){ if(T != NULL){ InOrder(T->lchild); visit(T); InOrder(T->rchild); } }

3. 后序遍历

时间复杂度O(n)，空间复杂度O(n)

void PostOrder(BiTree T){ if(T != NULL){ PostOrder(T->lchild); PostOrder(T->rchild); visit(T); } }

4. 递归和非递归的转换

可以借助栈，将二叉树的递归遍历转化为非递归遍历。

非递归先序遍历 算法步骤如下： 从根开始，当前节点存在或栈不为空，重复下面两个操作。 （1）访问当前节点，当前节点进栈，进入其左子树，重复至当前节点为空； （2）若栈非空，则栈顶节点出栈，并进入其右子树。 void PreOrder(BiTree root){ SeqStack *S; BiTree p; InitStack(S); p = root; while(p != NULL || !IsEmpty(S)){ //当前节点指针和栈均为空，则结束 while(p != NULL){ visit(p->data); //访问根节点 Push(S, p); //根指针进栈 p = p->lchild; //进入左子树 } if(!IsEmpty(S)){ //如果栈非空 Pop(S, &p); //根指针出栈 p = p->rchild; //进入右子树 } } } 非递归中序遍历 算法步骤如下： 从根开始，当前节点存在或栈不为空，重复下面两个操作。 （1）当前节点进栈，进入其左子树，重复至当前节点为空； （2）若栈非空，则栈顶节点出栈，访问该出栈节点，并进入其右子树。 void InOrder(BiTree root){ SeqStack *S; BiTree p; InitStack(S); p = root; while(p != NULL || !IsEmpty(S)){ //当前节点指针和栈均为空，则结束 while(p != NULL){ Push(S, p); //根指针进栈 p = p->lchild; //进入左子树 } if(!IsEmpty(S)){ //如果栈非空 Pop(S, &p); //根指针出栈 visit(p->data); //访问根节点（和先序遍历的不同之处） p = p->rchild; //进入右子树 } } } 非递归后序遍历 算法步骤如下： 从根开始，当前节点存在或栈不为空，重复下面两个操作。 （1）当前节点进栈，进入其左子树，重复至当前节点为空； （2）若栈非空，判断栈顶 p 的右子树是否为空、右子树是否刚访问过。 若是，则出栈、访问节点 p ，p 赋给 q，p置为空； 若不是，则进入 p 的右子树。 void PostOrder(BiTree root){ SeqStack *S; BiTree p,q; InitStack(S); p = root; q = NULL; while(p != NULL || !IsEmpty(S)){ //当前节点指针和栈均为空，则结束 while(p != NULL){ Push(S, p); //根指针进栈 p = p->lchild; //进入左子树 } if(!IsEmpty(S)){ //如果栈非空 Top(S, &p); //判断栈顶的右子树是否为空，右子树是否访问过 if((p->rchild==NULL) || (p->rchild==q)){ Pop(S, &p); //根指针出栈 visit(p->data); //访问根节点 q = p; p = NULL; } else{ p = p->rchild; } } } }

5. 层次遍历

层次遍历需要借助一个队列。 算法步骤如下： 首先根节点入队，当队列非空时，重复如下操作。 （1）队头节点出队，并访问出队节点； （2）出队节点的非空 左、右孩子依次入队。

void LevelOrder(BiTree T){ InitQueue(Q); BiTree p; EnQueue(Q, T); //根节点入队 while(!IsEmpty(Q)){ //队列不为空进循环 DeQueue(Q, p); //队头元素出队 visit(p); //访问当前p所指向的节点 if(p->lchild != NULL){ EnQueue(Q, p->lchild); //左子树不为空，则左子树入队 } if(p->rchild != NULL){ EnQueue(Q, p->rchild); //右子树不为空，则右子树入队 } } }

6. 由遍历构造二叉树

二叉树的先序和中序可以唯一的确定一棵二叉树。二叉树的后序和中序可以唯一的确定一棵二叉树。二叉树的层次和中序可以唯一的确定一棵二叉树。注意：先序和后序，不能唯一确定一棵二叉树。

四、线索二叉树

1. 线索二叉树的基本概念

传统的链式存储只能体现一种父子关系，不能直接得到遍历中的前驱和后继。引入线索二叉树的目的：为了加快查找前驱和后继节点的速度。线索化规定：若无左子树，另 lchild 指向其前驱节点；若无右子树，则令 rchild 指向其后继节点。 ltag = 0, lchild指向节点的左孩子 ltag = 1, lchild指向节点的前驱rtag = 0, rchild指向节点的右孩子 rtag = 1, rchild指向节点的后继 typedef struct ThreadNode{ ElemType data; struct ThreadNode *lchild, *rchild; int ltag, rtag; }ThreadNode, *ThreadTree;

2. 线索二叉树的构造

通过中序遍历对二叉树线索化：

//中序遍历对二叉树线索化的递归算法 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 CreateInThread(ThreadTree T){ ThreadTree pre = NULL; if(T != NULL){ //树非空 InThread(T, pre); //线索化二叉树（调用函数） pre->rchild = NULL; //处理便利的最后一个节点 pre->rtag = 1; } }

3. 线索二叉树的遍历

中序线索二叉树的遍历不需要栈，可以实现非递归遍历。

求中序线索二叉树中 中序序列的第一个节点 ThreadNode *Firstnode(ThreadNode *p){ while(p->ltag == 0){ p = p->lchild; //最左下节点（不一定是叶子节点） } return p; } 求中序线索二叉树中 节点 p 在中序序列下的后继节点 ThreadNode *Nextnode(ThreadNode *p){ if(p->rtag == 0){ return Fiestnode(p->rchild); } else{ return p->rchild; //rtag==1，直接返回后继线索 } } 二叉树的线索链表也可以带头结点。

五、树和森林

1. 树的存储结构

（1）双亲表示法

#define MAX_TREE_SIZE 100 typedef struct{ //树的结点定义 ElemType data; int parent; }PTNode; typedef struct{ //树的类型定义 PTNode nodes[MAX_TREE_SIZE]; //双亲表示 int n; //节点数 }PTree; 优点：可以很快得到每个节点的双亲节点。缺点：求节点的孩子时要遍历整个结构。

（2）孩子表示法

优点：寻找子女节点操作简单。缺点：寻找双亲节点需要遍历多。

（3）孩子兄弟表示法

typedef struct CSNode{ ElemType data; struct CSNode *firstchild, *nextsibling; //第一个孩子、右兄弟 指针 }CSNode, *CSTree; 优点：可以方便实现树转化为二叉树的操作，易于查找节点的孩子。缺点：从当前节点查找双亲节点比较麻烦。（如果为每个节点增设一个parent域指向父亲节点，则查找节点的父亲节点也方便。）

2. 树、森林、二叉树的转换

树转换为二叉树：每个节点左指针指向第一个孩子节点，右指针指向它在树中相邻的兄弟节点。（左孩子右兄弟） 注意：由树转换得到的二叉树没有右子树。

森林转换为二叉树：与上述转换类似，先将森林中的每棵树转换为二叉树。然后将第一棵树的根作为二叉树的根，第二棵树的根作为第一个右孩子，以此类推。

二叉树转换为森林：上述过程的逆推即可。

3. 树和森林的遍历

树的遍历 （1）先根遍历 （2）后根遍历森林的遍历 （1）先序遍历 （2）中序遍历树、森林、二叉树 各种遍历之间的关系 树森林二叉树先根遍历先序遍历先序遍历后根遍历中序遍历中序遍历 重要性质：在 n 个节点的树中有 n-1 条边。 那么对于每棵树来说，节点数=边数+1。 故如果题目：森林中节点数比边数多5，则森林有5棵树。

六、 树的应用——并查集

七、 二叉树的应用

1. 二叉排序树

（1）二叉排序树定义

二叉排序树（BST），也称二叉查找树，中序遍历是一个有序序列。 左子树节点值 < 根节点值 < 右子树节点值

（2）二叉排序树查找

二叉排序树的非递归查找：从根节点开始，沿某一个分支逐层向下进行比较

//查找函数返回指向关键字值为key的节点指针，若不存在，返回 NULL BSTNode *BST_Search(BiTree T, ElemType key, BSTNode *&p){ p = NULL; while(T != NULL && key != T->data){ p = T; // p 指向被查找节点的双亲，用于插入和删除操作中 if(key < T->data){ T = T->lchild; } else{ T = T->rchild; } } return T; }

（3）二叉排序树插入

二叉排序树是一种动态集合，树的结构通常不是一次生成的，而是在查找过程中，逐渐插入的。（插入的新节点一定是某个叶子节点）

//在二叉排序树中插入一个关键字为 k 的节点 int BST_Insert(BiTree &T, KeyType k){ if(T == NULL){ //原树为空，新插入的记录为根节点 T = (BiTree)malloc(sizeof(BSTNode)); T->key = k; T->lchild = T->rchild = NULL; return 1; //返回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); } }

（4）二叉排序树构造

构造一棵二叉排序树就是一次输入数据元素，并将它们插入到二叉排序树中的适当位置上的过程。

//用关键字数组 str[] 建立一个二叉排序树 void Creat_BST(BiTree &T, KeyType str[], int n){ T = NULL; //初始时为空树 int i = 0; while(i < n){ //依次将每个元素插入 BST_Insert(T, str[i]); i++; } }

（5）二叉排序树删除

删除操作的过程按三种情况来处理： （1）若被删节点 k 为叶子节点，则直接删除。 （2）若被删节点 k 只有一棵左子树或右子树，则令 k 的孩子替代 k 的位置。 （3）若被删节点 k 有左、右两棵子树，则令 k 的直接后继（或直接前驱）替代 k ，然后将其删除。

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

对于高度为 H 的二叉排序树，其插入和删除操作的运行时间都是 O(H) 平均查找长度 ASL 主要取决于树的高度。

如果是一棵单支树，平均查找长度为 O(n) 如果是一棵平衡二叉树，平均查找长度为 O(log2 n)

优点：无需移动节点，只需修改指针即可完成插入和删除操作。 当有序表是静态查找时，宜用顺序表作为其存储结构，用二分查找； 当有序表是动态查找时，宜用二叉排序树作为其逻辑结构。

2. 平衡二叉树

（1）平衡二叉树定义

平衡二叉树（AVL树）：任意节点的左、右子树高度差的绝对值不超过1。平衡因子：节点左子树和右子树的高度差，平衡二叉树的平衡因子只能为 -1、0、1.

（2）平衡二叉树插入

二叉排序树保证平衡的基本思想：每当插入或删除节点时，首先要检查是否会导致不平衡。① 如果导致了不平衡，则先找到插入路径上离插入节点最近的平衡因子绝对值大于1的节点A；② 再对以A为根的子树，在保持二叉排序树特性的前提下，调整各节点位置关系，重新达到平衡。注意：每次调整的对象都是最小不平衡子树。一般可将失去平衡后进行调整的规律归纳为以下四种情况：

（1）LL平衡旋转（右单旋转）

（2）RR平衡旋转（左单旋转）

（3）LR平衡旋转（先左后右双旋转）

（4）RL平衡旋转（先右后左双旋转）

（3）平衡二叉树查找

在平衡二叉树上的查找过程和二叉排序树相同。 平衡二叉树的平均查找长度为 O(log2 n)

3. 哈夫曼树

（1）哈夫曼树定义

节点的带权路径长度：从树的根节点到任意节点的路径长度与该节点上权值的乘积。 树的带权路径长度：树中所有叶子节点的带权路径长度之和。

（2）哈夫曼树构造

哈夫曼树的构造过程：

哈夫曼树的特点： （1）每个初始节点都成为叶子节点，并且权值越小到根节点路径越长。 （2）构造过程中共新建了 N-1 个节点，因此哈夫曼树中节点总数为 2N-1。 （3）每次构造都选择2棵树作为新节点的孩子，因此哈夫曼树中不存在度为1的节点。

（3）哈夫曼编码

可变长度的编码比固定长度的编码好，其特点是对频率高的字符用短编码，频率低的字符用长编码。可以起到压缩数据的效果。前缀编码：没有一个编码是另一个编码的前缀。如：0、101、100是前缀编码。