前言

树的基本概念

树的定义

树是一种数据结构，它和我们现实生活中的树非常类似，其存在一个根节点，向下分裂，产生分支节点，如此，形成了如下图所示的“树”：

image-20220818031232002

图片来源王道《数据结构》

当然，存在一种特殊的树——空树，也就是结点树为 0 的树。

非空树的特性：

  • 有且仅有一个根节点
  • 没有后继的结点称为“叶子结点”（终端结点）
  • 有后继的结点称为“分支节点”（非终端结点）

结点之间的关系描述

  • 祖先结点：在当前指定结点前驱到根节点路径上的所有结点（即上层）
  • 子孙结点：指定结点下面的所有结点
  • 双亲结点：指定结点的前驱结点
  • 孩子结点：指定结点的直接后继
  • 兄弟结点：指定结点同一层且同一个前驱的结点
  • 堂兄弟结点：指定结点同一层且不是同一个前驱的结点
  • 结点之间的路径：根结点到指定结点（只能从上往下）
  • 路径长度：指的经过了几条边（只能从上往下）

结点，树的属性描述

  • 结点的层次（深度）：从上往下数
  • 结点的高度：从下往上数
  • 树的高度（深度）：总共多少层
  • 结点的度：结点有几个分支
  • 树的度：各结点的度的最大值

树的分类

  • 有序树：逻辑上树中的结点的各子树从左到右是有次序的，不能互换。
  • 无序树：逻辑上树中的结点的各子树从左到右是无次序的，可以互换。
  • 森林：是由 n 棵互不相交的树的集合

二叉树

二叉树的基本概念

二叉树就是每个分支结点都由左子树和右子树组成，图示如下：

image-20220818040634519

图片来源：王道《数据结构》

二叉树可以分为两种：

  • 空二叉树
  • 或者由一个根结点和两个互不相交的被称为跟的左子树和右子树组成。左子树和由子树又分别是一颗二叉树。

二叉树的特点：

  • 每个结点至多只有两颗子树
  • 左右子树不能颠倒（二叉树是有序树）

特殊的二叉树

满二叉树

一颗树高为 $h$ ，且含有 $2^h-1$ 个结点的二叉树。

image-20220818041148646

其特点：

  • 只有最后一层有叶子结点
  • 不存在度为 1 的结点（要么是 2 ，要么是 0）
  • 按层序从 1 开始编号，结点 $i$ 的左孩子为 $2i$ ，右孩子为 $2i+1$ ；结点 $i$ 的父节点为 $\frac{i}{2}$ （向下取整）

完全二叉树

当二叉树的其每个结点都与同高度的满二叉树编号 $1 \sim n$ 的结点一一对应时，称其为完全二叉树。

image-20220818042748756

其特点：

  • 只有最后两层可能有叶子结点
  • 最多只有一个度为 1 的结点
  • 按层序从 1 开始编号，结点 $i$ 的左孩子为 $2i$ ，右孩子为 $2i+1$ ；结点 $i$ 的父节点为 $\frac{i}{2}$ （向下取整）
  • $i \leqslant \frac{n}{2}$ 为分支结点，$i > \frac{n}{2}$ 为叶子结点

二叉排序树

一棵二叉树或者空二叉树，具有如下性质：

  • 左子树上所有结点关键字均小于根节点的关键字
  • 右子树上所有结点关键字均大于根节点的关键字
image-20220818043620187

平衡二叉树

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

image-20220818043902145

二叉树的存储结构

和线性表一样，二叉树也可以使用顺序存储和链式存储的方式来建立

顺序存储

完全二叉树

使用顺序存储借助数组，将完全二叉树从上到下从左到右按顺序依次存储到数组中，其存储结构代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
#define MaxSize 100	//树的大小
#define ElemType int	//结点存储的数据类型

typedef struct TreeNode {
	ElemType value;	//二叉树结点存储的数据
	bool isEmpty;	//表示该结点是否为空
}TreeNode;

//通过建立数组来建立一个二叉树
int main() {
	TreeNode t[MaxSize];
}

使用顺序存储，对于常用的完全二叉树基本操作：

  • 获取 i 的左孩子：$2i$
  • 获取 i 的右孩子：$2i+1$
  • 获取 i 的父结点：$\frac{i}{2}$
  • 获取 i 所在的层次：$\log_2{(n+1)}$ 或 $log_2{n} + 1$

