一.树的概念和结构

1.树的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

1. 有一个特殊的结点，称为根结点，根节点没有前驱结点。
2. 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。
   
   注意：树形结构中，子树之间不能有交集，否则就不是树形结构。
   

上图就不是树：

1. 子树是不相交的
2. 除了根节点外，每个节点有且仅有一个父节点
3. 一个n个节点的树有n-1条边

2.树有关的基本概念

1. 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6
2. 叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点
3. 非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G…等节点为分支节点
4. 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
5. 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
6. 兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
7. 树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6
8. 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
9. 树的高度或深度：树中节点的最大层次； 如上图：树的高度为4
10. 堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
11. 节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
12. 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
13. 森林：由m（m>0）棵互不相交的树的集合称为森林；

3.树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既要保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的左孩子右兄弟表示法。

typedef int DataType;
struct Node
{
 struct Node* _firstChild1; // 第一个孩子结点
 struct Node* _pNextBrother; // 指向其下一个兄弟结点
 DataType _data; // 结点中的数据域
};
1
2
3
4
5
6
7

如上图所示：
A指向它左边的孩子B，而左边的孩子B指向它右边的兄弟C
B指向它左边的孩子D，而左边的孩子D指向它右边的兄弟E，E又指向它右边的兄弟F，这样继续链接下去，整个树就能很有规律的表示出来。

二.二叉树的概念和结构

1.概念

一棵二叉树是结点的一个有限集合，该集合：

1. 或者为空
2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

从上图可以看出：

1. 二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

对于任意的二叉树都是由以下几种情况复合而成的：

2.特殊的二叉树

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是2^k-1，则它就是满二叉树。
   

2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。简单来讲:完全二叉树是第k-1层全部排满,第k层从左到右排列节点的二叉树.
   

3.二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h-1 .
3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有n0 ＝n2 ＋1
4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log(n+1) . (ps： 是log以2为底，n+1为对数)
5. 高度为h的完全二叉树,节点数量的范围为[2^(h-1),2^h-1]

4.二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构

1. 顺序存储
   顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中只有堆才会使用数组来存储，下文会进行堆的讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
   
2. 链式存储
   二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是，链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，本篇实现采用二叉链。
   

二叉链:

typedef int BTDataType;
struct BinaryTreeNode
{
 struct BinTreeNode* _pLeft; // 指向当前节点左孩子
 struct BinTreeNode* _pRight; // 指向当前节点右孩子
 BTDataType _data; // 当前节点值域
}
1
2
3
4
5
6
7

三叉链

// 三叉链
struct BinaryTreeNode
{
 struct BinTreeNode* _pParent; // 指向当前节点的双亲
 struct BinTreeNode* _pLeft; // 指向当前节点左孩子
 struct BinTreeNode* _pRight; // 指向当前节点右孩子
 BTDataType _data; // 当前节点值域
}；
1
2
3
4
5
6
7
8

三.二叉树顺序结构及实现

1.什么是堆

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

堆的概念：

如果有一个关键码的集合K = { k₀，k₁ ，k₂ ，……，k_n-1 }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：K_i <=K_2i+1 且K_i <=K_2i+2 ( K_i >=K_2i+1 且 K_i>=K_2i+2 ) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一棵完全二叉树
  

2.堆的实现

函数接口 ：

typedef int HPDataType;
typedef struct Heap
{
 HPDataType* _a;
 int _size;
 int _capacity; 
}Heap;
// 堆的构建
void HeapInitArray(HP* php, int* a, int n);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

（1）向上调整算法

当我们要在堆中添加数据时，我们的做法是先将数据data插入到堆的尾部，再将data进行向上调整，直到它到达合适的位置：

如图，现在要将data=60插入到一个大根堆中

第一步：将60插入到根的末尾，及数组的的末尾

第二步：比较60与它父节点的大小，如果60大于父亲，则交换位置。

第三步：继续比较60与父亲的值，如果大于父亲则交换位置，直到60小于父节点为止。

这就是向上调整算法，来看下代码实现：

