C语言实现二叉树、堆、堆排序（二万字总结）

一、树的概念及结构

1.1 树的概念

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

• 有一个特殊的结点，称为根结点，根节点没有前驱结点;
• 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。
• 因此，树是递归定义的。

注意：树形结构中，子树之间不能有交集，否则就不是树形结构

1.2 树的相关概念

1.3 树的表示

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

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

二、二叉树概念及结构

2.1 概念

二叉树是一种树形结构，其中每个节点最多有两个子节点，通常被称为左子节点和右子节点。

一棵二叉树由一个根节点加上两棵别称为左子树和右子树的二叉树组成，左右子树可以为空:

注意：

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

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

---

现实中的二叉树：

2.2 特殊的二叉树

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是2^k^-1，则它就是满二叉树。
2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
   简单来说，对于一个深度为K的二叉树，它的前k-1层为满的，第K 层所有的结点都连续集中在最左边。
   
   这个树就不是完全二叉树：
   

2.3 二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 2^i-1 个结点；
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h-1;
3. 对任何一棵二叉树, 如果度为 0 的叶结点个数为n₀, 度为 2 的分支结点个数为n₂,则有n₀＝ n₂＋1;

假设度为 1 的叶节点个数为n₁
当一个度为 0 的节点变为度为 1 的节点时，n₁++，n₀不变
当一个度为 1 的节点变为度为 2 的节点时，n₁- -，n₂++，n₀++
因此每多一个度为 2 的节点，就会多一个度为 0 的节点，所以n₀与n₂的关系是不变的;
从只有跟节点开始算，此时 n₀ = 1，n₂ = 0，那不管之后怎么变化，n₀增加一个n₂也增加一个，n₀减少一个n₂也减少一个，那么n₀始终比n₂多1，当然空树除外。

4. 若规定根节点的层数为1，具有n个结点的满二叉树，它的深度 h = log₂(n + 1) (ps：log₂(n + 1)是log以2为底，n+1为对数)

设深度为 h ，则此满二叉树节点个数 n 为 2⁰+2¹+2²+…+2^h-1，等比数列推出 h 即可。

5. 对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从 0 开始编号，则对于序号为 i 的结点有：
   • 若 i >0，i 位置节点的双亲序号：(i-1)/2；i=0，i 为根节点编号，无双亲节点 (ps:这条很重要，建堆的时候要用到)
   • 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
   • 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

2.4 二叉树的存储结构

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

1. 顺序存储
   顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。
   二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
   
2. 链式存储
   二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。
   通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链，当前学习中一般都是二叉链，后面的高阶数据结构如红黑树等会用到三叉链。
   
   

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
	struct BinTreeNode* _pLeft; // 指向当前节点左孩子
	struct BinTreeNode* _pRight; // 指向当前节点右孩子
	BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
	struct BinTreeNode* _pParent; // 指向当前节点的双亲
	struct BinTreeNode* _pLeft; // 指向当前节点左孩子
	struct BinTreeNode* _pRight; // 指向当前节点右孩子
	BTDataType _data; // 当前节点值域
}；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

三、二叉树的顺序结构及实现

3.1 二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。

我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

3.2 堆的概念及结构

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

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

简单来讲，堆是一颗完全二叉树，且父节点总是大于等于其子节点或小于等于其子节点。而兄弟节点之间没有要求。

代码里实现的都是存储结构，脑海里想象成逻辑结构。

typedef int HPDataType;//方便修改数据类型
typedef struct Heap
{
    HPDataType* _a;
        int _size;//实际存储的有效元素个数
        int _capacity;//数组容量
}Heap;
1
2
3
4
5
6
7

3.3 堆的实现

3.3.1 堆向下调整算法与向上调整算法

向上调整算法：

向上调整算法的作用是通过从下到上的算法排序，将一个堆变成最小堆或最大堆。通常在堆的插入中用到。
向上调整算法的一个条件：一个节点的祖先必须是堆才能向上调整。

例如向一个最小堆中插入10，就是将和它的父节点比较，如果比父节点小就交换，继续和父节点比较，直到比父节点大或成为根节点为止。