如果完全二叉树共有 n 个结点，则：

  • 判断 i 是否有左孩子：$2i \leq n$
  • 判断 i 是否有右孩子：$2i+1 \leq n$
  • 判断 i是否时叶子结点：$i> \frac{n}{2}$

非完全二叉树

对于普通的二叉树，不可以直接使用上述的方案来存储，需要将其对应的完全二叉树内容进行重编号来排列，例如：

image-20220818202840142

如果非完全二叉树共有 n 个结点，它的一些基本操作的判断就不能使用上述的完全二叉树来判断了，只能使用定义二叉树时的关键字isEmpty来判断。

如果非完全二叉树采用顺序存储结构，会造成大量的空间浪费，所以对于顺序存储来说，完全二叉树是最适合的。

链式存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define MaxSize 100
#define ElemType int

//链式存储
typedef struct TreeNode {
	ElemType data;	//结点存储的数据
	struct TreeNode* lchild, *rchild;	//左孩子和右孩子的指针
}TreeNode;

//初始化树
bool InitTree(Tree t) {
	t = malloc(sizeof(TreeNode));
	t->data = 1;
	t->lchild = NULL;
	t->rchild = NULL;
}
image-20220818204141147

二叉树的遍历

前排说明：如下的先中后序遍历，层次遍历是伪代码示例，在层次遍历最后我会附上可以执行的C代码说明。

先/中/后序遍历

先序遍历

先序遍历规则：根左右（NLR），即先遍历根节点，再遍历左结点，再遍历右结点

1
2
3
4
5
6
7
8
9
//先序遍历
void PreOrder(Tree t) {
	if (t!=NULL)
	{
		GetNodeData((TreeNode*)t);	//先获取根结点的值
		PreOrder(t->lchild);	//再获取左边结点的值
		PreOrder(t->rchild);	//再获取右边结点的值
	}
}

中序遍历

先序遍历规则：左根右（NLR）

1
2
3
4
5
6
7
8
9
//中序遍历
void InOrder(Tree t) {
	if (t != NULL)
	{
		InOrder(t->lchild);	//先获取左边结点的值
		GetNodeData((TreeNode*)t);	//再获取根结点的值
		InOrder(t->rchild);	//再获取右边结点的值
	}
}

中序遍历和先序遍历，只需要将根节点的的获取调换位置即可。

后序遍历

先序遍历规则：左右根（NLR）

1
2
3
4
5
6
7
8
9
//后序遍历
void PostOrder(Tree t) {
	if (t != NULL)
	{
		PostOrder(t->lchild);	//先获取左边结点的值
		PostOrder(t->rchild);	//再获取右边结点的值
		GetNodeData((TreeNode*)t);	//再获取根结点的值
	}
}

层序遍历

层序遍历也是我们所符合逻辑上直观的遍历方式，它采用从上到下从左到右的遍历顺序遍历二叉树。

image-20220820012743860

实现思路：

  1. 初始化辅助队列
  2. 将根节点压入队
  3. 如果队列非空，则出队读取其数据并将其左右孩子依次入队（队尾）
  4. 然后重复如上，直到队列为空

代码示例（伪代码）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//层序遍历
void LevelOrder(Tree t) {
	//创建辅助队列
	Queue s;
	//将根节点压入队列
	AddItem(&s, t);
	//如果队列非空
	while (!IsEmpty(&s))
	{
		//出队元素并访问
		GetNodeData(DeQueue(&s));
		//将元素的左右孩子压入队列
		if (t->lchild!=NULL)
			AddItem(&s, t->lchild);
		if (t->rchild != NULL)
			AddItem(&s, t->rchild);
	}
}

二叉树遍历代码

如下代码为纯C语言代码，使用Visual Studio的C/C++环境编译成功，请创建两个头文件（即.h文件），**分别命名为队列的链式存储.h和二叉树结构.h**。

如果你问我为什么这么做？我其实是为了复用我在队列部分定义的代码而修改使用的（其实是我很懒），所以你会看到队列的头文件中定义的方法可能有部分没用上，那是因为那是队列的适合定义的代码。

各个文件内容如下：

二叉树结构.h

1
2
3
4
5
6
7
8
#define MaxSize 100
#define ElemType int

//链式存储
typedef struct TreeNode {
	ElemType data;	//结点存储的数据
	struct TreeNode* lchild, * rchild;	//左孩子和右孩子的指针
}TreeNode, * Tree;

队列的链式存储.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdbool.h>
#include <malloc.h>
#include "二叉树结构.h"
#define ElemType TreeNode*

//队列元素结构
typedef struct node
{
    ElemType data; //二叉树结点
    struct node* next; //下一个结点的指针
}QNode;

