目录
本章重点：
1.树的概念及结构
1.1树的概念
1.2树的相关概念
1.3树的表示
左孩子有兄弟表示法
1.4树在实际中的应用
表示文件系统的目录树结构
思维导图
2.二叉树的概念及结构
2.1概念
2.2现实中的二叉树
2.3特殊的二叉树
两个满二叉树、完全二叉树的重要性质！
2.4二叉树的性质
小试牛刀（二叉树题目）
2.5二叉树的存储结构
1.顺序存储
2.链式存储
2.6二叉树父亲节点与孩子节点关系计算
3.二叉树的顺序结构及实现
3.1二叉树的顺序结构
3.2堆的概念及结构
本章重点：
- 树的概念及结构
- 二叉树概念及结构
- 二叉树顺序结构及实现
- 二叉树链式结构及实现
文章图片
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、E、G是P的祖先
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
森林：由m（m>0）棵互不相交的树的集合称为森林；
注意：
树的层次有两种写法，都没有错误：
- 从1开始，依次类推
- 从0开始，依次类推
文章图片
习惯上，我们采用从1开始的层次；如果题目不说，那么我们也采用第一种，从1开始的方式来定义树的层次。
除非题目有特指是，层次从0层次开始（空树为 -1），才采用第二种。
1.3树的表示 树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：
双亲表示法，孩子表示法以及左孩子右兄弟表示法等。我们这里就简单的了解其中最常用的左孩子右兄弟表示法。
首先，我们想想，如何去表示树呢？代码如何实现树的结构呢？
文章图片
脑海中冒出第一个想法————定义一个结构体，里面有数据data，有存储子结点的指针，那么问题来了！需要定义多少指针呢？？？
文章图片
但是，我们发现了缺陷：
- 可能会存在不少的空间浪费
- 万一没有限定树的度为多少呢？
不知道N，没关系，来一个节点，往顺序表里放，不够了就扩容。
文章图片
结构复杂，所以，也不考虑方式2，
除此之外，我们可以考虑结构数组存储结点（数据+父亲节点所在下标）
文章图片
但是，上面的方式，各有优缺点，而表示树结构的最优方法，是左孩子右兄弟表示法。
左孩子右兄弟表示法
typedef int DataType;
struct Node
{
DataType data;
// 结点中的数据域
struct Node* firstChild;
// 永远只指向第一个孩子结点
struct Node* NextBrother;
// 指向其下一个兄弟结点
};
文章图片
即：
文章图片
1.4树在实际中的应用 表示文件系统的目录树结构
文章图片
思维导图
文章图片
2.二叉树的概念及结构 2.1概念 一棵二叉树是结点的一个有限集合，该集合:
- 或者为空
- 由一个根节点加上两棵别称为左子树和右子树的二叉树组成
文章图片
从上图可以看出：
- 二叉树不存在度大于2的结点
- 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
文章图片
2.2现实中的二叉树
文章图片
2.3特殊的二叉树
- 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 2^K - 1，则它就是满二叉树。
- 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
文章图片
由图可得到：
两个满二叉树、完全二叉树的重要性质！ （1）满二叉树中，
- 所有的叶子节点都在最后一层。
- 所有的分支节点都有两个孩子。
高度是h的满二叉树，共有2^h - 1个结点。
文章图片
反过来同理：给出满二叉树的结点个数，求出树的高度
文章图片
（2）完全二叉树：
- 前N - 1层都是满的。
- 最后一层不满，但是最后一层从左到右是连续的。
- 最多只有一个度为1的结点。
文章图片
最多只有一个度为1的结点说明：
文章图片
2.4二叉树的性质
文章图片
文章图片
小试牛刀（二叉树题目）
文章图片
文章图片
解释：
文章图片
文章图片
文章图片
2.5二叉树的存储结构 二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。
1.顺序存储
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
文章图片
注意，顺序存储，顺序二字很重要，即使没有数据，数组那个位置空着，也要遵守。
文章图片
2.链式存储
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面课程学到高阶数据结构如红黑树等会用到三叉链。
文章图片
2.6二叉树父亲节点与孩子节点关系计算 假设parent是父亲节点在数组中的下标
- leftchild = parent * 2 + 1
- rightchild = parent * 2 + 2
- parent = (chile - 1) / 2
文章图片
对于非完全二叉树，也可以使用数组顺序存储，但是可能会浪费空间！！
文章图片
3.二叉树的顺序结构及实现 3.1二叉树的顺序结构 普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
文章图片
3.2堆的概念及结构 事先说明数据结构的堆与操作系统的堆不是一个概念！！！：
文章图片
堆的概念
文章图片
详细说明：
- 大堆：树中一个树及子树中，任何一个父亲的值都大于等于孩子的值。
- 小堆：树中一个树及子树中，任何一个父亲的值都小于等于孩子的值。
- 堆排序
- topK问题。在N个数中，找出最大的前K个/找出最小的前K个。
文章图片
堆的实现 拿最大堆举例（树中一个树及子树中，任何一个父亲的值都大于等于孩子的值。）
定义堆
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;
}交换父子结点
//交换父子结点数据
void Swap(HPDataType* px, HPDataType* py)
{
HPDataType tmp = *px;
*px = *py;
*py = tmp;
}打印堆内数据
//打印堆内数据
void HeapPrint(HP* hp)
{
for (int i = 0;
i < hp->size;
++i)
{
printf("%d ", hp->a[i]);
}
printf("\n");
}堆是否为空
//堆为空
bool HeapEmpty(HP* hp)
{
assert(hp);
return hp->size == 0;
}对于插入堆来说，最大堆、最小堆都是向上调整
区别：
最大堆向上调整，插入后的结点数据，要不改变最大堆（ps:定义最大堆是每个节点的数据值都大于等于其子树数据值），影响了插入节点到根节点那段路径上的结点（ 产生变化！）：将插入结点作为child，与其父亲parent比较，如果a[child] > a[parent]，就交换节点数据值，直到child是根节点，才截至！
最小堆向上调整，插入后的结点数据，要不改变最小堆（ps:定义最小堆是每个节点的数据值都小于等于其子树数据值），影响了插入节点到根节点那段路径上的结点（ 产生变化！）：将插入结点作为child，与其父亲parent比较，如果a[child] < a[parent]，就交换节点数据值，直到child是根节点，才截至！
代码以最大堆，作为插入堆、删除根节点为例子，后续不再说明：
数据插入堆（拿最大堆举例）
//数据插入堆（堆的定义：最大堆or最小堆）
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\n");
exit(-1);
}
hp->a = tmp;
hp->capacity = newCapacity;
}
hp->a[hp->size] = x;
hp->size++;
//向上调整
AdjustUp(hp->a, hp->size - 1);
}向上调整
//向上调整(变成父亲)
void AdjustUp(int* a, int child)
{
assert(a);
int parent = (child - 1) / 2;
//while (parent >= 0)错误写法，仔细体会！！
while (child > 0)
{
if (a[child] > a[parent])
{
/*HPDataType tmp = a[child];
a[child] = a[parent];
a[parent] = tmp;
*/
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}对于删除堆顶数据来说，最大堆、最小堆都是需要向下调整
需要注意的是，根节点，也就是堆顶结点，我们直接删除是不行的！！需要将最后一个结点与根节点位置互换，因为我们删除尾结点（堆本质上是数组嘛~~~~~）是方便的！！！然后再进行“根结点” 向下调整...................
区别：
最大堆删除堆顶数据，看是否此时还仍然符合最大堆的要求，若不符合，那么就需要向下调整，调成符合最大堆的形式。
考虑到完全二叉树中，任意一个父亲节点左孩子存在，而右孩子不一定存在（细品！！！），所以我们需要判断，避免造成非法访问数组元素。如果右孩子存在，即：child + 1 < n ，右孩子大于左孩子，即：a[child + 1] > a[ child ]。那么就child指向右孩子。
（即：该代码段是用child指向左右孩子中较大孩子）
如果说，a[child] > a[parent]，那么就交换父子结点，然后继续向下调整。
最小堆删除堆顶数据，看是否此时还仍然符合最小堆的要求，若不符合，那么就需要向下调整，调成符合最小堆的形式。
考虑到完全二叉树中，任意一个父亲节点左孩子存在，而右孩子不一定存在（细品！！！），所以我们需要判断，避免造成非法访问数组元素。如果右孩子存在，即：child + 1 < n ，右孩子小于左孩子，即：a[child + 1] < a[ child ]。那么就child指向右孩子。
（即：该代码段是用child指向左右孩子中较小孩子）
如果说，a[child] < a[parent]，那么就交换父子结点，然后继续向下调整。
删除堆顶数据
//删除堆顶数据
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);
}向下调整
//向下调整
void AdjustDown(int* a, int n, int parent)
{
//int left = parent * 2 + 1;
//int right = parent * 2 + 2;
//while (parent < n)
//{
// if (a[left] > a[right])
// {
//Swap(&a[left], &a[parent]);
//parent = left;
// }
// else if (a[left] < a[right])
// {
//Swap(&a[right], &a[parent]);
//parent = right;
// }
// else
//break;
//完全二叉树中，左孩子存在，右孩子有可能不存在，要避免越界访问，需要判断
int child = parent * 2 + 1;
//左孩子小于n
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;
}
}
}TopK问题（1.建立小堆2.若比堆顶数据大，则push） （注：此时的push、pop都是小堆操作，注意区别于上述我们讲的代码（大堆）~~~~）
首先想想为什么要有堆排序？
文章图片
文章图片
文章图片
Heap.h文件代码：
#pragma once
#include
#include
#include
#includetypedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
//初始化堆
void HeapInit(HP* hp);
//交换父子结点数据
void Swap(HPDataType* px, HPDataType* py);
//打印堆内数据
void HeapPrint(HP* hp);
//堆为空
bool HeapEmpty(HP* hp);
//数据插入堆（堆的定义：最大堆or最小堆）
void HeapPush(HP* hp, HPDataType x);
//向上调整(变成父亲)
void AdjustUp(int* a, int child);
//删除堆顶数据
void HeapPop(HP* hp);
//向下调整
void AdjustDown(int* a, int n, int parent);
//获取堆顶数据
HPDataType HeapTop(HP* hp);
Heap.c文件代码
#define _CRT_SECURE_NO_WARNINGS
#include"Heap.h"//初始化堆
void HeapInit(HP* hp)
{
assert(hp);
hp->a = NULL;
hp->size = hp->capacity = 0;
}//交换父子结点数据
void Swap(HPDataType* px, HPDataType* py)
{
HPDataType tmp = *px;
*px = *py;
*py = tmp;
}//打印堆内数据
void HeapPrint(HP* hp)
{
for (int i = 0;
i < hp->size;
++i)
{
printf("%d ", hp->a[i]);
}
printf("\n");
}//堆为空
bool HeapEmpty(HP* hp)
{
assert(hp);
return hp->size == 0;
}//数据插入堆（堆的定义：最大堆or最小堆）
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\n");
exit(-1);
}
hp->a = tmp;
hp->capacity = newCapacity;
}
hp->a[hp->size] = x;
hp->size++;
//向上调整
AdjustUp(hp->a, hp->size - 1);
}//向上调整 （小堆）
void AdjustUp(int* a, int child)
{
assert(a);
int parent = (child - 1) / 2;
//while (parent >= 0)错误写法，仔细体会！！
while (child > 0)
{
//如果孩子小于父亲
if (a[child] < a[parent])
{
/*HPDataType tmp = a[child];
a[child] = a[parent];
a[parent] = tmp;
*/
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
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);
}//向下调整（小堆）
void AdjustDown(int* a, int n, int parent)
{
//完全二叉树中，左孩子存在，右孩子有可能不存在，要避免越界访问，需要判断
int child = parent * 2 + 1;
//左孩子小于n
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;
}
}
}//获取堆顶数据
HPDataType HeapTop(HP* hp)
{
assert(hp);
assert(!HeapEmpty(hp));
return hp->a[0];
}Test.c文件代码
#define _CRT_SECURE_NO_WARNINGS
#include"Heap.h"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]);
//小堆的HeapPush
}
// 2. 将剩余n-k个元素依次与堆顶数据比较，比他大，就替换他，进堆
for (int i = k;
i < n;
++i)
{
if (a[i] > HeapTop(&hp))
{
//方法1
//HeapPop(&hp);
//HeapPush(&hp, a[i]);
//方法2
hp.a[0] = a[i];
AdjustDown(hp.a, hp.size, 0);
}
}
HeapPrint(&hp);
//HeapDestroy(&hp);
}
void TestTopk()
{
int n = 10000;
int* a = (int*)malloc(sizeof(int) * n);
srand(time(0));
for (size_t i = 0;
i < n;
++i)
{
//随机生成数字，%100w就保证了数字小于100w
a[i] = rand() % 1000000;
}
//手动设置10个大于100w的数字
a[5] = 1000000 + 1;
a[1231] = 1000000 + 2;
a[531] = 1000000 + 3;
a[5121] = 1000000 + 4;
a[115] = 1000000 + 5;
a[2335] = 1000000 + 6;
a[9999] = 1000000 + 7;
a[76] = 1000000 + 8;
a[423] = 1000000 + 9;
a[3144] = 1000000 + 10;
PrintTopK(a, n, 10);
}
int main()
{
TestTopk();
return 0;
}运行结果：
文章图片
堆排序 （升序中的Push、Pop都是对小堆操作，如上述代码；降序即是建立大堆，只需要把Push、Pop对堆操作即可）
//堆排序 - 升序- 空间复杂度（ O(N) ）
void HeapSort(int* a, int n)
{
HP hp;
HeapInit(&hp);
//建立一个小堆
for (int i = 0;
i < n;
++i)
{
HeapPush(&hp, a[i]);
} //PopN 次
for (int i = 0;
i < n;
++i)
{
a[i] = HeapTop(&hp);
HeapPop(&hp);
}
//HeapDestroy(&hp);
}
int main()
{
int a[] = { 70,56,30,25,15,10,75 };
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");
return 0;
}该程序空间复杂度是O(N)，那么能否优化到O(1)呢？？
4.二叉树的链式结构及实现 4.1为什么要存在链式二叉树？ 因为并不是所有的二叉树都是特殊的完全二叉树或者满二叉树，普通的二叉树是没有规定的，即：一个节点会在保证二叉树的前提下，后续连接很多节点，如下图所示。这种结构是很复杂的！对于一些增删查改的操作来说，并没有存在的必要，因为链表就可以解决，何必要那么费劲去造一棵树呢？
所以，我们在此不去研究普通二叉树的增删查改操作，而是在普通二叉树的基础上，增加一些性质，去研究它，方便后续更难的树的学习！！
文章图片
4.2二叉树的遍历 4.2.1前序、中序、后序遍历
学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
文章图片
按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：
- 前序遍历(Preorder Traversal 亦称先序遍历)——根、左子树、右子树
- 中序遍历(Inorder Traversal)——左子树、根、右子树
- 后序遍历(Postorder Traversal)——左子树、右子树、根
文章图片
文章图片
文章图片
注意，遍历就是针对根、左子树、右子树而言！
前序、中序、后序遍历代码实现（不难，但是递归过程要理解！！）
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 = https://www.it610.com/article/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');
BTNode* nodeG = BuyNode('G');
BTNode* nodeH = BuyNode('H');
BTNode* nodeI = BuyNode('I');
BTNode* nodeJ = BuyNode('J');
nodeA->left = nodeB;
nodeA->right = nodeC;
nodeB->left = nodeD;
nodeB->right = nodeE;
nodeC->left = nodeF;
nodeC->right = nodeG;
nodeD->left = nodeH;
nodeD->right = nodeI;
nodeG->right = nodeJ;
return nodeA;
}// 二叉树前序遍历
void PreOrder(BTNode* root)
{
if (root == NULL)
{
//printf("NULL ");
//加上该句，其实是真实的走的过程，因为访问到NULL才算一条路走完！
return;
}
printf("%c ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}// 二叉树中序遍历
void InOrder(BTNode* root)
{
if (root == NULL)
{
//printf("NULL ");
//加上该句，其实是真实的走的过程，因为访问到NULL才算一条路走完！
return;
}
InOrder(root->left);
printf("%c ", root->data);
InOrder(root->right);
}
// 二叉树后序遍历
void PostOrder(BTNode* root)
{
if (root == NULL)
{
//printf("NULL ");
//加上该句，其实是真实的走的过程，因为访问到NULL才算一条路走完！
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%c ", root->data);
}
int main()
{
BTNode* root = CreatBinaryTree();
//PreOrder(root);
//前
//InOrder(root);
//中
PostOrder(root);
//后 return 0;
}注意：递归过程要深刻理解啊！！！！
文章图片
4.2.2层序遍历
【数据结构与算法（C语言版）|【05_1数据结构】【算法入门_分治】二叉树初阶的基本理解、堆的概念及结构（含二叉树经典笔试题~）】
4.3二叉树节点计数 先说结论：用遍历思想做二叉树的计数是错误的！
代码1错误点：count变量是局部变量，根据函数栈帧的知识，每次调用函数都需要创建此变量count，所以count始终是只执行一次++，即：count = 1！！不能完成计数！
——————啥？改成全局变量或者用static修饰变量变成可以随着调用而改变的静态变量，可行？？
//二叉树的节点个数
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return;
}
int count = 0;
++count;
BinaryTreeSize(root->left);
BinaryTreeSize(root->right);
return count;
}int main()
{
BTNode* root = CreatBinaryTree();
//PreOrder(root);
//前
//InOrder(root);
//中
PostOrder(root);
//后
printf("\n");
//ABCDEFGHIJ 共10个字母，所以TreeSize = 10才对！我们来验证一下
printf("TreeSize = %d \n", BinaryTreeSize(root));
//1 return 0;
}代码2错误点：static修饰，变成静态变量后，的确可以随着函数调用而改变值，我们试了一次，发现可以输出正确结果10。但是我们再次试一次，却发现打印输出了20？同样的一棵树，我去遍历两次怎么节点数还增加？？两次应该是一样的哇！！
——————static修饰的变量是静态变量，在静态区，不会随着栈帧创建和销毁而去销毁，所以第二次再去变量这棵树，节点个数当然会增加，并且是翻一倍增加，就相当于重复遍历这棵树把节点又加了一遍；而不是仍然保持正确结果，输出10！！
——————可见，静态变量也是不合适的！难道我们去计数仅仅去计数一次，后面不再去计数了吗？不合适不合适！这个遍历思想方法去计数思想是错误的！！！！！
//二叉树的节点个数
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return;
}
static int count = 0;
++count;
BinaryTreeSize(root->left);
BinaryTreeSize(root->right);
return count;
}int main()
{
BTNode* root = CreatBinaryTree();
//PreOrder(root);
//前
//InOrder(root);
//中
PostOrder(root);
//后
printf("\n");
//ABCDEFGHIJ 共10个字母，所以TreeSize = 10才对！我们来验证一下
printf("TreeSize = %d \n", BinaryTreeSize(root));
//10
printf("TreeSize = %d \n", BinaryTreeSize(root));
//20!?答案错了！ return 0;
}那该怎么去写二叉树计数的代码呢？？
——————显然，用遍历思想去计数是不对的。那么我们去传地址就可以！！
//二叉树的节点个数
void BinaryTreeSize(BTNode* root,int* pcount)
{
if (root == NULL)
{
return;
}
++(*pcount);
BinaryTreeSize(root->left,pcount);
BinaryTreeSize(root->right,pcount);
}int main()
{
BTNode* root = CreatBinaryTree();
//PreOrder(root);
//前
//InOrder(root);
//中
PostOrder(root);
//后
printf("\n");
int count = 0;
BinaryTreeSize(root, &count);
//ABCDEFGHIJ 共10个字母，所以TreeSize = 10才对！我们来验证一下
printf("TreeSize = %d \n", count);
//10
printf("TreeSize = %d \n", count);
//还是10 return 0;
}最优化的计算二叉树节点个数的算法（画递归调用图来理解！！！要深刻理解！！）（分治思想）
//二叉树的节点个数
int BinaryTreeSize(BTNode* root)
{
return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
int main()
{
BTNode* root = CreatBinaryTree();
//PreOrder(root);
//前
//InOrder(root);
//中
PostOrder(root);
//后
printf("\n");
//ABCDEFGHIJ 共10个字母，所以TreeSize = 10才对！我们来验证一下
printf("TreeSize = %d \n", BinaryTreeSize(root));
//10
printf("TreeSize = %d \n", BinaryTreeSize(root));
//还是10 return 0;
}同样的道理，二叉树的叶子节点也可以这样写：
4.4 二叉树叶子节点计数
//二叉树的叶子节点个数
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);
}int main()
{
BTNode* root = CreatBinaryTree();
//PreOrder(root);
//前
//InOrder(root);
//中
PostOrder(root);
//后
printf("\n");
//ABCDEFGHIJ 共10个字母，所以TreeSize = 10才对！我们来验证一下
printf("TreeSize = %d \n", BinaryTreeSize(root));
//10
printf("TreeSize = %d \n", BinaryTreeSize(root));
//还是10 //叶子节点应该是5个
printf("TreeLeafSize = %d \n", BinaryTreeLeafSize(root));
//5 return 0;
}4.5二叉树第K层节点个数 比较难以理解！！思想如下：
文章图片
比如要求对于这棵树，我们想要求A的第3层，可以抓换成求左子树第2层+右子树第2层的节点数量
左子树第2层，即：求B的第2层，转换成求其(B)左子树的第1层+求其右子树的第1层
.............................
//二叉树第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);
}int main()
{
BTNode* root = CreatBinaryTree();
//PreOrder(root);
//前
//InOrder(root);
//中
PostOrder(root);
//后
printf("\n");
//ABCDEFGHIJ 共10个字母，所以TreeSize = 10才对！我们来验证一下
printf("TreeSize = %d \n", BinaryTreeSize(root));
//10
printf("TreeSize = %d \n", BinaryTreeSize(root));
//还是10 //叶子节点应该是5个
printf("TreeLeafSize = %d \n", BinaryTreeLeafSize(root));
//5 //二叉树第K层节点的数量第4层应该是3个节点
printf("TreeLevelKSizeSize = %d \n", BinaryTreeLevelKSize(root, 4));
//3 return 0;
}很难理解！！画递归展开图来深刻理解一下！！
文章图片
4.6二叉树的深度/高度 思想依旧是分治思想（大问题分解成小问题）（层层往下调结果！最后汇总！）
树的高度/深度 = 左子树深度和右子树深度中较大的那个 + 1
想想看这样写，代码的缺陷在哪里？？
//二叉树的深度/高度
int BinartTreeDepth(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return BinartTreeDepth(root->left) > BinartTreeDepth(root->right) ? BinartTreeDepth(root->left) + 1 : BinartTreeDepth(root->right) + 1;
}解释：
很浪费的函数栈帧调用，对于一个BinartTreeDepth(root->left)就得调用到底，不断地在栈区积累；后面的BinartTreeDepth(root->right)也是需要不断在栈区调用。然后最后的BinartTreeDepth(root->left) + 1 : BinartTreeDepth(root->right) + 1也是还需要再次调用函数栈帧，因为起初的调用并没有被保存，函数栈帧随着调用结束而被销毁！！所以说，极大地恶劣地浪费了栈的内存，而且大量的重复计算！所以，我们可以将调用后的先保存一下，方便后面再去重复计算，浪费栈帧。优化后的求二叉树的深度/高度的算法
//二叉树的深度/高度
int BinartTreeDepth(BTNode* root)
{
if (root == NULL)
{
return 0;
} int leftDepth = BinartTreeDepth(root->left);
int rightDepth = BinartTreeDepth(root->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}int main()
{
BTNode* root = CreatBinaryTree();
//PreOrder(root);
//前
//InOrder(root);
//中
PostOrder(root);
//后
printf("\n");
//ABCDEFGHIJ 共10个字母，所以TreeSize = 10才对！我们来验证一下
printf("TreeSize = %d \n", BinaryTreeSize(root));
//10
printf("TreeSize = %d \n", BinaryTreeSize(root));
//还是10 //叶子节点应该是5个
printf("TreeLeafSize = %d \n", BinaryTreeLeafSize(root));
//5 //二叉树第K层节点的数量第4层应该是3个节点
printf("TreeLevelKSizeSize = %d \n", BinaryTreeLevelKSize(root, 4));
//3 //二叉树的深度
printf("TreeDepth = %d \n", BinartTreeDepth(root));
// return 0;
}4.7二叉树查找值为x的节点 左数有值为x的节点就停止查找了，不用再去找了！
//二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data =https://www.it610.com/article/= 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;
}
文章图片
注意：尽量不要出现如下这种情况的代码！因为这种情况的代码，左子树和右子树都找了，找的效率不高，而且没必要都找了，我们需要找到就不用再去找了，比如：先找左子树有无x值，有则停止继续找；没有，则再去找右子树。
文章图片
5.二叉树的OJ题 5.1单值二叉树
文章图片
总体思想还是分治思想：大事化小，去递归调用。
（交换律）
/**
* Definition for a binary tree node.
* struct TreeNode {
*int val;
*struct TreeNode *left;
*struct TreeNode *right;
* };
*/bool isUnivalTree(struct TreeNode* root)
{
if(root == NULL)
return true;
//如果root->left不等于NULL,即：有值；但是值不等于val
if(root->left && root->left->val != root->val)
{
return false;
}//如果root->right不等于NULL,即：有值；但是值不等于val
if(root->right && root->right->val != root->val)
{
return false;
}return isUnivalTree(root->left) && isUnivalTree(root->right);
}另一个思路：前序遍历，逐一比较
5.2二叉树的前序遍历int PrevOrder(struct TreeNode* root , int val) { if (root == NULL) { return 0; } if (root->val != val) { return 1; } return PrevOrder(root->left, val) + PrevOrder(root->right, val); } bool isUnivalTree(struct TreeNode* root) { //递归计数法，遇到不相等的就返回1，相等就继续 int data = https://www.it610.com/article/root->val; int tmp = PrevOrder(root, data); if (tmp == 0) { return true; } else { return false; } }
文章图片
文章图片
思想：基本的前序遍历：根、左、右
需要注意的是：
- 返回值要求是malloc出来的，所以malloc多大的空间是个问题。空间大了浪费甚至超时，空间小了不够用。所以我们想到了先用TreeSize计算出节点个数，精准开辟空间大小。
- 前序遍历，我们要思考是否能直接递归调用preorderTraversal（）函数呢？————递归调用的话，其中的输出型参数int* returnSize该怎么办？所以，我们构造出一个前序遍历递归的子函数——_preorderTraversal（）【子函数最好是原函数前面加个_】，来方便前序遍历将数放进数组中，而先不用考虑输出型参数int* returnSize的问题。
- 注意，输出型参数*returnSize的作用是返回的时候，事先确定好返回的参数有几个。因为我们返回值仅仅能返回一个值，而加上输出型参数*returnSize后，即可在return a后确定a数组种返回的数据个数。
文章图片
文章图片
原因我们可以通过递归调用图来深究一下：
文章图片
所以，我们看出，i这个参数，在每次调用的时候，要有所区别，他是形参，不会随着值得改变而改变。
因为，我们考虑传指针来避免这个错误！
正确代码
/**
* Definition for a binary tree node.
* struct TreeNode {
*int val;
*struct TreeNode *left;
*struct TreeNode *right;
* };
*//**
* 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;
}
文章图片
5.3相同的树
文章图片
思想：
两棵树先比较根是否都为空？是则return true；再判断两棵树是否其中有一个为空？是则return false；既然满足都不为空，那么再去判断是否根的值相同？不是则return false；既然根不为空且根的值也相同，再去判断两棵树左子树与左子树之间是否相同？右子树与右子树之间是否相同？
/**
* 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);
}5.4对称二叉树
文章图片
文章图片
思想：
我们将一棵树拆开两部分来看->
首先，对于整棵树的根节点进行判断：根节点是NULL，则return true;
然后再去判断根节点的左右节点是否相同？所以我们运用对称二叉树的思想，建立了一个子函数用来判断是否对称相等（具体思想方法见对称二叉树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);
}5.5另一棵树的子树
文章图片
思想：用root的每一个子树都和sub比一下
/**
* 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);
}、
推荐阅读
- 数据结构|劈叉都会还不会下腰吗（（二叉树经典面试题详解））
- LeetCode算法刷题|LeetCode_二叉树_中等_107.二叉树的层序遍历 II
- 历史上的今天|【历史上的今天】1 月 8 日（谷歌推出 Google Pay；Quibi 的重生；平衡二叉树的发明者出生）
- leecode题解|「代码随想录」968.监控二叉树【贪心算法】力扣详解！
- 二叉树|二叉树的 前序 中序 后序,面试题小计 根据中序 后序 得出前序
- C语言与C++编程|二叉树操作详解
- 《LeetCode算法全集》|LeetCode 297. 二叉树的序列化与反序列化
- 数据结构|数据结构与算法—— 树
- 数据结构|二叉排序/搜索树类模板