根据2.3中第5条性质，父节点parent = (child - 1)/2，因此在存储结构中，我们可以这样找到一个子节点的父节点。因为要将一个节点向上调整（与父节点比较），所以形参中需要传子节点。
以下的parent、child表示元素下标，不是元素本身。

void Swap(HPDataType* p1, HPDataType* p2)//交换函数
{
    HPDataType tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
1
2
3
4
5
6

void AdjustUp(HPDataType* a, int child)
{
    int parent = (child - 1) / 2;//通过子项找到父亲
    while (child > 0)
    {
    //因为建的是小堆，孩子比父亲小就要交换，向上调整
        if (a[parent] > a[child])
        {
            Swap(&a[parent], &a[child]);
            child = parent;//更新孩子的下标
            parent = (child - 1) / 2;//更新父亲的下标
        }
        else
        {
        //1. child = 0退出即孩子已调整到跟节点
        //2. 孩子比父亲大，不需要交换，直接退出
            break;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

向下调整算法：

向下调整算法是在建堆的过程中，通过不断调整堆顶元素的位置，使其满足“堆的性质”的一种算法。
向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

现在给出一个数组，它的左右子树都是一个小堆，因此我们可以通过向下调整算法把它变成一个小堆。

int array[] = {27,15,19,18,28,34,65,49,25,37};
1

实现的思路就是这样的：

需要注意的是，向下调整算法要考虑兄弟节点，父节点交换的是子节点中较小的值，因为要保证交换后的父节点小于等于子节点，如果遇到两个子节点都比其大就停止。
建大堆则相反。

同样根据2.3中第5条性质，左孩子节点leftchild = parent*2+1，右孩子节点rightchild = parent*2+1，再对左右孩子进行比较。实际上，我们只用找出左孩子，如果左孩子是a[child]，那么右孩子一定是a[child+1]。
因为向下调整，传参传父节点，n表示节点总数，防止孩子越界。

void AdjustDown(HPDataType* a, int n, int parent)
{
    int child = parent * 2 + 1;//找到左孩子
    while (child < n)//判断左孩子是否存在，因为在完全二叉树中，左孩子如果不存在，右孩子一定不存在
    {
    //判断右孩子是否存在，如果不存在child默认为左孩子
    //如果右孩子存在且比左孩子小，child++就表示右孩子了
        if (child + 1 < n && a[child] > a[child + 1])
        {
            child++;
        }
        //用较小的孩子与父亲比较
        if (a[parent] > a[child])
        {
            Swap(&a[parent], &a[child]);
            parent = child;//更新
            child = parent * 2 + 1;
        }
        else
        {
        //孩子不存在退出，或无需交换退出
            break;
        }
    }
}
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

3.3.2 堆的创建

讲完了向上/向下调整算法的原理，那该怎么把一个普通的数组建成堆呢？

方法一：向上调整建堆（不推荐）

以建大堆为例，从一个元素开始，它可以看作一个堆，那么就可以对它的孩子进行向上调整，调整之后能看做一个堆，于是可以继续对后面的元素向上调整…
总之，从前往后遍历，向上调整。

void HeapCreate(Heap* hp, HPDataType* a, int n)
{
    assert(hp);
    hp->_a = a;//这样堆中的数组与传递的是同一块，节省内存空间
    for (int i = 1; i < n; i++)
    {
        AdjustUp(hp->_a, i);
    }
    hp->_size = hp->_capacity = n;
}
1
2
3
4
5
6
7
8
9
10

---

方法二：向下调整建堆（推荐）

向下调整与向上调整不同，跟节点的子树并不是堆，那该怎么调整呢？

这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

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

从倒数第一个父节点开始，它的左右子树最多只有一个节点，因此本身就能看做一个堆，向下调整过后，它也变成了一个堆，因此它的父节点也能够进行向下调整了，直到调整到跟节点为止。

void HeapCreate(Heap* hp, HPDataType* a, int n)
{
    assert(hp);
    hp->_a = a;
    //n-1才是最后一个子节点的下标,不是n,所以父节点为(n-1-1)/2
    for (int i = (n-1-1)/2; i >=0 ; i--)
    {
        AdjustDown(hp->_a,n, i);
    }
    hp->_size = hp->_capacity = n;
}
1
2
3
4
5
6
7
8
9
10
11

3.3.3 建堆时间复杂度

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

1. 向上调整建堆：

因此，向上调整建堆的时间复杂度为：O(N*logN)

---

2. 向下调整建堆：

向下调整建堆的时间复杂度为：O(N)

---

综上所述，向下调整建堆比向上调整建堆的时间复杂度要小，这意味着向下调整建堆要快得多。
因此，通常建堆默认为向下调整建堆，其时间复杂度为O(N)。

3.3.4 堆的插入

堆的插入指向堆中插入一个元素，使用向上调整算法，之前已经提过，此处不多赘述。

void HeapPush(Heap* hp, HPDataType x)
{
    assert(hp);
    if (hp->_size == hp->_capacity)//数组容量不够需要扩容，当然这个数组得是动态开辟的
    {
        int newcapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;
        HPDataType* tmp = (HPDataType*)realloc(hp->_a, newcapacity);
        if (tmp == NULL)
        {
            perror("realloc fail");
            return;
        }
        hp->_a = tmp;
        hp->_capacity = newcapacity;
    }
    hp->_a[hp->_size] = x;//尾部插入
    AdjustUp(hp->_a, hp->_size);//向上调整
    hp->_size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3.3.5 堆的判空

字面意思，判断堆中还有没有数据，1为空，0为非空。

int HeapEmpty(Heap* hp)
{
    assert(hp);
    return hp->_size == 0 ? 1 : 0;
}
1
2
3
4
5

3.3.6 堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
因为删除普通的数据没有意义，要么就删除最大的，要么删除最小的，视大堆小堆而定。

void HeapPop(Heap* hp)
{
    assert(hp);
    assert(!HeapEmpty(hp));
    Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
    hp->_size--;
    AdjustDown(hp->_a, hp->_size, 0);//重新调整为堆
}
1
2
3
4
5
6
7
8

3.3.7 堆的完整代码实现

Heap.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int HPDataType;
typedef struct Heap
{
	    HPDataType* _a;
        int _size;
        int _capacity;
}Heap;

// 堆的构建
void HeapCreate(Heap* hp, HPDataType* 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
22
23
24
25
26
27
28

Heap.c

#include "Heap.h"
void Swap(HPDataType* p1, HPDataType* p2)
{
    HPDataType tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

void AdjustDown(HPDataType* a, int n, int parent)
{
    int child = parent * 2 + 1;
    while (child < n)
    {
        if (child + 1 < n && a[child] > a[child + 1])
        {
            child++;
        }
        if (a[parent] > a[child])
        {
            Swap(&a[parent], &a[child]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
void AdjustUp(HPDataType* a, int child)
{
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        if (a[parent] > a[child])
        {
            Swap(&a[parent], &a[child]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}
/*void HeapCreate(Heap* hp, HPDataType* a, int n)
{
    assert(hp);
    hp->_a = a;
    for (int i = 1; i < n; i++)
    {
        AdjustUp(hp->_a, i);
    }
    hp->_size = hp->_capacity = n;
}*/
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
    assert(hp);
    hp->_a = a;
    //n-1才是最后一个子节点的下标,不是n,所以父节点为(n-1-1)/2
    for (int i = (n-1-1)/2; i >=0 ; i--)
    {
        AdjustDown(hp->_a,n, i);
    }
    hp->_size = hp->_capacity = n;
}
void HeapDestory(Heap* hp)
{
    assert(hp);
    hp->_a = NULL;
    hp->_size = 0;
    hp->_capacity = 0;
}

void HeapPush(Heap* hp, HPDataType x)
{
    assert(hp);
    if (hp->_size == hp->_capacity)
    {
        int newcapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;
        HPDataType* tmp = (HPDataType*)realloc(hp->_a, newcapacity);
        if (tmp == NULL)
        {
            perror("realloc fail");
            return;
        }
        hp->_a = tmp;
        hp->_capacity = newcapacity;
    }
    hp->_a[hp->_size] = x;
    AdjustUp(hp->_a, hp->_size);
    hp->_size++;
}

void HeapPop(Heap* hp)
{
    assert(hp);
    assert(!HeapEmpty(hp));
    Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
    hp->_size--;
    AdjustDown(hp->_a, hp->_size, 0);
}

HPDataType HeapTop(Heap* hp)
{
    assert(hp);
    assert(!HeapEmpty(hp));
    return hp->_a[0];
}

int HeapSize(Heap* hp)
{
    assert(hp);
    return hp->_size;
}

int HeapEmpty(Heap* hp)
{
    assert(hp);
    return hp->_size == 0 ? 1 : 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
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

3.4 堆的应用

3.4.1 堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

1. 建堆
   升序：建大堆
   降序：建小堆
2. 利用堆删除思想来进行排序

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

以升序为例：

升序建大堆
void AdjustDown(HPDataType* a, int n, int parent)
{
    int child = parent * 2 + 1;
    while (child < n)
    {
        if (child + 1 < n && a[child] < a[child + 1])//找到较大的那个孩子
        {
            child++;
        }
        if (a[parent] < a[child])//孩子比父亲大就向上调整
        {
            Swap(&a[parent], &a[child]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

建堆建好后，用堆删除的思想，将堆顶的元素与最后一个元素交换，再重新建堆，这时堆顶的元素即第二大的元素，再与剩下元素里最后一个元素交换，就换到了倒数第二个位置，再重复以上步骤。

void HeapSort(int* a, int n)
{
	//升序建大堆
    for (int i = (n-1-1)/2; i >= 0; i--)
    {
        AdjustDown(a, n, i);
    }
    
    int end = n - 1;//最后一个元素的下标
    while (end > 0)
    {
        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

3.4.2 TOP-K问题

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

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

• 前k个最大的元素，则建小堆
• 前k个最小的元素，则建大堆

2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

例如求前 k 个最大元素：

我们先建一个小堆，这样在这个堆中，堆顶的元素就是最小的，再用剩余的元素与堆顶的元素比较，只要遇到比它大的就交换，然后向下调整，这样每次都把堆中最小的元素交换掉，剩下的就是前 k 个最大的元素了。

void PrintTopK(int* a, int n, int k)
{
    int* kminheap = (int*)malloc(sizeof(int) * k);//建立堆的存储结构
    if (kminheap == NULL)
    {
        perror("malloc fail");
        return;
    }
    for (int i = 0; i < k; i++)
    {
      	kminheap[i] = a[i];
    }
    //建小堆
    for (int i = (k - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(kminheap, k, i);//注意向下调整函数中的符号
    }
    int val;
    for(int i = k; i < n ; i++)
    {
    	if(a[i] > kminheap[0])
    	{
    		kminheap[0] = a[i];
    		AdjustDown(kminheap, k, 0);
    	}
    }
    for (int i = 0; i < k; i++)
    {
        printf("%d ", kminheap[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
28
29
30
31

---

---

四、二叉树链式结构的实现

4.1 二叉树的链式结构

之前学习了二叉树的顺序结构，主要作用是建堆，现在来学习链式结构。

typedef int BTDataType;
//表示一个二叉树的节点
typedef struct BinaryTreeNode
{
BTDataType _data;//根的数据
struct BinaryTreeNode* _left;//左子结点
struct BinaryTreeNode* _right;//右子节点
}BTNode;
1
2
3
4
5
6
7
8

我们先手动创造一棵二叉树方便理解，之后会讲到创建二叉树的真正方式。
方便起见写一个申请节点的函数：

BTNode* BuyNode(BTDataType x)
{
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
    if (newnode == NULL)//申请空间失败
    {
        perror("malloc fail");
        return NULL;
    }
    newnode->_data = x;
    newnode->_left = NULL;
    newnode->_right = NULL;
    return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

BTNode* CreatBinaryTree()
{
	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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

再回顾下二叉树的概念，二叉树是：

1. 空树
2. 非空：根节点，根节点的左子树、根节点的右子树组成的。
   
   从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。

4.2 二叉树的遍历

4.2.1 前序、中序以及后序遍历

所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。
遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

• 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
• 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
• 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

---

前序遍历递归图解：

因此前序遍历的实际顺序是：1 - 2 - 3 - N - N - N - 4 - 5 - N - N - 6 - N - N

void BinaryTreePrevOrder(BTNode* root)
{
    if (root == NULL)//遇空则返回
    {
        printf("NULL ");
        return;
    }
    printf("%d ", root->_data);//先根
    BinaryTreePrevOrder(root->_left);//再左子树
    BinaryTreePrevOrder(root->_right);//再右子树
}
1
2
3
4
5
6
7
8
9
10
11

通过前序遍历的所有顺序一定是根、左子树右子树的关系
(1)根 - (2 - 3 - N - N - N)左子树 - (4 - 5 - N - N - 6 - N - N)右子树
1 - 2 - 3 - N - N - N - (4)根 - (5 - N - N)左子树 - (6 - N - N)右子树
1 - 2 - (3)根 - (N)左子树 - (N)右子树 - N - 4 - 5 - N - N - 6 - N - N
…

---

中序遍历递归图解：

我们可以发现，只要是从根节点递归到左子树再递归到右子树，那么它们的递归顺序是一样的，这里的前序、中序、后序遍历并不是指递归的顺序，而是打印的顺序，当然打印只是一种直观的表现形式，方便观察，把它换成赋值操作也一样的。

同样，通过中序遍历的所有顺序一定是左子树、根、右子树的关系
(N - 3 - N - 2 - N)左子树 - (1)根 - (N - 5 - N - 4 - N - 6 - N)右子树
N - 3 - N - 2 - N - 1 - (N - 5 - N)左子树 - (4)根 - (N - 6 - N)右子树
(N)左子树 - (3)根 - (N)右子树 - 2 - N - 1 - N - 5 - N - 4 - N - 6 - N
…

void BinaryTreeInOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    BinaryTreeInOrder(root->_left);//左
    printf("%d ", root->_data);//根
    BinaryTreeInOrder(root->_right);//右
}
1
2
3
4
5
6
7
8
9
10
11

---

后序遍历递归图解：

同样，通过后序遍历的所有顺序一定是左子树、右子树、根的关系，这里就不举例了。
N - N - 3 - N - 2 - N -N - 5 - N - N - 6 - 4 - 1

void BinaryTreePostOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    BinaryTreePostOrder(root->_left);
    BinaryTreePostOrder(root->_right);
    printf("%d ", root->_data);
}
1
2
3
4
5
6
7
8
9
10
11

4.2.2 层序遍历

除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

层序遍历先访问根节点，然后访问所有子节点，然后访问所有孙子节点，以此类推。

这里要用到之前学过的队列¹，遍历算法的基本步骤如下：

1. 首先，将根节点入队。
2. 当队列不为空时，取出队列的头节点，访问该节点。
3. 如果该节点的左子节点不为空，则将左子节点入队。
4. 如果该节点的右子节点不为空，则将右子节点入队。
5. 重复步骤2-4，直到队列为空。

void BinaryTreeLevelOrder(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    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);
    }
    QueueDestroy(&q);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这样根据入队的先后顺序，就完成了层序遍历。

4.3 二叉树几个功能

4.3.1 二叉树节点个数

思路：前序遍历，遇到非空节点就加1，空即为0。

int BinaryTreeSize(BTNode* root)
{
    if (root == NULL)
        return 0;
    return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
    //因为是节点的总个数，所以要加起来
}
1
2
3
4
5
6
7

4.3.2 二叉树叶子节点个数

思路：叶子节点即度为0的节点，因此我们只用统计没有子节点的节点，同样前序遍历。

int BinaryTreeLeafSize(BTNode* root)
{
    if (root == NULL)
    {
        return 0;
    }
    if (root->_left == NULL && root->_right == NULL)
    {
        return 1;
    }
    return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

1
2
3
4
5
6
7
8
9
10
11
12
13

4.3.3 二叉树第k层节点个数

思路：可以在形参中传一个变量，每向下递归一层就加1，直到等于k为止，这是一种方案。
还有更好的方案，假设k = 3，那么在第一层时k = 3，每下一层k就减1，这样当k = 1时就在第k层。

int BinaryTreeLevelKSize(BTNode* root, int k)
{
    if (root == NULL)
        return 0;
    if (k == 1)
        return 1;
    return BinaryTreeLevelKSize(root->_left,k-1) + BinaryTreeLevelKSize(root->_right,k-1);
}
1
2
3
4
5
6
7
8

4.3.4 二叉树查找值为x的节点

思路：前序遍历，找到了就返回。

一些初学者可能这样写：

if(BinaryTreeFind(root->_left, x))
return BinaryTreeFind(root->_left, x);
else return BinaryTreeFind(root->_right, x);
1
2
3

但是这种写法将查找左子树进行了2次，而通过递归消耗的时间可不止2倍这么简单，而是呈指数式地增长，大大增加了时间复杂度。

解决方法就是将节点存起来，再来判断。

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
    if (root == NULL)
        return NULL;
    if (root->_data == x)
        return root;
    BTNode* left = BinaryTreeFind(root->_left, x);
    if (left != NULL)//说明找到了
    {
        return left;
    }
    //左子树没找到，找右子树
    BTNode* right = BinaryTreeFind(root->_right, x);
    return right;//不管找没找到都能返回，要么是空，要么是节点
    //return BinaryTreeFind(root->_right, x);也可以直接返回右子树
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

4.3.5 判断二叉树是否是完全二叉树

同样用到队列，这里用到层序遍历的思路，但比层序遍历要简单一些。

我们对二叉树进行层序遍历，每遍历一个节点，就将它的左子节点和右子节点入队（不管是否为空），当出队遇到NULL的时候立刻退出。

比如这幅图，出队时遇到了NULL，节点5和节点6就留在了队列中，于是队列非空，判断为不是完全二叉树。
如果2的右子树非空，那么出队便会在3的左子树NULL处停止，这时队列里剩下的都是NULL，队列为空，判断为完全二叉树。

int BinaryTreeComplete(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    QueuePush(&q, root);
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if (front)
        {
            QueuePush(&q, front->_left);
            QueuePush(&q, front->_right);
        }
        else
        {
            break;
        }
    }
    if (QueueEmpty(&q))
    {
        QueueDestroy(&q);
        return 1;
    }
    else return 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

4.4 二叉树的创建和销毁

4.4.1 二叉树的创建

因为二叉树并没有什么要求，比如要有多少层，哪个元素放在哪个节点，是要完全二叉树还是非完全二叉树，这些都没有规定，所以没有直接创建二叉树的函数。

比如给我一个数组，可以建成这样的，也可以是这样的:

还能是这样的：

所以直接建立二叉树并没有意义，除非题目特定要求，比如：

通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树

题目明确告诉了我们前序遍历，并且把结构表示了出来，我们只需要写一个建立的函数。

char arr[] = "ABD##E#H##CF##G##";
1

pi表示的是下标，n表示的是数组的长度，需要注意的是，在传pi时应该传pi的地址而不是值，因为在递归中，通过地址改变的pi才会改变，如果是传值，在递归结束后形参就销毁了，而pi没有改变。
因此应该这样传：

int n = strlen(arr);
int i = 0;
BinaryTreeCreate(arr, n, &i);
1
2
3

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
    if ((*pi)>=n || a[*pi] == '#')//遇到'#'返回空，i自增，并判断是否越界
    {
        ++(*pi);
        return NULL;
    }
    //不为空时
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    if (root == NULL)
    {
        perror("malloc fail\n");
        return NULL;
    }
    root->_data = a[*pi];
    ++(*pi);
    root->_left = BinaryTreeCreate(a, n, pi);
    root->_right = BinaryTreeCreate(a, n, pi);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

4.4.2 二叉树的销毁

注意传二级指针，如果传一级指针，就是原二叉树的临时拷贝，销毁得传址。
注意得用后序遍历，要用跟节点找到子节点再销毁根节点。

void BinaryTreeDestory(BTNode** root)
{
    if (*root != NULL)
    {
        BinaryTreeDestory((*root)->_left);
        BinaryTreeDestory((*root)->_right);
        free(*root);
    }
}
1
2
3
4
5
6
7
8
9

---

1. 关于队列 ↩︎