void AdjustUp(HPDataType* a, int child)
{
//根据数组的存储结构推出父子下标的关系
int parent = (child - 1) / 2;

while (child > 0)
{
//建大堆用'>'，小堆用'<'
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
 
void HeapPush(Heap* php, HPDataType data)
{
assert(php);
//如果容量不足就扩容
if (php->size == php->capacity)
{
int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)*newCapacity);
 
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
php->a = tmp;
php->capacity = newCapacity;
}
//添加数据
php->a[php->size] = data;
php->size++;
//将新入堆的data进行向上调整
AdjustUp(php->a, php->size-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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

（2）向下调整算法

当我们要删除堆顶的数据时，我们不能像往常的数组那样进行头删。
因为数组在进行头删时，要将从第二个位置起的后面的所有元素都向前挪移，如下图所示：

如图所示：此时这个二叉树就不是堆了，破坏了堆的结构。
这时候就要用到向下调整算法了，我们依然是删除堆顶的数据：

第一步：交换堆顶与堆尾的值，并将堆的Size–（相当于删除了末尾的元素）

第二步：对现在的堆顶即10进行向下调整，找出10的两个孩子中值最大的那个，如果10小于该数字就与其进行交换。

继续循环第二步，直到10大于它的两个孩子为止。
代码实现：

void AdjustDown(HPDataType* a, int n, int parent)
{
assert(a);
//先默认较大的为左孩子
int child = parent * 2+1;
while (child<n)
{
//如果右孩子比左孩子大，就++
if (child + 1 < n&&a[child] < a[child + 1])
{
child++;
}
//建大堆用'>'，小堆用'<'
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
 
void HeapPop(Heap* php)
{
assert(php);
assert(php->size>0);
 
//将堆顶的数据与堆尾交换
Swap(&php->a[0], &php->a[php->size - 1]);
//弹出堆尾数据
php->size--;
//将此时堆顶的data向下调整
AdjustDown(php->a, php->size, 0);
}
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

特别注意：不管是向上调整还是向下调整，都得满足一个前提：

1. 向上调整：进行向上调整的时候，该位置之前的所有数据已经是一个堆了。
2. 向下调整：进行向下调整的时候，该位置的左子树和右子树都已经是堆了。

（3）如何建堆

int a[] = {1,5,3,8,7,6};
1

现在有一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。

1. 如果根节点左右子树都是堆，那么我们可以直接向下调整根节点。
2. 如果整个数组都不是堆，我们可以从倒数的第一个非叶子节点的子树开始向下调整，一直调整到根节点，就可以调整成堆。

第一步：初始化堆

第二步：从倒数的第一个非叶子节点的子树开始向下调整，一直调整到根节点。

代码实现：

void HeapCreate(Heap* php, HPDataType* a, int n)
{
php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
if (php->a == NULL)
{
perror("malloc fail");
exit(-1);
}
//将数组的内容全部拷贝到php->a中
memcpy(php->a, a, sizeof(HPDataType) * n);
php->size = php->capacity = n;
 
//建堆算法
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(php->a, n, i);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

（4）向下调整建堆的时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

因此，建堆的时间复杂度为O(N)。

3.堆的应用

（1）堆排序

前面介绍了向下调整算法，我们就用向下调整算法来完成堆排序。

堆排序的主要步骤为：

1. 首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆顶

2. 将堆顶的数与堆尾的数交换，此时，堆尾的数为最大值，剩余待排序数组个数为n-1

3. 将堆顶的数进行向下调整，剩余的n-1个数再构造成大根堆，再将堆顶数与n-1位置的数交换，如此反复执行，便能得到有序数组

注意：

• 升序，建大根堆
• 降序，建小根堆

本文排序为升序，建大根堆
如下图所示：

代码实现：

void HeapSort(int* a, int n)
{
//向上建堆
//for (int i = 0; i < n; i++)
//{
//AdjustUp(a, i);
//}
 
//向下建堆
for (int i = n - 1; i >= 0; i--)
{
AdjustDown(a, n, i);
}

    //升序建大堆，降序建小堆
//排序
int end = n-1;
while (end)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
end--;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

堆排序的时间复杂度是多少？

因为上文计算了向下调整算法的时间复杂度为O(N)，但是最坏的情况下堆的最后一层的数据都要与堆顶交换，也就是说最后一层的数据都要进行一次向下调整算法，而堆的最后一层节点数是所有结点数的一半，因此可以估算出堆排序的时间复杂度为O(N*logN)。

（2）用堆来解决Top-K问题

什么是Top-K问题？

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前K个元素来建堆
   前k个最大的元素，则建小堆
   前k个最小的元素，则建大堆

2. 用剩余的N-K个元素依次与堆顶元素来比较，若大于（小于）堆顶元素，则赋值给堆顶元素，并向下调整。

3. 将剩余N-K个元素依次与堆顶元素比较完之后，堆中剩余的K个元素就是所求的前K个最大（最小）的元素。

代码实现：

void PrintTopK(int* a, int n, int k)
{
Heap hp;
    //初始化堆
HeapInit(&hp);

//对数组的前K个元素进行建堆
HeapCreate(&hp, a, k);
 
//依次比较剩余N-K个元素与堆顶元素
for (int i = k; i < n; i++)
{
if (a[i] > hp.a[0])
{
//若大于则赋值
hp.a[0] = a[i];
}
//向下调整
AdjustDown(hp.a, k, 0);
}
 
//打印堆中的K个元素，即为TopK的元素
for (int i = 0; i < k; i++)
{
printf("%d ", hp.a[i]);
}
}
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

4.二叉树顺序结构(堆)实现相关源码

（1）heap.h

typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
//堆的创建
void HeapInitArray(HP* php, int* a, int n);
//堆的销毁
void HeapDestroy(HP* php);
//堆的插入
void HeapPush(HP* php, HPDataType x);
//弹出堆顶数据
void HeapPop(HP* php);
//返回堆顶数据
HPDataType HeapTop(HP* php);
//判断堆是否为空
bool HeapEmpty(HP* php);
//堆数据的个数
int HeapSize(HP* php);
//向上调整算法
void AdjustUp(HPDataType* a, int child);
//向下调整算法
void AdjustDown(HPDataType* a, int n, int parent);
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

（2）heap.c

//堆的创建
void HeapInitArray(HP* php, int* a, int n)
{
assert(php);

php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
if (php->a == NULL)
{
perror("malloc fail");
return;
}

php->size = n;
php->capacity = n;

// 建堆
for (int i = (n-2)/2; i >= 0; --i)
{
AdjustDown(php->a, php->size, i);
}
}
//堆的销毁
void HeapDestroy(HP* php)
{
assert(php);

free(php->a);
php->a = NULL;
php->capacity = php->size = 0;
}
//交换两个元素
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType x = *p1;
*p1 = *p2;
*p2 = x;
}

//向上调整算法：该位置之前的所有数据已经是一个堆了
void AdjustUp(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
//while (parent >= 0)
while(child > 0)
{
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//堆的插入
void HeapPush(HP* php, HPDataType x)
{
assert(php);

if (php->size == php->capacity)
{
HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity*2);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
php->a = tmp;
php->capacity *= 2;
}

php->a[php->size] = x;
php->size++;

AdjustUp(php->a, php->size - 1);
}

// 向下调整算法：左右子树都是大堆/小堆
void AdjustDown(HPDataType* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
// 选出左右孩子中大的那一个
if (child + 1 < n && a[child+1] < a[child])
{
++child;
}

if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//堆的弹出
void HeapPop(HP* php)
{
assert(php);
assert(!HeapEmpty(php));

// 删除数据
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;

AdjustDown(php->a, php->size, 0);
}
//返回堆顶数据
HPDataType HeapTop(HP* php)
{
assert(php);
return php->a[0];
}
//判断堆是否为空
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
//堆中元素个数
int HeapSize(HP* php)
{
assert(php);
return php->size;
}
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

四.二叉树链式结构及实现

1.二叉树遍历的方式

故名思意，链式结构要用链表存储，但在遍历二叉树之前，首先得拥有一棵二叉树。因为目前还没有学习如何构建二叉树，所以此处我们用最原始的办法——申请N个节点，将它们手动拼接为二叉树。

//二叉树节点的结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
//申请一个节点
BTNode* BuyNode(BTDataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
perror("malloc fail");
return NULL;
}

node->data = x;
node->left = NULL;
node->right = NULL;

return node;
}
//手动创建一颗二叉树
BTNode* CreatTree()
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
BTNode* node4 = BuyNode(4);
BTNode* node5 = BuyNode(5);
BTNode* node6 = BuyNode(6);


node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;

return node1;
}
int main()
{
BTNode* root = CreatTree();
}
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

注：上述代码并不是创建二叉树的方式，真正创建二叉树方式下文会详细讲解

在看二叉树基本操作前，先回顾下二叉树的概念，二叉树是：

1. 空树
2. 非空：根节点，根节点的左子树、根节点的右子树组成的。

由图可以看出，二叉树是递归定义的，下文将基于二叉树递归的性质实现二叉树的遍历。

二叉树遍历的规则一般有四种：前序遍历、中序遍历、后序遍历和层序遍历。其中，前三种较为简单且实现方式大同小异:

1. 前序遍历：先访问根节点，再遍历左右子树。
2. 中序遍历：先遍历左子树，再访问根节点，再遍历右子树。
3. 后序遍历：先遍历左子树，再遍历右子树，再访问根节点。
4. 层序遍历：自上而下，自左至右逐层访问树的结点。

简单来说：前（根，左，右），中（左，右，右），后（左，右，根）

（1）前序遍历

前序遍历：先访问根节点，再访问左子树，再访问右子树；

void PrevOrder (BTNode* root)
1

递归搜索树如下图所示：

按照递归顺序，前序遍历的结果是：

1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL 
1

代码实现：

void PrevOrder(BTNode* root)
{
if (root == NULL)
{ 
printf("NULL ");//空节点用 NULL 表示
return; 
}
 
printf("%d ", root->data);//前序在前
PrevOrder(root->left);
PrevOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12

运行结果：

与上述逻辑分析得出的结果一致。

（2）中序遍历

中序遍历：先遍历左子树，再访问根节点，再遍历右子树。

void InOrder(BTNode* root)
1

递归搜索树如下图所示：

按照递归顺序，中序遍历的结果是：

NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL
1

代码实现：

void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
 
InOrder(root->left);
printf("%d ", root->data);//中序在中
InOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12

运行结果：

与上述逻辑分析得出的结果一致。

（3）后序遍历

后序遍历：先遍历左子树，再遍历右子树，再访问根节点。

void PostOrder(BTNode* root);
1

递归搜素树参考前序遍历与中序遍历的分析。
按照分析结果，后续遍历的结果是：

NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4 1
1

代码实现：

void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
 
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);//后序在后
}
1
2
3
4
5
6
7
8
9
10
11
12

运行结果：

与上述逻辑分析得出的结果一致。

（4）层序遍历

层序遍历：自上而下，自左至右逐层访问树的结点。

void BinaryTreeLevelOrder(BTNode* root);
1

层序遍历与前面三者不同，我们将采用非递归的方式实现，虽然实现方法并不难，但是实现的思路将是后面学习BFS（广度优先遍历）算法的重要基础。
实现思路：
假设下图所示二叉树：
。
层序遍历的结果应为：

1 2 4 3 5 6
1

我们使用队列，首先将根节点1先入队，然后根节点左右孩子2，4入队，接着根节点出队，然后将节点2，4分别看成根节点重复上述步骤直到访问完所有节点：

代码实现：
（队列有疑惑的可以戳戳这里小小学习一下~）

//队列的初始化
void QueueInit(Queue* pq);
//释放malloc出的内存
void QueueDestroy(Queue* pq);
//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//获取队头的数据
QDataType QueueFront(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);
 
//层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
 
if (root)
QueuePush(&q, root);
 
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
printf("%d ", front->data);

QueuePop(&q);
 
if(front->left)
QueuePush(&q, front->left);
if(front->right)
QueuePush(&q, front->right);
}
 
printf("\n");
QueueDestroy(&q);
}
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

2.二叉树相关接口函数

//二叉树节点个数
int TreeSize(BTNode* root);
//二叉树的深度
int TreeHeight(BTNode* root);
//二叉树第k层的节点个数
int TreeKLevel(BTNode* root, int k);
//查找二叉树值为x的节点
BTNode* TreeFind(BTNode* root, BTDataType x);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
1
2
3
4
5
6
7
8
9
10

在实现上述函数的时候，我们一定要抓住和利用二叉树递归定义这一特点，可以很好的帮助我们理解和简化代码：

（1）二叉树节点的个数

左树节点个数+右树节点个数+根节点自身

int TreeSize(BTNode* root)
{
return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
1
2
3
4

（2）二叉树的深度

比较左树和右树哪个更深，返回深的那一个

int TreeHeight(BTNode* root)
{
if (root == NULL)
return 0;

//要先保存一下左右的值，防止比较大小的时候重复递归，增加不必要的时间复杂度
int leftHeight = TreeHeight(root->left);
int rightHeight = TreeHeight(root->right);

return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
1
2
3
4
5
6
7
8
9
10
11

（3）二叉树第k层节点的个数

第k层节点个数等于上一层所有节点的左孩子加上右孩子的个数

int TreeKLevel(BTNode* root, int k)
{
assert(k > 0);

if (root == NULL)
return 0;
//k是1，表示遍历到了祖宗节点，该层只有一个
if (k == 1)
return 1;

return TreeKLevel(root->left, k - 1)
+ TreeKLevel(root->right, k - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

（4）查找二叉树值为x的节点

递归查找根，左孩子，右孩子是否有匹配上的

BTNode* TreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;

if (root->data == x)
return root;
//查找左孩子并返回
BTNode* lret = TreeFind(root->left, x);
//非空，表示找到了，返回左孩子
if (lret)
return lret;
//查找右孩子并返回
BTNode* rret = TreeFind(root->right, x);
//非空，表示找到了，返回右孩子
if (rret)
return rret;

return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

（5）二叉树销毁

用后序遍历的方式销毁，防止原树结构破坏，找不到左右孩子节点

// 二叉树销毁
void TreeDestory(BTNode* root)
{
if (root == NULL)
return;

TreeDestory(root->left);
TreeDestory(root->right);
free(root);
}
1
2
3
4
5
6
7
8
9
10

3.二叉树链式结构实现相关源码

（1）Binary.h

typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;

//手动创建一颗二叉树
BTNode* BuyNode(BTDataType x);
BTNode* CreatTree();
//前序遍历
void PreOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历
void PostOrder(BTNode* root);
//层序遍历
void LevelOrder(BTNode* root);
//二叉树节点的个数
int TreeSize(BTNode* root);
//二叉树的深度
int TreeHeight(BTNode* root);
//二叉树第k层节点的个数
int TreeKLevel(BTNode* root, int k);
//查找二叉树值为x的节点
BTNode* TreeFind(BTNode* root, BTDataType x);
// 二叉树销毁
void TreeDestory(BTNode* root);
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

（2）Binary.c

//手动创建一颗二叉树
BTNode* BuyNode(BTDataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
perror("malloc fail");
return NULL;
}

node->data = x;
node->left = NULL;
node->right = NULL;

return node;
}

BTNode* CreatTree()
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
BTNode* node4 = BuyNode(4);
BTNode* node5 = BuyNode(5);
BTNode* node6 = BuyNode(6);
BTNode* node7 = BuyNode(7);


node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
node3->right = node7;

return node1;
}
//前序遍历
void PreOrder(BTNode* root) {
if (root == NULL) {
printf("NULL ");
return;
}

printf("%d ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
//中序遍历
void InOrder(BTNode* root) {
if (root == NULL) {
printf("NULL ");
return;
}

InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
//后序遍历
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}

PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}
//层序遍历
//(这里要用到队列的相关知识，具体代码就不写到博客里了)
void LevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q, root);

while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%d ", front->data);

if(front->left)
QueuePush(&q, front->left);

if (front->right)
QueuePush(&q, front->right);
}

QueueDestroy(&q);
}
//二叉树节点的个数
int TreeSize(BTNode* root)
{
return root == NULL ? 0 : 
TreeSize(root->left) 
+ TreeSize(root->right) 
+ 1;
}
//二叉树的深度
int TreeHeight(BTNode* root)
{
if (root == NULL)
return 0;

int leftHeight = TreeHeight(root->left);
int rightHeight = TreeHeight(root->right);

return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
//二叉树第k层节点的个数
int TreeKLevel(BTNode* root, int k)
{
assert(k > 0);

if (root == NULL)
return 0;

if (k == 1)
return 1;

return TreeKLevel(root->left, k - 1)
+ TreeKLevel(root->right, k - 1);
}
//找到二叉树值为x的节点
BTNode* TreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;

if (root->data == x)
return root;

BTNode* lret = TreeFind(root->left, x);
if (lret)
return lret;

BTNode* rret = TreeFind(root->right, x);
if (rret)
return rret;

return NULL;
}
// 二叉树销毁
void TreeDestory(BTNode* root)
{
if (root == NULL)
return;

TreeDestory(root->left);
TreeDestory(root->right);
free(root);
}
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

---

本篇到此结束，码文不易，还请多多支持哦！！