文章目录
口令：此乃何物？
前言
经过两周的努力奋战，博主呕心沥血地总结了数据结构中树与二叉树的所有基本操作，包括堆的实现，链式二叉树等等并含有完整的测试代码，不要问博主应得什么，要问博主为大家做了什么（泪目），全文有大约两万字，在总结的过程中还发现了写递归程序的一种快速方法，欢迎大家点赞收藏。
树
什么是树
树是一种数据结构，它是由n(n≥1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。我们用树的逻辑结构来表示一下它：
这就表示了一棵树，其中每一个节点都会存储一定的信息，这里A为树根。
我们可以发现树其实是递归进行定义的，任何一棵树都可以分成根节点和子树。
树的基本概念
1.节点的度：一个节点含有子树的个数我们称之为该节点的度，比如A的度为3，D的度为1，J的度为2。
2.叶节点：度为0的节点，在这棵树中有K,F,G,H,I,L,M。
3.分支节点：度不为0的节点。即除了叶子节点之外的节点都可以称为分支节点。
4.父节点：一个节点为其子节点的父节点。
5.兄弟节点：具有相同父节点的节点。
6.树的度：一棵树中最大节点的度称为树的度。
7.节点的层次：根为第一层，其子节点为第二层，以此类推空树的高度为0。
8.树的高度或深度：一棵树中节点的最大层次。
9.堂兄弟节点：双亲在同一层的非兄弟节点称为堂兄弟节点，这里的G和H就为堂兄弟节点。
10.节点的祖先：从根到该节点经过的所有节点称为该节点的祖先。
11.子孙：以某节点为根的任意子树上的所有顶点称为该节点的子孙。
12.森林：不相交的树的集合。比如并查集就是多棵树的集合。
树的实现方式
树的实现方式有很多种，目前公认最好的实现方式是：左孩子右兄弟表示法。
就是每一个树的节点中，存储两个指针，分别指向它的最左侧的孩子节点和它的向右一位的兄弟节点，如果没有左孩子或者右兄弟的话则对应的指针指向空，注意是右兄弟而不是堂兄弟。
定义节点的方式为：
struct Node{
struct Node* firstchild;//指向左孩子
struct Node* nextbrother;//指向右兄弟
int data//用于存放数据
实现方式的逻辑结构如下图： 
但其实我们直接应用普通的树的情况并不多，所以我们考虑树的一种应用更广泛的特殊情况即：二叉树。
二叉树
什么是二叉树
最大的度为2的树，注意是最大的树，二叉树中也可以有度为0和1的节点。
两种特殊的二叉树
满二叉树
所有非叶子节点的度为2，所有叶子节点都在最后一层。
完全二叉树
完全二叉树满足两个特点：
1.前n-1层都是满的
2.最后一层不满但是从左到右是连续的。
这两棵树就是完全二叉树。
这两棵树中前一棵树没有满足最后一层从左到右是连续的，后一棵没有满足最后一层之前都是满的。
二叉树的性质
- 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.
- 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1.
- 对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0＝n2＋1
- 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log2(n+1). (ps：log2(n+1)是log以2为
底，n+1为对数) - 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对
对于序号为i的结点有： - 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
- 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
- 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子
二叉树的存储
对于一般的树来说，左孩子右兄弟的存储方法是最优的，但是对于二叉树来说，杀鸡焉用宰牛刀，由于一个节点最大的度就为2，不如存储它的两个子节点的地址作为二叉树节点的结构。
节点的定义：
struct TreeNode{
struct TreeNode* leftchild;//左孩子节点
struct TreeNode* rightchild;//右孩子节点
int data;
它的逻辑结构为下图：
堆
什么是堆
堆是一种特殊的二叉树，是一种数据的存储方式，我们在数据结构中所说的栈和堆与操作系统中的栈和堆是两种完全不同的概念。堆是一个完全二叉树。
堆的分类及特点
堆分为大堆和小堆：
大堆：树中任何一棵子树中，父节点的data值都大于等于其子节点的data值。
小堆：树中任何一棵子树中，父节点的data值都小于等于其子节点的data值。
堆的作用
数据结构中引入堆这个概念可以解决两类问题：
1.堆排序：是一种常用的排序算法。
2.topK问题：即在一组数中寻找最大的前K个数。下面要使用大堆实现，所以要寻找一组数中最小的十个数。
堆的实现
堆的插入（建立大堆）
void HeapPush(HP* hp, DataType x)
{
assert(hp);
if (hp->size == hp->capacity)
{
int newcapacity = (hp->size == 0) ? 4 : hp->capacity * 2;
DataType* tmp = (DataType*)realloc(hp->a, sizeof(DataType)*newcapacity);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
hp->a = tmp;
hp->capacity = newcapacity;
}
}//如果空间不够进行扩容
hp->a[hp->size] = x;
hp->size++;//将元素插入末尾
Adjustup(hp->a, hp->size - 1);//进行向上调整。
}
由于我们是使用顺序表来建立的堆，堆的物理结构实际上就是连续存储的数组，我们将它看成堆。
堆插入一共分为两个步骤：
1.将要插入的元素插入堆的末尾。
2.使用向上调整算法进行调整。
将插入元素放入末尾很容易，下面我们来实现向上调整算法，向上调整算法即将插入元素后的结构再一次调整成堆。
void Adjustup(DataType* a, int child)
{
assert(a);
int parent = (child - 1) / 2;
while (child > 0)//当child小于0的时候停止
{
if (a[parent] < a[child])
{
Swap(&a[parent], &a[child]);
child = parent;
parent = (parent - 1) / 2;//比较父亲节点与孩子节点如果父亲比孩子小则交换
}
else
{
break;//当父节点大于子节点的时候停止
}
}
}
我们根据流程图来理解这一段代码。
1.首先我们将要插入的节点插入堆的末尾。并记录它的下标为child，并将其父亲节点的下标记为parent。
2.比较child和parent的值，由于建立的是大堆，所以当父亲节点的值小于孩子节点时，两者交换位置。
3.更新child的值为parent，更新parent的值为新child的父亲节点，继续进行比较。
4.当父亲节点与孩子节点重合（即新插入的节点是堆顶），或者当父亲节点大于孩子节点的时候，循环停止进行。
注意根据孩子节点找父亲节点的方式在二叉树的性质中提到过，即parent=2*child+1。
以上就是向上调整算法，实际上就是把末尾的元素向上进行调整使结构仍为一个堆。
这是插入后的效果。
堆的删除
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.将堆顶元素与最后一个元素互换位置，并将堆的大小-1（为了排除堆顶元素）。
2.利用向下调整算法将换到上面的最后一个元素进行向下调整使扔构成一个堆。
下面我们来实现向下调整算法。
void Adjustdown(DataType* a, int n, int parent)
{
assert(a);
int child = 2 * parent + 1;
while (child < n)
{
if (child + 1 < n && a[child + 1] > a[child])
{
child++;
}//将child置为最大的孩子节点
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}//当child大于parent时进行交换
else
{
break;
}
}
}
我们按照流程图来理解。
1.首先我们要删除的是99这个元素，在将99和34交换之后99就已经删除了，99不参与任何比较。
2.交换之后进行向下调整，使用parent记录34的坐标，使用child记录34的最大孩子的坐标，这里需要对两个孩子进行比较。
3.如果child记录的元素比parent大则交换，并将parent的值置为child，child置为新parent的最大孩子节点。
4.在当child超出数组范围的时候或者当孩子节点小于父亲节点的时候停止。否则循环继续进行。
这里就是堆删除的效果。
堆排序
堆最常用的功能就是进行排序，时间复杂度可以为O(NlogN)。
void HeapSort(DataType* a, int n)
{
int i;
for (i=(n-2)/2; i >= 0; i--)
{
Adjustdown(a, n, i);//第一次建立堆
}
for (int end = n - 1; end > 0; --end)
{
Swap(&a[end], &a[0]);
Adjustdown(a, end, 0);//每一次将堆顶元素与最后一个互换然后再重新建立堆
}
}
堆排序一共分为两步：
1.对所有有子节点或者子树的节点进行从左向右，从上向下进行向下调整。**向下调整的本质是找出一棵最小二叉树中节点的最大值。**所以最后调整之后建立了一个堆，堆顶点是这组数的最大值。
2.交换堆顶点与最后一个元素，在堆中对最后一个元素进行向下调整（不包含最后一个元素）。【这里和删除时一样的】，从而找出次大的数。
总结一下就是首先明确堆顶的元素是最大的，记录最大的元素，然后排除最大元素再建立一个堆，仍然找出最大元素，然后循环下去。
下面我们用流程图来理解一下。
下面对每一张图进行解释：
1.首先我们拿到了一组数：3,7,2,6,0,1,9,5,4,35，我们先把它们画成堆的形式。
2.从3这个节点开始，依次对6,9,7,0的位置（作为父节点）进行向下调整，成功建立一个堆。
3.将堆顶元素即最大元素35与最后一个元素0互换位置。
4.对0进行向下调整，找出堆顶元素即次大元素9，然后将它与末尾的4互换位置。然后再对4进行向下调整依次类推。
最后得到已经排好序的堆。本质其实就是把最大的元素依次插入到末尾。
最后建立的堆的结果如上图。
TopK问题
TopK问题是寻找一组数中最大的K个元素，但是博主建立的是大堆所以能找到最小的K个值，建立小堆找最大的K个值同理。
void HeapTopK(DataType* a, int n,int k)
{
HP hp;
HeapInit(&hp);
assert(a);
for (int i = 0; i < k; i++)
{
HeapPush(&hp, a[i]);
}//前K个元素入堆
for (int i = k; i < n; i++)
{
if (a[i] < HeapTop(&hp))
{
HeapPop(&hp);
HeapPush(&hp, a[i]);
}
}//将剩余的元素与堆顶元素进行比较，如果比它小就入堆
HeapPrint(&hp);
HeapDestroy(&hp);
}
TopK问题分为两步
1.首先建立一个大小为K的堆（可以利用堆插入），将这组数中前K个元素放入堆中，此时堆顶是这K个元素中的最大值。
2.将这组数中剩余的元素与堆顶的数比较，如果比堆顶的数小就将堆顶元素删除，将该元素入堆。依次循环下去。
我们用图来理解一下
假设要寻找3,7,2,6,0,1,9,5,4,35这组树的最小的四个数。
看这个例子，首先将这组数的前四个元素7,6,2,3放入堆中，然后将0与堆顶元素7进行比较，比7小，所以7出堆，0入堆，向下调整形成堆，
此时堆顶元素为6，然后用1与6进行比较，6出堆，1入堆，以此类推，可以得到最后堆中剩下的元素就是最小的4个元素。
堆的所有代码（已经过完整测试）
heap.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#define DataType int
//构建堆的节点--顺序表
typedef struct Heap {
int* a;
int size;
int capacity;
}HP;
void HeapInit(HP* hp);//初始化
void HeapDestroy(HP* hp);//销毁堆
void HeapPrint(HP* hp);//打印堆
bool HeapEmpty(HP* hp);//判断堆空
int HeapSize(HP* hp);//堆的大小
DataType HeapTop(HP* hp);//取堆顶元素
void Swap(DataType* x, DataType* y);//交换两个元素
void HeapPush(HP* hp, DataType x);//堆插入建大堆
void Adjustup(DataType* a,int child);//向上调整算法
void HeapPop(HP* hp);//堆删除
void Adjustdown(DataType* a,int n, int parent);//向下调整算法
void HeapSort(DataType* a, int n);//堆排序
void HeapTopK(DataType* a, int n,int k);//TopK问题
heap.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"heap.h"
//堆的初始化
void HeapInit(HP* hp)
{
assert(hp);
hp->size = hp->capacity = 0;
hp->a = NULL;//将堆中元素的个数置为0，指向堆中元素的指针置为空
}
void HeapDestroy(HP* hp)
{
assert(hp);
free(hp->a);//顺序表建立堆，根据free()函数性质可以直接释放首元素从而释放整个堆
hp->size = hp->capacity = 0;//将堆中元素个数置为0
}
//打印整个堆
void HeapPrint(HP* hp)
{
assert(hp);
int i;
for (i = 0; i < hp->size; i++)
{
printf("%d ", hp->a[i]);
}
printf("\n");
}
//判断堆空
bool HeapEmpty(HP* hp)
{
assert(hp);
return hp->size == 0;//当size为0返回true,当不为0返回false
}
//计算堆的大小
int HeapSize(HP* hp)
{
assert(hp);
return hp->size;
}
//得到堆顶元素
DataType HeapTop(HP* hp)
{
assert(hp);
assert(hp->a);//需要判断指向堆的指针，和堆中指向元素的指针都不为空
return hp->a[0];
}
//交换两个元素
void Swap(DataType* x, DataType* y)
{
DataType tmp=0;
tmp = *x;
*x = *y;
*y = tmp;
}
//堆的插入
void HeapPush(HP* hp, DataType x)
{
assert(hp);
if (hp->size == hp->capacity)
{
int newcapacity = (hp->size == 0) ? 4 : hp->capacity * 2;
DataType* tmp = (DataType*)realloc(hp->a, sizeof(DataType)*newcapacity);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
hp->a = tmp;
hp->capacity = newcapacity;
}
}
hp->a[hp->size] = x;
hp->size++;
Adjustup(hp->a, hp->size - 1);
}
//向上调整算法建立大堆
void Adjustup(DataType* a, int child)
{
assert(a);
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[parent] < a[child])
{
Swap(&a[parent], &a[child]);
child = parent;
parent = (parent - 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(DataType* a, int n, int parent)
{
assert(a);
int child = 2 * parent + 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 HeapSort(DataType* a, int n)
{
int i;
for (i=(n-2)/2; i >= 0; i--)
{
Adjustdown(a, n, i);
}
for (int end = n - 1; end > 0; --end)
{
Swap(&a[end], &a[0]);
Adjustdown(a, end, 0);
}
}
//TopK问题
void HeapTopK(DataType* a, int n,int k)
{
HP hp;
HeapInit(&hp);
assert(a);
for (int i = 0; i < k; i++)
{
HeapPush(&hp, a[i]);
}
for (int i = k; i < n; i++)
{
if (a[i] < HeapTop(&hp))
{
HeapPop(&hp);
HeapPush(&hp, a[i]);
}
}
HeapPrint(&hp);
HeapDestroy(&hp);
}
test.c(测试用)
#define _CRT_SECURE_NO_WARNINGS 1
#include"heap.h"
void menu()
{
printf("****1.堆插入****2.堆删除****\n");
printf("****3.判断堆空**4.取堆顶元素\n");
printf("****0.销毁堆****************\n");
}
int main()
{
//测试堆排序和TopK问题
//printf("written by lonely little boy\n");
/*int i;
int a[10] = { 3,7,2,6,0,1,9,5,4,35 };
HeapSort(a, 10);
for (i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
printf("\n");
HeapTopK(a, 10, 4);
return 0;*/
HP hp;
HeapInit(&hp);
HeapPush(&hp, 1);
HeapPush(&hp, 9);
HeapPush(&hp, 8);
HeapPush(&hp, 34);
HeapPush(&hp, 90);
HeapPush(&hp, 0);
HeapPush(&hp, 17);
HeapPush(&hp, 56);
HeapPush(&hp, 21);
HeapPrint(&hp);
int input = 0;
do {
menu();
scanf("%d", &input);
int x;
switch (input)
{
case 1:scanf("%d", &x);
HeapPush(&hp, x);
HeapPrint(&hp);
break;
case 2:HeapPop(&hp);
HeapPrint(&hp);
break;
case 3:if (x = HeapEmpty(&hp))
{
printf("Empty\n");
}
else
{
printf("not Empty\n");
}
break;
case 4:x = HeapTop(&hp);
printf("%d\n", x);
break;
case 0:HeapDestroy(&hp);
break;
default:printf("wrong type\n");
break;
}
} while (input);
return 0;
}
代码已经经过测试可以直接使用，需要可以自取。
总结一下，其实堆一般用来找最大值即它的堆顶元素，它的本质就是可以在三个数中挑选出最大的作为“根”节点，说堆是一个存储结构，我觉得不如把它当做一个程序来看，这个程序可以自动将最大的数显示出来。
链式二叉树
在堆中我们使用了顺序表来实现堆，而在建立链式二叉树时，我们采用真正的树结构来建立，即使用左右孩子节点法来建立链式二叉树。
链式二叉树本身是没有什么意义的，我们要在其基础上增加一些性质才有意义。比如搜索二叉树，哈夫曼树等。这里只介绍一些基础操作。
链式二叉树节点的建立
BTNode* BuyNode(DataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
printf("failed\n");
exit(-1);
}
else
{
node->left = node->right = NULL;//将左右子树都置为空
node->val = x;
}
}
这里建立了链式二叉树的一个节点。
链式二叉树的遍历（前序，中序，后序）
//前序遍历，中左右
void PreOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%c ", root->val);
PreOrder(root->left);
PreOrder(root->right);
}
//中序遍历，左中右
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%c ", root->val);
InOrder(root->right);
}
//后序遍历，左右中
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%c ", root->val);
}
由于都是使用了递归进行遍历，因此这里只介绍前序遍历，其他两种遍历方法和前序的是一样的。
我们使用这样一棵树来举例子：
我们知道前序遍历的方式是以中->左->右来进行的。
写递归程序的方法
我们以前序遍历来举例。
1，先写断言，判断传参是否正确
第一点无论是否要书写递归，都是必须要做的第一步。
2，然后写递归的终止条件
在前序遍历中，我们需要以中左右的顺序来打印节点，显然截止条件是某一个节点为空，即没有左子树和右子树。
因此当节点为空的时候我们进行打印。
3，把每递归看成一个宏观的过程
我们要写的只是最后一步的过程
我们遍历以root为根的二叉树和遍历以root->left为根的二叉树使用的方法和函数是相同的。都是使用函数PreOrder
所以图可以抽象成：
此时前序遍历以root为根的二叉树的函数是PreOrder(root)
前序遍历以root->left为根的二叉树的函数是PreOrder(root->left)
前序遍历以root->right为根的二叉树的函数是PreOrder(root->right)
我们要写的就是把这三者关联起来。
既然是前序遍历，遵循的是中左右的顺序，即先打印根节点，然后打印左子树的节点，最后打印右子树的节点。
所以他们的顺序是这样的。
printf("%c ", root->val);
PreOrder(root->left);
PreOrder(root->right);
这里的关键就是我们要认为PreOrder(root->left)和PreOrder(root->right)已经把左右子树遍历完了，虽然你什么都没做
因此说这是一个宏观的过程的理解。
二叉树叶子节点的个数
我们依然使用上述方法来解决这个问题：
断言这里就不多说了。
先写递归截止条件
第一种情况，遇到的是空，此时返回的应该是0，因为NULL不是叶子节点。
第二种情况，遇到的是叶子节点，叶子节点的特点是它的左右子树都为空，此时返回1。
宏观过程理解
BinaryNodeTreeSize（root）表示的是以root为根的叶子节点的个数。
BinaryNodeTreeSize(root->left)表示的是以root->left为根的叶子节点的个数。
BinaryNodeTreeSize(root->right)表示的是以root->right为根的叶子节点的个数。
我们发现它们的关系是：BinaryNodeTreeSize（root）=BinaryNodeTreeSize(root->left)+BinaryNodeTreeSize(root->right)+1
因此我们要返回的就是BinaryNodeTreeSize(root->left)+BinaryNodeTreeSize(root->right)+1
整个代码就写好了：
int BinaryNodeTreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}//终止条件
return BinaryNodeTreeSize(root->left) + BinaryNodeTreeSize(root->right);//宏观过程
}
二叉树的深度
我们依然可以采用这个思路，首先是终止条件：
当为空时，返回0，当不为空时返回1。
树与左右子树的深度关系是，树的深度等于左右子树的最大深度加1。
可以检测一下自己，代码我放在后面了。
第K层节点个数
第K层节点的个数等于左右子树第K-1层节点个数之和，根据这一点写递归代码。
查找值为x的节点
我们采用前序遍历的方式进行查找：
BTNode* BinaryTreeFind(BTNode* root, DataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->val == x)
{
return root;
}
if (BinaryTreeFind(root->left,x))
{
return BinaryTreeFind(root->left, x);
}
if (BinaryTreeFind(root->right, x))
{
return BinaryTreeFind(root->right, x);
}
return NULL;
}
.h文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#define DataType char
typedef struct TreeNode
{
DataType val;
struct TreeNode* left;
struct TreeNode* right;
}BTNode;
BTNode* BuyNode(DataType x);//建立树的节点
void PreOrder(BTNode* root);//前序遍历
void InOrder(BTNode* root);//中序遍历
void PostOrder(BTNode* root);//后序遍历
int BinaryNodeTreeSize(BTNode* root);//二叉树叶子节点个数
int BinaryTreelevelKSize(BTNode* root, int k);//第k层节点个数
int BinaryTreeDepth(BTNode* root);//二叉树的深度
BTNode* BinaryTreeFind(BTNode* root, DataType x);//查找值为x的节点
void BinaryTreeDesTroy(BTNode* root);//二叉树的销毁
.c文件
#define _CRT_SECURE_NO_WARNINGS 1
#include "Tree.h"
//建立节点
BTNode* BuyNode(DataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
printf("failed\n");
exit(-1);
}
else
{
node->left = node->right = NULL;
node->val = x;
}
}
//前序遍历，中左右
void PreOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%c ", root->val);
PreOrder(root->left);
PreOrder(root->right);
}
//中序遍历，左中右
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%c ", root->val);
InOrder(root->right);
}
//后序遍历，左右中
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%c ", root->val);
}
//二叉树叶子节点个数
int BinaryNodeTreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
return BinaryNodeTreeSize(root->left) + BinaryNodeTreeSize(root->right);
}
//第k层节点个数
int BinaryTreelevelKSize(BTNode* root, int k)
{
assert(k >= 1);
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return BinaryTreelevelKSize(root->right, k - 1) + BinaryTreelevelKSize(root->left, k - 1);
}
//二叉树的深度
int BinaryTreeDepth(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return BinaryTreeDepth(root->left)>BinaryTreeDepth(root->right)? BinaryTreeDepth(root->left)+1: BinaryTreeDepth(root->right)+1;
}
//查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, DataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->val == x)
{
return root;
}
if (BinaryTreeFind(root->left,x))
{
return BinaryTreeFind(root->left, x);
}
if (BinaryTreeFind(root->right, x))
{
return BinaryTreeFind(root->right, x);
}
return NULL;
}
void BinaryTreeDesTroy(BTNode* root)
{
if (root == NULL)
{
return;
}
BinaryTreeDesTroy(root->left);
BinaryTreeDesTroy(root->right);
free(root);
}
测试文件
#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"
int main()
{
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');
nodeA->left = nodeB;
nodeA->right = nodeC;
nodeB->left = nodeD;
nodeC->left = nodeE;
nodeC->right = nodeF;
nodeF->right = nodeG;
BTNode* root = nodeA;
PreOrder(root);
printf("\n");
InOrder(root);
printf("\n");
PostOrder(root);
printf("\n");
int m;
m = BinaryNodeTreeSize(root);
printf("%d\n", m);
int n;
n=BinaryTreelevelKSize(root, 3);
printf("%d\n", n);
BinaryTreeDesTroy(root);
}
代码测试结果
总结
首先感谢看到这里的你，这是目前我写的最长的一篇文章了，比动态规划的篇多了5000字。
由于代码是在自习室敲的，所以特此鸣谢自习室的同学们没有给我以“正义的群殴”，从一些人狰狞的表情和通红的眼眶我能看出他们对我敲代码的支持与理解（发抖），也许他们认为在自习室打字的人也不能全盘否定，一棍子打死，比如有像我这样一心为大家输出文章的爱党爱国的积极码农分子（泪目），所以就按耐住了怒火。这里说一声抱歉。
如果你看完文章觉得对你有帮助，一定要三连啊，因为一个白嫖之后三连点赞的人，一定是一个高尚的人，一个纯粹的人，一个脱离的低级趣味的人，一个有益于人民的人。三连一下吧球球了（卑微）。