[数据结构与算法]【数据结构初阶】：堆和二叉树

【数据结构初阶】：堆和二叉树

1. 树概念及结构

1.1 树的概念

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

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

1.2 树的相关概念

**节点的度：**一个节点含有的子树的个数称为该节点的度； 如上图：A的度为6

**叶节点或终端节点：**度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点

**非终端节点或分支节点：**度不为0的节点； 如上图：D、E、F、G…等节点为分支节点

**双亲节点或父节点：**若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点

**孩子节点或子节点：**一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点

**兄弟节点：**具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点（亲兄弟）

**树的度：**一棵树中，最大的节点的度称为树的度； 如上图：树的度为6

**节点的层次：**从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

**树的高度或深度：**树中节点的最大层次； 如上图：树的高度为4 （区分“度“和”高度”）

**堂兄弟节点：**双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点

**节点的祖先：**从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先

**子孙：**以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙

**森林：**由m（m>0）棵互不相交的树的集合称为森林；（并查集：多棵树构成森林）

1.3 树的表示

// 方式1：假设说明了树的度为N
struct TreeNode
{
	int data;
	struct TreeNode* subs[N];// 指针数组
}

问题：

1. 可能存在不少空间浪费
2. 万一未限定树的度是多少？

// 方式2：
typedef struct TreeNode* SLDataType;// Seqlist
struct TreeNode
{
    int data;
    Seqlist s;// 二级指针
}

**问题：**结构相对复杂

// 方式3：双亲表示法
struct TreNode
{
    int parenti;
    int data;
}

以上表示方法各有优缺点，但表示树结构最好的方法被称为***“左孩子右兄弟表示法”***

typedef int DataType;
struct Node
{
 struct Node* _firstChild1; // 第一个孩子结点(永远指向第一个孩子)
 struct Node* _pNextBrother; // 指向其下一个兄弟结点（指向孩子右边的兄弟）
 DataType _data; // 结点中的数据域
};

1.4 树在实际中的运用（表示文件系统的目录树结构）

2. 二叉树概念及结构

2.1 概念

一棵二叉树(度最大为2)是结点的一个有限集合，该集合:

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

从上图可以看出：

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

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

2.2现实中的二叉树：

2.3 特殊的二叉树：

1. **满二叉树：**一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。

? 也就是说，如果一个二叉树的层数为k，且结点总数是$2^k?1$，则它就是满二叉树。

? 等比数列求和：假设树的高度是h的满二叉树，节点总数： $2^0+2^1+2^2+...+2^{(h?1)}=2^h?1$

2. **完全二叉树：**完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

   特点：

   • 前$N?1$层都是满的

   • 最后一层不满，但是最后一层从左到右是连续的

   • 最多只有1个度为1的节点

2.4 二叉树的性质

2. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有$2^{(i?1)}$个结点
3. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是$2^h?1$
4. 对任何一棵二叉树, 如果度为0的叶子结点个数为$n_0$,度为2的分支结点个数为$n_2$,则有$n_0$=$n_2$+1(度为0的永远比度为2的多1个)
5. 若规定根节点的层数为1，具有n个结点的满二叉树的深度$h={\log }_2(n+1)$（10亿个节点满二叉树是30层：$2^{30}=10亿多$）
6. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：
   1. **若i>0，i位置节点的双亲序号：(i-1)/2；**i=0，i为根节点编号，无双亲节点
   2. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
   3. 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（B）
A 不存在这样的二叉树
B 200
C 198
D 199
2.下列数据结构中，不适合采用顺序存储结构的是（A）
A 非完全二叉树
B 堆
C 队列
D 栈

3.在具有 2n 个结点的完全二叉树中，叶子结点个数为（A）
A n
B n+1
C n-1
D n/2

4.一棵完全二叉树的节点数位为531个，那么这棵树的高度为（B）
A 11
B 10
C 8
D 12

5.一个具有767个节点的完全二叉树，其叶子节点个数为（B）
A 383
B 384
C 385
D 386

2.5 二叉树的存储结构

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

1. 顺序存储

   顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一棵二叉树。

• 假设parent是父亲节点在数组中下标

leftchild = parent$*$2+1

rightchild = parent$*$2+2

• 假设孩子的下标是child，不管左孩子还是右孩子

parent = (child-1)$/$2

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; // 当前节点值域
}；