//头结点结点结构
typedef struct head
{
    struct node* front; //队列队头指针
    struct node* rear;  //队列队尾指针
    int size;   //队列的大小
}QHead;


//初始化队列-带头结点
void InitQueue(QHead* q) {
    q->front = NULL;    //队头指针初始化
    q->rear = NULL; //队尾指针初始化
    q->size = 0;    //初始化队列大小
    printf("队列初始化成功\n");
}

//入队操作
bool EnQueue(QHead* q, ElemType data) {
    QNode* qn = (QNode*)malloc(sizeof(QNode));  //新元素结点申请内存空间
    qn->data = data;
    if (q->size < 1)
    {
        qn->next = NULL;    //尾指针为空
        q->front = qn;  //头指针指向第一个元素
    }
    else {
        qn->next = q->rear->next;   //新元素的下一个元素指针指向队尾指针的下一个
        q->rear->next = qn; //原来的队尾元素指向新队尾元素
    }
    q->rear = qn;   //尾指针指向第一个元素
    q->size++;  //队列的长度+1
    //printf("元素 %d 入队成功,当前队列长度为:%d\n", data, q->size);
    //GetHead(q);
    return true;
}

//出队操作
ElemType DeQueue(QHead* q) {
    if (q->front == NULL)  //判断队列是否为空
        return NULL;
    QNode* tempNode = q->front;
    ElemType tempdata = tempNode->data; //获取队头元素
    q->front = tempNode->next;  //队头指向新的队头元素
    free(tempNode); //释放出队元素的内存空间
    q->size--;  //队列元素-1
    return tempdata;    //返回出队元素数据
}

//读取队头元素
ElemType GetHead(QHead* q) {
    if (q->front == NULL) {
        printf("队列为空队列\n");
        return NULL;
    }  //判断队列是否为空
    printf("队头元素为:%d\n", q->front->data);
    return q->front->data;
}

//销毁队列
bool Destory(QHead* q) {
    for (int i = 0; i < q->size; i++)
    {
        DeQueue(q);
    }
    InitQueue(q);
    printf("队列已销毁\n");
    return true;
}

二叉树.c

这是本体文件所在，即我定义和使用二叉树的相关方法的文件，也是main入口函数的位置.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <string.h>
#include "队列的链式存储.h"	//引入队列文件

//初始化树
bool InitTree(Tree* t) {
	(*t) = NULL;
	printf("初始化结点完成\n");
	return true;
}

//返回左节点，为空则返回NULL
TreeNode* LeftNode(TreeNode* node) {
	return node->lchild;
}

//返回右节点，为空则返回NULL
TreeNode* RightNode(TreeNode* node) {
	return node->rchild;
}

//返回结点的数据
ElemType GetNodeData(TreeNode* node) {
	//如果结点不为空
	if (node != NULL)
	{
		printf("结点数据为:%d\n", node->data);
		return node->data;
	}
	return -999;
}

//先序遍历
void PreOrder(Tree* t) {
	if ((*t)!=NULL)
	{
		GetNodeData((TreeNode*)(*t));	//先获取根结点的值
		PreOrder(&(Tree*)(*t)->lchild);	//再获取左边结点的值
		PreOrder(&(Tree*)(*t)->rchild);	//再获取右边结点的值
	}
}

//中序遍历
void InOrder(Tree* t) {
	if ((*t) != NULL)
	{
		InOrder(&(Tree*)(*t)->lchild);	//先获取左边结点的值
		GetNodeData((TreeNode*)(*t));	//再获取根结点的值
		InOrder(&(Tree*)(*t)->rchild);	//再获取右边结点的值
	}
}

//后序遍历
void PostOrder(Tree* t) {
	if ((*t) != NULL)
	{
		PostOrder(&(Tree*)(*t)->lchild);	//先获取左边结点的值
		PostOrder(&(Tree*)(*t)->rchild);	//再获取右边结点的值
		GetNodeData((TreeNode*)(*t));	//再获取根结点的值
	}
}

//层序遍历
bool LevelOrder(Tree* t) {
	TreeNode* tempNode;	//临时结点
	QHead q;	//创建辅助队列
	InitQueue(&q);	//初始化辅助队列
	EnQueue(&q, (*t));	//根节点数据入队
	while (q.size!=0)
	{
		tempNode = DeQueue(&q);
		GetNodeData(tempNode);	//结点出队并获取结点的值
		if (tempNode->lchild!=NULL)
		{
			EnQueue(&q, tempNode->lchild);	//将结点的左子树压入队列
		}
		if (tempNode->rchild!=NULL)
		{
			EnQueue(&q, tempNode->rchild);	//将结点的右子树压入队列
		}
	}
	return true;
}

