【数据结构从0到1】第四篇：二叉树_计算机网络中二叉树的零一的意义

---

前言

本篇是介绍关于树的基本概念、性质，进而对一个特殊的树（二叉树）进行重点介绍，而在二叉树中，我们又介绍堆的概念、性质、代码实现一个堆以及堆的应用。最后再实现二叉树的遍历、来让我们对二叉树有一定的认识。但是本篇不讨论如何用二叉树存储数据，因为一颗普通的二叉树对数据存储过于复杂，而如果用C语言来实现更是难上加难，对我们没有太大的用处，所以关于存储数据的树，我们之后用更高阶的语言（C++）实现，类似搜索二叉树、平衡搜索二叉树、AVL树、红黑树到最后的B树。

一、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 树的表示

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

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

用一张图片形象的表示：

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

二、叉树概念及结构

2.1概念

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

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

用图片表示就是：

从上图可以看出：

• 1. 二叉树不存在度大于2的结点
     比特科技
• 2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
     注意：对于任意的二叉树都是由以下几种情况复合而成的：

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

2.2现实中的二叉树：

上面这两种图片都可以形象的表示出来二叉树。

2.3 特殊的二叉树：

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

2.4 二叉树的性质

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. 对于具有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否则无右孩子

2.5 二叉树的存储结构

1. 顺序存储
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

2. 链式存储
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链。

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

3.1 二叉树的顺序结构

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

3.2 堆的概念及结构

如果有一个关键码的集合K = {K0 ，K1 ，K2 ，K3…，K(n-1) }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <=K(2i+1) (2i-1为下标) 且 Ki<=K(2i+2)（2i+2为下标） ( Ki>=K(2i+1) 且 Ki>=(2i+2) ) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
概念有点复杂，用一张图片来表示：

堆的性质：

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

3.3 堆的实现

Heap.h

#pragma once

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

typedef int HPDataType;
//完全二叉树用数组实现
//假设先建一个小堆
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

void HeapInit(HP* hp);
void HeapDestroy(HP* hp);
void HeapPrint(HP* hp);
void HeapPush(HP* hp, HPDataType x);
void HeapPop(HP* hp);//删堆顶数据
HPDataType HeapTop(HP* hp);
bool HeapEmpty(HP* hp);
int HeapSize(HP* hp);

void HeapSwap(HPDataType* px, HPDataType* py);//交换两个数
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
26
27
28
29
30
31
32

Heap.c

#define _CRT_SECURE_NO_WARNINGS
#include"Heap.h"

void HeapInit(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->capacity = hp->size = 0;
}

void HeapDestroy(HP* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	free(hp->a);
	hp->capacity = hp->size = 0;
}

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

void HeapSwap(HPDataType* px, HPDataType* py)
{
	HPDataType tmp = *px;
	*px = *py;
	*py = tmp;
}

void AdjustUp(HPDataType* a, int child)//插入时向上调整数据
{
	assert(a);
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			HeapSwap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}

}