3. 二叉树的顺序结构及实现

3.1 二叉树的顺序结构

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

操作系统对内存划分：栈（栈帧）、堆（malloc）、静态区（静态数据、全局数据）、常量区（常量数据）

数据结构里也有堆（完全二叉树）和栈，和操作系统的定义完全没有关系

3.2 堆的概念及结构

堆总是一棵完全二叉树

**大堆：**树中一个树及子树中，任何一个父亲都大于等于孩子

**小堆：**树中一个树及子树中，任何一个父亲都小于等于孩子

堆的应用相关问题

1、堆排序

2、topK问题：在N个数中，找出最大的前K个/找出最小的前K个

堆

逻辑结构：想象出来的 ---- 完全二叉树

物理结构：内存中存储的结构 ---- 数组

所有的数组都可以表示成完全二叉树，但不一定是堆

1.下列关键字序列为堆的是：（A）
A 100,60,70,50,32,65
B 60,70,65,50,32,100
C 65,100,70,32,50,60
D 70,65,100,32,50,60
E 32,50,100,70,65,60
F 50,100,70,65,60,32

3.3 堆的实现

3.3.1 堆的创建和初始化

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int HPDataType;

typedef struct Heap
{
    HPDataType* a;
    int size;
    int capacity;
}HP;

// 堆的创建
void HeapInit(HP* hp)
{
    assert(hp);

    hp->a = NULL;
    hp->size = hp->capacity = 0;
}

3.3.2 堆的销毁

// 堆的销毁
void HeapDestroy(HP* hp)
{
    assert(hp);

    free(hp->a);
    hp->capacity = hp->size = 0;
}

3.3.3 堆的插入

当插入一个新元素到数组的尾上时，使用向上调整算法，直到满足堆的性质。

// 交换数据
void Swap(HPDataType* px, HPDataType* py)
{
    HPDataType tmp = *px;
    *px = *py;
    *py = tmp;
}