//构建二叉树
bool CreateBiTree(Tree* t) {
	ElemType tempdata;	//存放临时存储数据
	scanf("%d", &tempdata);	//读取输入数据
	if (tempdata==-999)
	{
		(*t) = NULL;
	}
	else
	{
		(TreeNode*)(*t) = (TreeNode*)malloc(sizeof(TreeNode));	//新结点生成内存空间
		(*t)->data = tempdata;	//结点赋值
		CreateBiTree(&(*t)->lchild);	//创造左子树
		CreateBiTree(&(*t)->rchild);	//创造右子树
	}
	return true;
}

//程序入口
int main() {
	Tree t = NULL;	//声明二叉树
	InitTree(&t);	//初始化二叉树
	printf("请输入二叉树数据:\n");
	CreateBiTree(&t);	//创建二叉树
	printf("创建二叉树完成\n");
	printf("=====先序遍历二叉树=====\n");
	PreOrder(&t);	//先序遍历二叉树
	printf("=====中序遍历二叉树=====\n");
	InOrder(&t);
	printf("=====后序遍历二叉树=====\n");
	PostOrder(&t);
	printf("=====层序遍历二叉树=====\n");
	LevelOrder(&t);
}

我代码创建二叉树采用的逻辑是先序遍历创建二叉树，所以创建二叉树的结构如下图：

image-20220827003935280

运行结果如下：

image-20220827002636196

线索二叉树

我们在创建和使用二叉树的时候，会发现一个问题，对于一个 $n$ 个结点的二叉树，其叶子结点和度为 1 的结点总共空出来 $n+1$ 个指针，我们将这些指针利用起来从而形成的新树称为线索二叉树。

线索二叉树通过先序/中序/后序遍历将其空指针指向其遍历的前一个结点，进而线程一个“线性表”，如下图所示：

image-20220827005713725

图片来源：王道《数据结构》，图中使用的是中序遍历线索化成功的线索二叉树

由于不同的遍历方式，自然会产生先序/中序/后续线索二叉树。

线索二叉树的存储结构

1
2
3
4
5
6
7
8
#define ElemType int

//链式存储
typedef struct TreeNode {
	ElemType data;	//结点存储的数据
	struct TreeNode* lchild, * rchild;	//左孩子和右孩子的指针
	int ltag, rtag;	//左，右线索标识，0表示为结点，1表示线索
}TreeNode, * Tree;

先序线索二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//线索化
bool ThreadTree(TreeNode* node) {
	if (node != NULL)
	{
		if (node->lchild == NULL)
		{
			node->lchild = pre;	//设置结点前驱线索
			node->ltag = 1;
		}
		if (pre != NULL && pre->rchild == NULL)
		{
			pre->rchild = node;	//设置结点后继线索
			pre->rtag = 1;
		}
		pre = node;
		return true;
	}
	else
	{
		return false;
	}
}

//先序线索化
bool PreThread(Tree* t) {
	if ((*t) != NULL)
	{
		ThreadTree((TreeNode*)(*t));	//再获取根结点的值
		if ((*t)->ltag==0)
		{
			PreThread(&(Tree*)(*t)->lchild);	//先获取左边结点的值
		}
		PreThread(&(Tree*)(*t)->rchild);	//再获取右边结点的值
	}
}

//创建先序线索化
void CreatPreThread(Tree* t) {
	pre = NULL;	//初始化全局变量指针
	if (t != NULL)
	{
		PreThread(t);	//中序线索化
		//需要最后处理一下最后一个结点
		if (pre == NULL)
		{
			pre->rchild = NULL;
			pre->rtag = 1;
		}
	}
}

中序线索二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//中序线索化
bool InThread(Tree* t) {
	if ((*t) != NULL)
	{
		InThread(&(Tree*)(*t)->lchild);	//先获取左边结点的值
		ThreadTree((TreeNode*)(*t));	//再获取根结点的值
		InThread(&(Tree*)(*t)->rchild);	//再获取右边结点的值
	}
}

//创建中序线索化
void CreatInThread(Tree* t) {
	pre = NULL;	//初始化全局变量指针
	if (t!=NULL)
	{
		InThread(t);	//中序线索化
		//需要最后处理一下最后一个结点
		if (pre==NULL)
		{
			pre->rchild = NULL;
			pre->rtag = 1;
		}
	}
}