void HeapPush(HP* hp, HPDataType x)
{
	assert(hp);
	//插入数据时是否已满
	if (hp->capacity == hp->size)
	{
		int newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newCapacity);
		if (NULL == tmp)
		{
			printf("realloc fail");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newCapacity;
	}

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

	//插入时向上调整数据
	AdjustUp(hp->a, hp->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])
		{
			HeapSwap(&a[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapPop(HP* hp)//删堆顶数据
{
	assert(hp);
	assert(!HeapEmpty(hp));
	//先交换堆顶的数据和最后一个的数据
	HeapSwap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;

	//堆顶数据向下调整
	AdjustDown(hp->a, hp->size, 0);
	
}

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

bool HeapEmpty(HP* hp)
{
	assert(hp);
	return hp->size == 0;
}

int HeapSize(HP* hp)
{
	assert(hp);
	return hp->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
135
136

3.4堆的应用

3.4.1 堆排序

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

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

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

void HeapSort(int* a, int n);//堆排序

1
2

void HeapSort(int* a, int n)//堆排序
{
	//假设排升序
	// 若果建小堆的话，我们在排升序的话时间复杂度就是O(n^2),没有意义
	// 所以我们如果排升序的话就建大堆，排降序的话就建小堆   
	//方法一,从1开始往上调
	/*for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}*/
	//方法二。从倒数第一个不为叶子节点开始网下调
	//建堆的复杂度为O(n)
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	//依次选数
	for (int end = n - 1; end > 0; end--)
	{
		HeapSwap(&a[end], &a[0]);
		/*再调堆，选出次小的数*/
		AdjustDown(a, end, 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

3.4.2 TOP-K问题

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

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

void TestTopk();//查找前k个数
void PrintTopK(int* a, int n, int k);//找出前k个数，打印前k个数
1
2

void PrintTopK(int* a, int n, int k)
{
	HP hp;
	HeapInit(&hp);
	int i = 0;
	//	建立一个k个数的堆
	//假设找出前k个最大的数，就建小堆
	for (i = 0; i < k; i++)
	{
		HeapPush(&hp, a[i]);
	}
	//将剩下的n-k个数插入堆
	//如果之前建的是大堆，插入数的时候就会堵住
	//相反建的小堆的话，来的数越大就会越往下沉
	for (i = k; i < n; i++)
	{
		HPDataType top = HeapTop(&hp);
		//判断堆顶的数据和插入的数据大小
		if (a[i] > top)
		{
			HeapPop(&hp);
			HeapPush(&hp, a[i]);
		}
	}

	//打印数据
	for (i = 0; i < k; i++)
	{
		printf("%d ", hp.a[i]);
	}
	printf("\n");
	HeapDestroy(&hp);
}

void TestTopk()
{
	//假设在文件中有10000个数据
	int n = 10000;
	int* a = (int*)malloc(sizeof(int) * n);
	srand(time(0));
	for (int i = 0; i < n; ++i)
	{
		a[i] = rand() % 1000000;
	}
	//随机位置设置前10个数
	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;
	//找出前10个数
	PrintTopK(a, n, 10);
}
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

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

4.1 前置说明

在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入，为了降低大家学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。
二叉树是：

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

4.2二叉树的遍历

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

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础

我们先手动建立一颗树

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

BTNode* CreatBinaryTree()//建一个二叉树
{
	BTNode* A = BuyNode('A');
	BTNode* B = BuyNode('B');
	BTNode* C = BuyNode('C');
	BTNode* D = BuyNode('D');
	BTNode* E = BuyNode('E');
	BTNode* F = BuyNode('F');

	A->left = B;
	A->right = C;
	B->left = D;
	C->left = E;
	C->right = F;
	return A;
}
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

此时这棵树用图片表示就是：

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

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

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

// 二叉树前序遍历
void PreOrder(BTNode* root);
// 二叉树中序遍历
void InOrder(BTNode* root);
// 二叉树后序遍历
void PostOrder(BTNode* root);
1
2
3
4
5
6

前序、中序和后续遍历的代码实现：

void PrevOrder(BTNode* root)//前序遍历
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	else
	{
		printf("%c ", root->data);
		PrevOrder(root->left);
		PrevOrder(root->right);
	}
}

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

void PostOrder(BTNode* root)//后序遍历
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	else
	{
		PostOrder(root->left);
		PostOrder(root->right);
		printf("%c ", root->data);
	}
}
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

4.2.2 层序遍历

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

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

BTNode* CreatBinaryTree()//建一个二叉树
{
	BTNode* A = BuyNode('A');
	BTNode* B = BuyNode('B');
	BTNode* C = BuyNode('C');
	BTNode* D = BuyNode('D');
	BTNode* E = BuyNode('E');
	BTNode* F = BuyNode('F');

	A->left = B;
	A->right = C;
	B->left = D;
	C->left = E;
	C->right = F;
	return A;
}
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

由于层序遍历的性质我们选择用队列实现层序遍历：

//层序遍历
void LevelOrder(BTNode* root);
1
2

代码实现

//层序遍历
//1.先入根
//2.当前节点出来，把孩子带进去，这样上一层出来的时候带入下一层
//3.队列为空的时候就说明最后一层就没有节点了。
void LevelOrder(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 != NULL)
		{
			QueuePush(&q, front->left);

		}
		if (front->right != NULL)
		{
			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

如果对栈代码不熟悉可以参考下面这篇博客：
【数据结构从0到1】第三篇：栈和队列

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

我们根据上面树的层序遍历，可以依照同样的方法来判断一颗树是否是完全二叉树：

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);
1
2

代码实现：

// 判断二叉树是否是完全二叉树
//1.先入根
//2.当前节点出来，把孩子带进去，这样上一层出来的时候带入下一层
//3.当头节点为空的时候就不在入孩子节点
//4.判断队列里面是否含有非空节点。
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	//先将头节点入进去
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		//
		if (front == NULL)
		{
			break;
		}
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	while(!(QueueEmpty(&q)))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}
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

4.3 节点个数以及高度等

//二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树深度/高度
int BinaryTreeDepth(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
1
2
3
4
5
6
7
8
9
10

代码实现：

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

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	else
	{
		return BinaryTreeLeafSize(root->left) + \
		BinaryTreeLeafSize(root->right);
	}	
}

// 二叉树深度/高度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	else
	{
		//查找左树的深度
		int leftDepth = BinaryTreeDepth(root->left);
		//查找右树的深度
		int rightDepth = BinaryTreeDepth(root->right);
		return leftDepth > rightDepth ? leftDepth + 1: rightDepth + 1;
	}
}

 /*二叉树第k层节点个数*/
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	assert(k >= 1);
	if (root == NULL)
	{
		return 0;
	}
	//求第一层就是1个节点，或则当到了第k减为1，说明就到了第k层，返回1
	if (k == 1)
	{
		return 1;
	}
	else
	{
		//找左树和右树的第k层节点数
		return BinaryTreeLevelKSize(root->left, k - 1) + \
			BinaryTreeLevelKSize(root->right, k - 1);
	}
}

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	//当前节点的值为x，就返回
	if (root->data == x)
	{
		return root;
	}
	else
	{
		//先查找左树上是否有x,找到就返回当前位置
		BTNode* leftRet = BinaryTreeFind(root->left, x);
		if (leftRet != NULL)
		{
			return leftRet;
		}
		//再查找右树上是否有x,找到就返回当前位置
		BTNode* rightRet = BinaryTreeFind(root->right, x);
		if (rightRet != NULL)
		{
			return rightRet;

		}
	}
	//如果左右两树都没有x,就返回空
	return NULL;
}
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

4.5 二叉树的创建和销毁

树的建立：
二叉树的构建及遍历 OJ链接

//思路：1.先通过输入的前序数组将这棵树建立
//      2.中序打印这颗树
#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];
    (*pi)++;
    root->left = CreateTree(str, pi);
    root->right = CreateTree(str, pi);
    return root;
}

void InOrder(struct TreeNode* root)
{
    if(root == NULL)
    {
        return;
    }
    else
    {
        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;
}
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

树的销毁：

// 二叉树销毁
void BinaryTreeDestory(BTNode* root);

1
2
3

代码实现：

// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
}
1
2
3
4
5
6
7
8
9
10
11