// 向上调整算法
void AdjustUp(int* a, int child)// 调整位置下标
{
    assert(a);

    int parent = (child - 1) / 2;
    while (child > 0)// while(parent >= 0)
    {
        if (a[child] > a[parent])
        {
            Swap(&a[child], &a[parent]);// 交换数据

            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

// 堆的插入
void HeapPush(HP* hp, HPDataType x)
{
    assert(hp);
    // 判断增容
    if (hp->size == hp->capacity)
    {
        size_t newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
        HPDataType* tmp = realloc(hp->a, sizeof(HPDataType) * newCapacity);
        if (tmp == NULL)
        {
            printf("realloc fail");
            exit(-1);
        }

        hp->a = tmp;
        hp->capacity = newCapacity;
    }
    // 插入数据
    hp->a[hp->size] = x;
    hp->size++;
    // 调整数据
    AdjustUp(hp->a, hp->size - 1);
}

以大堆的插入为例，要求：

• 插入1个x后仍是堆
• 堆插入数据对其他节点没有影响，只是可能影响它到根节点路径上的节点关系

注：

本意：符合parent<0条件终止循环， 实际最终parent=child=0，不满足if-else条件终止循环

修改：以child为判断条件，child=0时终止循环

3.3.4 堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调 整算法。

// 向下调整算法
void AdjustDown(int* 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* 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.3.5 堆实现测试

构建大堆或小堆的区别仅在于向下/向上调整算法内的“>”、“<”更改

// 打印查看
void HeapPrint(HP* hp)
{
    for (int i = 0; i < hp->size; ++i)
    {
        printf("%d ", hp->a[i]);
    }
    printf("\n");
}

// 大、小堆的实现
void TestHeap()
{
    int a[] = { 70,56,30,25,15,10,75 };
    HP hp;
    HeapInit(&hp);
    for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
    {
        HeapPush(&hp, a[i]);
    }

    HeapPrint(&hp);

    HeapPop(&hp);
    HeapPrint(&hp);

    HeapPop(&hp);
    HeapPrint(&hp);

    HeapPop(&hp);
    HeapPrint(&hp);

    HeapPop(&hp);
    HeapPrint(&hp);

    HeapDestroy(&hp);
}

int main()
{
    TestHeap();

    return 0;
}

3.4 堆的应用

3.4.1 Top-K问题

应用：Top-K问题 [在N个数里找出最大的前K个（例：1000个数中找出最大的前10个）]

• **方式1：**先排降序，前10个就是最大的

  时间复杂度：$O(N?lo{g}_{2}N)$

• **方式2：**N个数依次插入大堆，PopK次，每次取堆顶的数据

  时间复杂度：$O(N+{\log }_{2}N?K)$

  时间复杂度：最多调整“高度”次

  首先节点总数（$h$层，N）有2种情况：满二叉树：$2^{(h?1)}?1+1$ ； 完全二叉树（最底层只有1个叶子节点）$2^h?1$

  因此高度：$h={\log }_{2}N$

?

• **方式3：**假设N非常大，N是10亿，K是100，内存中存不下这些数，存在文件中。方式1和方式2都不能用

  时间复杂度：$O(K+(N?K)?{\log }_{2}K)$ —> $O(N?{\log }_{2}K)$ —>$O(N)$

  

?

对于Top-K问题，能想到的最简单直接的方式就是排序，但如果数据量非常大，排序就不太可取了(可能 数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前K个元素来建堆

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

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

2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

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

// 获取堆顶元素
HPDataType HeapTop(HP* hp)
{
    assert(hp);
    assert(!HeapEmpty(&hp));

    return hp->a[0];
}

// 在N个数中找出最大的前K个 / 在N个数中找出最小的前K个
void PrintTopK(int* a, int n, int k)
{
    HP hp;
    HeapInit(&hp);
    // 1. 建堆--用a中前K个元素建堆
    for (int i = 0; i < k; ++i)
    {
        HeapPush(&hp, a[i]);
    }
    // 2. 将剩余N-K个元素依次与堆顶元素比较，大于堆顶元素则替换进堆
    for (int i = k; i < n; ++i)
    {
        if (a[i] > HeapTop(&hp))// 在N个数中找出最大的前K个
        {
            // 1.
            HeapPop(&hp);
            HeapPush(&hp, a[i]);
             2.
            //hp.a[0] = a[i];
            //AdjustDown(hp.a, hp.size, 0);
        }
    }
    HeapPrint(&hp);

    HeapDestroy(&hp);
}

// Topk问题求解
void TestTopk()
{
    int n = 10000;
    int* a = (int*)malloc(sizeof(int) * n);
    srand(time(0));
    for (size_t i = 0; i < n; ++i)
    {
        a[i] = rand() % 1000000;
    }
    // 再设置10个比100w大的数
    a[5] = 1000000 + 1;
    a[1231] = 1000000 + 2;
    a[531] = 1000000 + 3;
    a[511] = 1000000 + 4;
    a[15] = 1000000 + 5;
    a[35] = 1000000 + 6;
    a[999] = 1000000 + 7;
    a[76] = 1000000 + 8;
    a[423] = 1000000 + 9;
    a[3144] = 1000000 + 10;
    PrintTopK(a, n, 10);
}

int main()
{
    TestTopk();
    return 0;
}

3.4.2 堆排序

以排升序为例

最初的想法，构建小堆排升序，选出最小的数、次小的数依次到最大的数

**方法一：**将第1个数先看作堆，后面的数据依次加入堆，然后向上调整，构建成堆

**方法二：**向下调整构建堆，即叶子所在子树不需要调堆，从倒数第一个非叶子节点的子树（最后一个节点的父亲）开始向下调整，不断左移，分别调堆

但是，排升序建小堆存在缺陷：

1. 以上两种方法均可以将数组（完全二叉树）构建成堆，也选出了最大/最小的数放在首位了
2. 如何选出次大/次小的数？若将剩余元素看作一个新堆，则破坏了原先建好的堆的关系，重新建堆才能选出次大/次小的数

**总结：**排升序，建小堆，方法可行，但是效率太低

实际应用的堆排序，共分为两个步骤：

1. 建堆

   给出一个数组，逻辑上可以看做一颗完全二叉树，但是还不是一个堆，因为根节点左右子树不是堆，我们怎么调整呢？

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

   • 升序：建大堆
   • 降序：建小堆

2. 利用堆删除思想来进行排序

   将当前根节点选出的最值和最后一个数交换，不再将其看作堆内的元素

   重新使用向下调整的算法，选出次大/次小值

   循环上述步骤即可完成排序

**总结：**建堆和堆删除中都用到了向下调整，掌握向下调整算法，就可以完成堆排序。

// 堆排序
void HeapSort(int* a, int n)
{
    // 建小堆，排升序
     方法1：a[]的第一个数先看做堆，后面的数据依次加入堆，通过向上调整构建堆
    //for (int i = 1; i < n; ++i)
    //{
    //    AdjustUp(a, i);
    //}

     方法2：叶子所在的子树不需要调，从倒着数第一个非叶子节点的子树开始调（最后一个节点的父亲）
    //for (int i = (n - 1 - 1) / 2; i >= 0; --i)
    //{
    //    AdjustDown(a, n, i);
    //}
    // 不可行在于选第二个数过于复杂

    // 堆排序 - 排升序，建大堆；排降序，建小堆
    // 1、排大堆[O(N)]
    for (int i = (n - 1 - 1) / 2; i >= 0; --i)
    {
        AdjustDown(a, n, i);
    }

    // 2、依次选数，调堆[O(N*logN)]
    for (int end = n - 1; end > 0; --end)
    {
        Swap(&a[end], &a[0]);

        // 再调堆，选出次小的数
        AdjustDown(a, end, 0);
    }
}

void TestHeapSort()
{
    int a[] = { 70,56,30,25,15,10,75,33,50,69 };
    for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
    {
        printf("%d ", a[i]);
    }
    printf("\n");

    HeapSort(a, sizeof(a) / sizeof(a[0]));

    for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}

int main()
{
	TestHeapSort();
    return 0;
}

3.4.3 建堆时间复杂度证明(了解)

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

需要移动节点的总的移动步数为：

$T(n)=2^0?(h?1)+2^1?(h?2)+2^2?(h?3)+2^3?(h?4)+...+2^{h?3}?2+2^{h?2}?1$ ①

$2T(n)=2^1?(h?1)+2^2?(h?2)+2^3?(h?3)+2^4?(h?4)+...+2^{h?2}?2+2^{h?1}?1$ ②

② $?$ ① 错位相减 :

$T(n)=1?h+2^1+2^2+2^3+2^4+...+2^{h?2}+2^{h?1}$

$T(n)=2^0+2^1+2^2+2^3+2^4+...+2^{h?2}+2^{h?1}?h$

$T(n)=2^h?1?h$

由已知$n=2^h?1$ $h={\log }_2(n+1)$

$T(n)=n?{\log }_2(n+1)\approx n$

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

4.二叉树链式结构的实现

对普通二叉树进行增删查改没有太多价值，因为用来存储数据，结构太过复杂

二叉树的价值主要体现：在此基础上增加一些性质，才更有意义

1. 搜索二叉树（最多查找高度次，最坏情况$O(N)$）、平衡搜索二叉树、AVLTree、红黑树、B树
2. Huffman tree

更多关注递归遍历结构：

1. 为后面学习更有效的树打基础
2. 完成部分oj题

4.1 前置说明

在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。此处手动快速创建一棵简单的二叉树，方便快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们再来研究二叉树真正的创建方式。

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>

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

BTNode* BuyNode(BTDataType x)
{
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    if (node == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    node->data = x;
    node->left = node->right = NULL;

    return node;
}

// 手动构建一棵二叉树
BTNode* CreatBinaryTree()
{
    BTNode* nodeA = BuyNode('A');
    BTNode* nodeB = BuyNode('B');
    BTNode* nodeC = BuyNode('C');
    BTNode* nodeD = BuyNode('D');
    BTNode* nodeE = BuyNode('E');
    BTNode* nodeF = BuyNode('F');
    nodeA->left = nodeB;
    nodeA->right = nodeC;
    nodeB->left = nodeD;
    nodeC->left = nodeE;
    nodeC->right = nodeF;

    return nodeA;
}

注意：上述代码并不是创建二叉树的方式，真正创建二叉树方式后序详解重点讲解。

回顾下二叉树的概念,二叉树是：

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

从概念中可以看出，二叉树定义是递归式的，因此后序基本操作基本都是按照该概念实现的。

4.2 二叉树的遍历

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

学习二叉树结构，最简单的方式就是遍历。

所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。

访问结点所做的操作依赖于具体的应用问题；遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

按照规则，二叉树的遍历有：

1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。

   **根、左子树、右子树：**A->B->D->NULL->NULL->NULL->C->E->NULL->NULL->F->NULL->NULL

2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。

   **左子树、根、右子树：**NULL->D->NULL->B->NULL->A->NULL->E->NULL->C->NULL->F->NULL

3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

   **左子树、右子树、根：**NULL->NULL->D->NULL->B->NULL->NULL->E->NULL->NULL->F->C->A

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

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

    printf("%c ", root->data);
    PreOrder(root->left);
    PreOrder(root->right);
}

// 二叉树中序遍历
void InOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }

    InOrder(root->left);
    printf("%c ", root->data);
    InOrder(root->right);
}

// 二叉树后序遍历
void PostOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
    }

    PostOrder(root->left);
    PostOrder(root->right);
    printf("%c ", root->data);
}

二叉树前序遍历示意图

4.2.2 层序遍历

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

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
    if (root == NULL)
    {
        return;
    }

    Queue q;
    QueueInit(&q);
    QueuePush(&q, root);// 数据进队列
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);// 取队头数据
        QueuePop(&q);
        printf("%c ", front->data);

        // 孩子节点带进队列
        if (front->left)
        {
            QueuePush(&q, front->left);
        }
        if (front->right)
        {
            QueuePush(&q, front->right);
        }
    }
    printf("\n");

    QueueDestroy(&q);
}