后续线索二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//后序线索化
bool PostThread(Tree* t) {
	if ((*t) != NULL)
	{
		PostThread(&(Tree*)(*t)->lchild);	//先获取左边结点的值
		PostThread(&(Tree*)(*t)->rchild);	//再获取右边结点的值
		ThreadTree((TreeNode*)(*t));	//再获取根结点的值
	}
}

//创建后序线索化
void CreatPostThread(Tree* t) {
	pre = NULL;	//初始化全局变量指针
	if (t != NULL)
	{
		PostThread(t);	//中序线索化
		//需要最后处理一下最后一个结点
		if (pre == NULL)
		{
			pre->rchild = NULL;
			pre->rtag = 1;
		}
	}
}

线索化代码示例

此处拿中序线索化二叉树示例，运行代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main() {
	Tree t = NULL;	//声明二叉树
	InitTree(&t);	//初始化二叉树
	printf("请输入二叉树数据:\n");
	CreateBiTree(&t);	//创建二叉树
	printf("创建二叉树完成\n");
	printf("=====先序遍历二叉树=====\n");
	PreOrder(&t);	//先序遍历二叉树
	printf("=====中序遍历二叉树=====\n");
	InOrder(&t);
	printf("=====后序遍历二叉树=====\n");
	PostOrder(&t);
	printf("=====层序遍历二叉树=====\n");
	LevelOrder(&t);
	printf("=====中序线索化二叉树=====\n");
	CreatInThread(&t);
}

我创建的二叉树图示如下，蓝色为应该正确的线索，黑色为二叉树原貌。

image-20220827023744191

运行结果：

image-20220827023327898

上图红色为根节点，绿色为根节点的子节点，紫色是新建立的线索，可以得知线索和预测的正确二叉树线索一致。

树的存储结构

前面讨论的是二叉树的存储结构，现在来说明对于一般的树来说如何存储，对于普通的树来说可以存在多个不限于两个的子节点，可以通过如下的方式来存储：

  • 双亲表示法
  • 孩子表示法
  • 孩子兄弟表示法

双亲表示法

每个结点都存在自己的父节点（根节点除外），所以可以通过顺序存储的方式来声明一个空间来存储每个结点的双亲，存储结构代码示例：

1
2
3
4
5
6
7
8
9
10
11
#define MaxSize 100	//最大结点数
#define ElemType int
typedef struct {
	ElemType data;
	int parent;	//父节点的位置
}PNode;

typedef struct {
	PNode p[MaxSize];	//存放结点
	int n;	//结点数目
}PTree;

孩子表示法

孩子表示法是采用了顺序存储和链式存储结合方法来实现的，它通过将结点存储指向第一个孩子（左孩子）的指针，然后让孩子指向自己另外的孩子，如此反复，如下图所示：

image-20220827030432143 image-20220827030356923

图片来源：《大话数据结构》

孩子兄弟表示法

可以采用纯链式的存储方式，存储结构代码示例：

1
2
3
4
5
6
7
#define ElemType int

//链式存储
typedef struct TreeNode {
	ElemType data;	//结点存储的数据
	struct TreeNode* firstChild, * nextChild;	//左孩子和堂兄弟的指针
}TreeNode, * Tree;

图示关系为：

image-20220827030305362

图片来源：王道《数据结构》

树和森林的遍历

树的遍历

树的遍历可以分为如下三种：

  • 先根遍历（广度优先遍历）：若树非空，先访问根结点，再依次对每棵子树进行先根遍历。
  • 后根遍历（深度优先遍历）：若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点。
  • 层次遍历：同二叉树层次遍历，需要使用队列作为辅助

森林的先序遍历

森林的遍历可以分为如下两种：

  • 先序遍历森林：森林非空，则访问第一棵树根节点，然后访问根节点的左右子树，如此递归。最终效果同先根遍历。
  • 中序遍历森林：最终效果同后根遍历。

哈夫曼树

  • 结点的权：结点的某些现实含义。

  • 结点的带权路径长度：从树的根节点到该结点的路径长度与该结点上权值的乘积。

  • 树的带权路径长度：树中所有叶子结点的带权路径长度之和（WPL，Weighted Path Length）

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

哈夫曼编码

利用哈夫曼带权路径长度的最小值，构造哈夫曼编码可以进行相关数据的压缩，懒得说明了，自行查阅相关资料吧，理解起来没什么难度。

image-20220827033036414