层序遍历流程：

1. 根节点先进入队列
2. 当前节点出队列时，它的孩子进入队列，即出上一层节点时，带入下一层节点
3. 当队列为空时，说明最后一层已没有节点，遍历结束

层序遍历的实现很简单，重点在于和队列结构的配合使用（队列内的数据类型为二叉树节点指针，而二叉树内需要用到节点）

方法就是在队列的头文件内进行前置声明

// 前置声明
struct BinaryTreeNode;// 二叉树节点类型
typedef struct BinaryTreeNode* QDataType;// 重定义

4.3 节点个数以及高度等

4.3.1 二叉树节点个数

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
    return root == NULL ? 0 : 
        BinaryTreeSize(root->left) 
        + BinaryTreeSize(root->right) 
        + 1;
}

二叉树节点个数递归示意图（以上图A的左子树为例）：

4.3.2 二叉树叶子节点个数

// 二叉树叶子节点个数
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);
}

二叉树叶子节点个数递归示意图（以上图A的左子树为例）：

4.3.3 二叉树第k层节点个数

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
    /*if (k < 1)
    {
        return 0;
    }*/
    assert(k >= 1);

    if (root == NULL)
    {
        return 0;
    }

    if (k == 1)
    {
        return 1;
    }

    // root不为空，k也不等于1，说明root这棵树的第k层节点在子树里面
    // 转换成求左右子树的第k-1层的节点数量
    return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

求二叉树第k层节点个数遍历示意图

4.3.4 二叉树深度/高度

// 二叉树深度/高度
int BinaryTreeDepth(BTNode* root)
{
    if (root == NULL)
    {
        return 0;
    }

    // 存在重复调用的问题
    //return BinaryTreeDepth(root->left) > BinaryTreeDepth(root->right) ? BinaryTreeDepth(root->left) + 1 : BinaryTreeDepth(root->right) + 1;
    
    int leftDepth = BinaryTreeDepth(root->left);
    int rightDepth = BinaryTreeDepth(root->right);

    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

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

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
    if (root == NULL)
    {
        return NULL;
    }

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

    BTNode* leftRet = BinaryTreeFind(root->left, x);
    if (leftRet)
    {
        return leftRet;
    }

    BTNode* rightRet = BinaryTreeFind(root->right, x);
    if (rightRet)
    {
        return rightRet;
    }

    return NULL;
}

二叉树查找值为E的节点递归示意图

4.4 二叉树的创建和销毁

4.4.1 二叉树的构建及遍历

二叉树遍历

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
#include<stdio.h>
#include<stdlib.h>
struct TreeNode
{
	struct TreeNode* left;
	struct TreeNode* right;
	char val;
};

struct TreeNode* CreateTree(char* str, int* pi)
{
	if (str[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}

	struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
	root->val = str[(*pi)++];
	root->left = CreateTree(str, pi);
	root->right = CreateTree(str, pi);

	return root;
}

void InOrder(struct TreeNode* root)
{
	if (root == NULL)
		return;

	InOrder(root->left);
	printf("%c ", root->val);
	InOrder(root->right);
}

int main()
{
	char str[100];
	scanf("%s", str);
	int i = 0;
	struct TreeNode* root = CreateTree(str, &i);
	InOrder(root);

	return 0;
}

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

思路：层序遍历完全二叉树，非空节点是连续的；而非完全二叉树的非空节点是不连续的

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    QueuePush(&q, root);// 数据进队列
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);// 取队头数据
        QueuePop(&q);

        if (front == NULL)// 出的是空节点
        {
            break;
        }
        else
        {
            QueuePush(&q, front->left);
            QueuePush(&q, front->right);
        }
    }
    // 遇到空了以后，检查队列中剩下的节点
    // 1、剩下全是空节点，则是完全二叉树
    // 2、剩下节点存在非空，则不是完全二叉树
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);// 取队头数据
        QueuePop(&q);

        if (front)// 存在非空节点
        {
            QueueDestroy(&q);
            return false;
        }
    }

    QueueDestroy(&q);
    return true;
}

4.4.5 二叉树销毁

采用后序遍历的方法，先销毁左子树，再销毁右子树，最后销毁根节点

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

    BinaryTreeDestory(root->left);
    BinaryTreeDestory(root->right);
    free(root);
}

4.5 二叉树基础oj练习

1. 单值二叉树

OJ链接

bool isUnivalTree(struct TreeNode* root)
{
    if(root == NULL)
    {
        return true;
    }

    if(root->left && root->left->val != root->val)
    {
        return false;
    }

    if(root->right && root->right->val != root->val)
    {
        return false;
    } 

    return isUnivalTree(root->left) && isUnivalTree(root->right); 
    // 左右同为真，才返回真，否则为假
}

2. 检查两颗树是否相同

OJ链接

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    // 根
    // 都为空
    if(p == NULL && q == NULL)
    {
        return true;
    }

    // 其中一个为空
    if(p == NULL || q == NULL)
    {
        return false;
    }

    // 都不为空
    if(p->val != q->val)
    {
        return false;
    }

    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

3. 对称二叉树

OJ链接

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool _isSymmetricTree(struct TreeNode* root1, struct TreeNode* root2)
{
    if(root1 == NULL && root2 ==NULL)
        return true;

    if(root1 == NULL || root2 == NULL)
        return false;

    if(root1->val != root2->val)
        return false;

    return _isSymmetricTree(root1->left, root2->right) && _isSymmetricTree(root1->right, root2->left);
}

bool isSymmetric(struct TreeNode* root)
{
    if(root == NULL)
        return true;

    return _isSymmetricTree(root->left, root->right);
}

4. 二叉树的前序遍历

OJ链接

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
// 节点个数计算
int TreeSize(struct TreeNode* root)
{
    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

// 子函数
void _preorderTraversal(struct TreeNode* root, int* a, int* pi)// 数组；下标
{
    if(root == NULL)
        return;

    a[(*pi)++] = root->val;// 前序遍历

    _preorderTraversal(root->left, a, pi);
    _preorderTraversal(root->right, a, pi);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    // 输出型参数：传进来整型的地址，解引用获得整型本身，给整形赋值得到数组大小
    int size = TreeSize(root);
    int* a = malloc(sizeof(int)*size);
    int i=0;
    _preorderTraversal(root, a, &i);
    *returnSize = size;
    return a;
}

注：

如果传值调用，每次递归调用都开辟不同的栈帧，因此即使i同名也代表不同的变量

同一作用域下的i不会因为递归调用的值改变而相应发生改变

想要递归时做到使用同一变量，应当传变量的地址

二叉树中序遍历

二叉树的后序遍历

5. 另一颗树的子树

OJ链接

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    // 根
    // 都为空
    if(p == NULL && q == NULL)
    {
        return true;
    }

    // 其中一个为空
    if(p == NULL || q == NULL)
    {
        return false;
    }

    // 都不为空
    if(p->val != q->val)
    {
        return false;
    }

    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
    // 先比较根节点
    if(root == NULL)
    {
        return false;
    }

    if(isSameTree(root, subRoot))
    {
        return true;
    }
	// 比较子树
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

时间复杂度

最好情况：$O(N)$：两棵树的所有节点都相等或都不等

最坏情况：$O(N^2)$：isSubtree比较N次，isSameTree比较N次，即两棵树只有最后一个节点不等