文章目录

数据结构之二叉树

数据结构之二叉树

在了解二叉树前，首先要知道什么树。

1. 树

1.1 树的概念

树是一种非线性的数据结构，是由n（n>=0）个（或有限个）结点组成的一个具有层次关系的集合。
把它称作树是因为它的结构看起来像一棵树，只是这棵树是倒着的（根在上，叶在下）。

树有一个特殊的结点，称为根结点。根结点没有先驱结点（根结点之前没有结点或没有结点指向根结点）。

除根结点外，每个结点被分成M（M>0）互不相交的集合T1，T2，T3，… …，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.4 树在实际情况中的应用

表示文件系统的目录树结构（例如windows、linux系统下的文件目录）。

2. 二叉树

2.1 二叉树的概念

二叉树是一种特殊的树。一棵二叉树是有限个结点的集合。该集合：

可以为空。

由一个根结点和两个被称为左子树和右子树的二叉树组成。

二叉树的度不大于2（其某个结点的后继结点数量不超过2个）。

二叉树的子树有左右之分，次序不能颠倒。因此，二叉树是有序树。

对于任意的二叉树，都由以下几种情况复合而成：
在这里插入图片描述

2.2 特殊的二叉树

满二叉树： 一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是，则它就是满二叉树。

完全二叉树： 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。通俗的说：如果一个二叉树只有最后一层和倒数第二层的结点的度小于等于2，且最后一层从右向左连续缺少若干个结点，那么它就是完全二叉树。
完全二叉树度为1的结点只有0或1个。
要注意的是满二叉树是一种特殊的完全二叉树。

2.3 二叉树的性质

若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(h-1) 个结点.

若规定根节点的层数为1，则深度为h的二叉树的最大结点数（当二叉树是满二叉树时）是2^h-1 .

对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有 n0＝n2 ＋1

若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log(n+1). (ps：log(n+1)是以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，则无右孩子

来个小测试吧：

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
	A 不存在这样的二叉树
	B 200
	C 198
	D 199
2.下列数据结构中，不适合采用顺序存储结构的是（ ）
	A 非完全二叉树
	B 堆
	C 队列
	D 栈
3.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
	A n
	B n+1
	C n-1
	D n/2
4.一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）
	A 11
	B 10
	C 8
	D 12
5.一个具有767个节点的完全二叉树，其叶子节点个数为（）
	A 383
	B 384
	C 385
	D 386
答案：
	1.B
	2.A
	3.A
	4.B
	5.B

解析：
在这里插入图片描述

2.4 二叉树的存储结构

二叉树一般使用顺序结构和链式结构存储。

顺序存储：
顺序结构存储就是使用数组来存储。使用数组一般只适合表示完全二叉树，因为如果不是完全二叉树，使用数组就会造成空间的浪费。实际应用中，只有堆才会使用数组来存储。
二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
链式存储：
链式结构存储就是使用链表来存储。用链表表示二叉树，就是用链来指示元素的逻辑关系。通常，链表中每个结点由三个域组成：数据域和左右指针域。左右指针分别存储该结点左孩子和右孩子所在的链结点的地址。
链式结构又分为二叉链和三叉链，二叉树用的都是二叉链。

在这里插入图片描述

代码表示：

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 二叉树的顺序结构

上文已经了解到，普通的二叉树是不适合用数组来存储的，因为可能会造成空间浪费；完全二叉树才适合用顺序结构存储。下面会引入一个“堆”的概念：
实际中，我们通常把堆（一种二叉树）使用顺序结构的数组存储。（注意：这里的堆和操作系统虚拟进程地址空间中的堆是两回事，前者是一种数据结构，后者是操作系统中管理内存的一块区域划分）
在这里插入图片描述

3.2 堆的概念及结构

在这里插入图片描述
堆的性质：

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

知道了什么是堆后，练练手吧：

1.下列关键字序列为堆的是：（）
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
2.已知小根堆为8,15,10,21,34,16,12，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次
数是（）。
A 1
B 2
C 3
D 4
3.一组记录排序码为(5 11 7 2 3 17),则利用堆排序方法建立的初始堆为
A(11 5 7 2 3 17)
B(11 5 7 2 17 3)
C(17 11 7 2 3 5)
D(17 11 7 5 3 2)
E(17 7 11 3 5 2)
F(17 7 11 3 2 5)
4.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后，其结果是（）
A[3，2，5，7，4，6，8]
B[2，3，5，7，4，6，8]
C[2，3，4，5，7，8，6]
D[2，3，4，5，6，7，8]

答案
1.A
2.C
3.C
4.C

3.3 堆的实现

3.3.1 堆的相关声明

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);
// 堆的判空
bool HeapEmpty(Heap* hp);

3.3.2 堆的向下调整算法

给出一个数组，这个数组逻辑上可以看作一棵完全二叉树。

我们可以通过从根结点开始的向下调整算法，把它调整成一个小堆。
向下调整算法有一个前提：左右子树必须是堆，才能调整。

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

在这里插入图片描述

// 向下调整（这里以调整成小堆为例）
static void AdjustDown(HPDataType* arr, int n, int parent)
{
	assert(arr);
	//找小的孩子，将其调整到父亲位置
	int lowerChild = parent * 2 + 1;
	while (lowerChild < n)
	{
		//较小的孩子
		if (lowerChild + 1 < n && arr[lowerChild] > arr[lowerChild + 1])
		{
			lowerChild++;
		}
		//调整
		if (arr[lowerChild] < arr[parent])
		{
			Swap(&arr[lowerChild], &arr[parent]);//Swap函数需要提前实现
			
			parent = lowerChild;
			lowerChild = parent * 2 + 1;
		}
		else
		{
			break;//不需要调整，即满足小堆，调整结束
		}
	}
}

既然有向下调整，那有没有向上调整呢？
当然是有的，下文会给出介绍。

3.2.3 堆的创建

同样给出一个数组，这个数组逻辑上可以看作一颗完全二叉树，但其还不是一个堆。下面我们通过向下调整算法把它调整成一个堆。

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

在这里插入图片描述
代码表示：

void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	assert(hp);
	assert(a);
	//创建堆，不建议直接对给出的数组进行建堆。
	//因为如果直接对直接给出的数组进行建堆，在销毁堆时，不知道当前数组是原数组，还是动态开辟的数组，也就无法对其释放空间。
	//不释放空间，如果是动态开辟的数组，就会造成内存泄漏。
	hp->a = (HPDataType*)malloc(n * sizeof(HPDataType));
	if (hp->a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	hp->size = 0;
	hp->capacity = n;
	int i = 0;
	for (i = 0; i < n; i++)
	{
		hp->size++;
		hp->a[i] = a[i];
		AdjustDown(hp->a, hp->size, 0);
	}
}

3.2.3 建堆时间复杂度

向下调整：
向上调整：

可以看出，只是向上调整的最后一层结点的移动步数便与向下调整的前h-1层结点的移动步数相当。所以，建堆时，向下调整的算法复杂度要比向上调整的算法复杂度小得多。两者的区别就在于是否要调整最后一层的结点。（最后一层的结点个数几乎占总节点个数的一半，且若是向上调整，最后一层结点就需要向上移动h-1层，这就是为什么向上调整的最后一层结点的移动步数便与向下调整的前h-1层结点的移动步数相当）

3.2.4 堆的插入

先将要插入的数据插入到数组的尾上，再进行向上调整算法，知道满足堆。
在这里插入图片描述
代码表示：

//向上调整
static void AdjustUp(HPDataType* arr, int child)
{
	assert(arr);

	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[child] < arr[parent])
		{
			//交换
			Swap(&arr[child], &arr[parent]);//需要提前实现
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
// 堆的插入
void HeapPush(Heap* 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, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newCapacity;
	}
	//插入数据
	hp->a[hp->size] = x;
	++hp->size;
	//向上调整顺序
	AdjustUp(hp->a, hp->size-1);
}

3.2.5 堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
在这里插入图片描述
代码表示：

// 堆的删除
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);
	
}

3.2.6 堆的应用之堆排序

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

建堆
- 升序：建大堆
- 降序：建小堆
利用堆删除思想来进行排序
- 如果我们要给数组升序排序，需要先找到最大的数字，将其放在数组末尾。然后找次大的，重复此过程。
- 如果我们要给数组降序排序，需要先找到最小的数字，将其放在数组末尾。然后找次小的，重复此过程。
- 这就是上面建堆为何要升序建大堆，降序建小堆的原因了。

在这里插入图片描述
代码展示：

// 对数组进行堆排序
void HeapSort(int* a, int n)
{
	assert(a);

	//降序  建小堆
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

	//降序排序
	i = 1;
	while (i < n)//n-1次
	{
		Swap(&a[0], &a[n - i]);
		AdjustDown(a, n - i, 0);
		++i;
	}
}

时间复杂度：

建堆：O(n)
排序：O(n*logn)
综合：O(n+n*logn)近似于O(nlogn)

3.2.7 Top-K问题

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

用数据集合中前K个元素来建堆
- 前k个最大的元素，则建小堆
- 前k个最小的元素，则建大堆
用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

在这里插入图片描述
代码展示：

void PrintTopK(int* a, int n, int k)
{
	assert(a);

	//建小堆  堆中存放k个数据
	int i = 0;
	for (i = (k - 2) / 2; i >= 0; --i)
	{
		AdjustDown(a, k, i);
	}

	for (i = k; i < n; i++)
	{
		if (a[i] > a[0])
		{
			a[0] = a[i];
			AdjustDown(a, k, 0);
		}
	}
	for (i = 0; i < k; i++)
	{
		printf("%d ",a[i]);
	}
	printf("\n");
}
void TestTopk()
{
	HPDataType a[] = { 10,5,7,35,67,23,26,15,40 };
	int len = sizeof(a) / sizeof(a[0]);
	PrintTopK(a, len, 3);
}

运行结果：
在这里插入图片描述

3.2.8 堆的源代码

heap.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.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);
// 堆的判空
bool HeapEmpty(Heap* hp);

//打印n个数里卖弄最大/最小的前k个
void PrintTopK(int* a, int n, int k);
//测试PrintTopK
void TestTopk()

// 对数组进行堆排序
void HeapSort(int* a, int n);

heap.c

#include "Heap.h"


// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->capacity = hp->size = 0;
}

//交换两个数
static void Swap(HPDataType* x, HPDataType* y)
{
	*x = *x ^ *y;
	*y = *x ^ *y;
	*x = *x ^ *y;
}
//向上调整
static void AdjustUp(HPDataType* arr, int child)
{
	assert(arr);

	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[child] < arr[parent])
		{
			//交换
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

// 向下调整
static void AdjustDown(HPDataType* arr, int n, int parent)
{
	assert(arr);

	int lowerChild = parent * 2 + 1;
	while (lowerChild < n)
	{
		//较小的孩子
		if (lowerChild + 1 < n && arr[lowerChild] > arr[lowerChild + 1])
		{
			lowerChild++;
		}
		if (arr[lowerChild] < arr[parent])
		{
			Swap(&arr[lowerChild], &arr[parent]);
			parent = lowerChild;
			lowerChild = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

// 堆的构建
// code-1
// 空间复杂度：O(N)
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	assert(hp);
	assert(a);

	hp->a = (HPDataType*)malloc(n * sizeof(HPDataType));
	if (hp->a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	hp->size = 0;
	hp->capacity = n;
	int i = 0;
	for (i = 0; i < n; i++)
	{
		hp->size++;
		hp->a[i] = a[i];
		AdjustDown(hp->a, hp->size, 0);
	}
}
// code-2：把a建成一个堆（不推荐）
//void HeapCreate(Heap* hp, HPDataType* a, int n)
//{
//	assert(hp);
//	assert(a);
//
//	int i = 0;
//	//向上调整  建堆
//	//for (i = 1; i < n; i++)
//	//{
//	//	AdjustUp(a, i);
//	//}
//
//	for (i = (n - 1 - 1) / 2; i >= 0; i--)
//	{
//		AdjustDown(a, n, i);
//	}
//	hp->a = a;
//	hp->capacity = hp->size = n;
//}

// 堆的插入
void HeapPush(Heap* 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, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newCapacity;
	}
	//插入数据
	hp->a[hp->size] = x;
	++hp->size;
	//向上调整顺序
	AdjustUp(hp->a, hp->size-1);
}

// 堆的删除
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)
{
	return hp->size;
}
// 堆的判空
bool HeapEmpty(Heap* hp)
{
	assert(hp);

	return hp->size == 0;
}

//打印n个数里卖弄最大/最小的前k个
void PrintTopK(int* a, int n, int k)
{
	assert(a);

	//建小堆  堆中存放k个数据
	int i = 0;
	for (i = (k - 2) / 2; i >= 0; --i)
	{
		AdjustDown(a, k, i);
	}

	for (i = k; i < n; i++)
	{
		if (a[i] > a[0])
		{
			a[0] = a[i];
			AdjustDown(a, k, 0);
		}
	}
	for (i = 0; i < k; i++)
	{
		printf("%d ",a[i]);
	}
	printf("\n");
}
//测试PrintTopK
void TestTopk()
{
	HPDataType a[] = { 10,5,7,35,67,23,26,15,40 };
	int len = sizeof(a) / sizeof(a[0]);
	PrintTopK(a, len, 3);
}
// 对数组进行堆排序
void HeapSort(int* a, int n)
{
	assert(a);

	//降序  建小堆
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

	//降序排序
	i = 1;
	while (i < n)//n-1次
	{
		Swap(&a[0], &a[n - i]);
		AdjustDown(a, n - i, 0);
		++i;
	}
}

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

4.1 创建二叉树

要对二叉树进行基本的操作前，首先需要创建一棵二叉树。

如果我们对二叉树还不是很了解，可以暂走捷径，手动创建（不推荐）：

BTNode* BinaryTreeCreate(BTDataType* a)
{
	assert(a);

	BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
	assert(n1);
	BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
	assert(n2);
	BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
	assert(n3);
	BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
	assert(n4);
	BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
	assert(n5);
	BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
	assert(n6);
	BTNode* n7 = (BTNode*)malloc(sizeof(BTNode));
	assert(n7);
	BTNode* n8 = (BTNode*)malloc(sizeof(BTNode));
	assert(n8);

	n1->data = a[0];
	n2->data = a[1];
	n3->data = a[2];
	n4->data = a[3];
	n5->data = a[4];
	n6->data = a[5];
	n7->data = a[6];
	n8->data = a[7];

	n1->left = n2;
	n1->right = n3;
	n2->left = n4;
	n2->right = n5;
	n3->left = n6;
	n3->right = n7;
	n4->left = NULL;
	n4->right = NULL;
	n5->left = NULL;
	n5->right = n8;
	n6->left = NULL;
	n6->right = NULL;
	n7->left = NULL;
	n7->right = NULL;
	n8->left = NULL;
	n8->right = NULL;

	return n1;
}

前文已经论述过，二叉树是递归定义的。我们就可以递归创建（推荐）：

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* src, int n, int* pi)
{
	if (src[*pi] == '#' || *pi >= n)
	{
		(*pi)++;
		return NULL;
	}

	BTNode* cur = (BTNode*)malloc(sizeof(BTNode));
	if (cur == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	cur->data = src[*pi];
	(*pi)++;

	cur->left = BinaryTreeCreate(src, n, pi);
	cur->right = BinaryTreeCreate(src, n, pi);

	return cur;
}

4.2 二叉树的遍历

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

在这里插入图片描述

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

按照规则，二叉树的遍历有前序、中序和后序三种递归遍历方式。

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

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

下面主要分析前序遍历图解：
在这里插入图片描述
为了方便理解，下面用较为简单的代码配合图解（此代码图解仅展示函数调用关系，与代码内容无关）：

前序遍历结果：1 2 3 4 5 6
中序遍历结果：3 2 1 5 4 6
后序遍历结果：3 2 5 6 4 1

代码展示：

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

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

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

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

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

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

4.2.2 层序遍历

层序遍历： 除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在
层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层
上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
在这里插入图片描述
那么如何写代码呢？ 使用队列。

// 层序遍历   (C语言下，队列需要自己提前实现)
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		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");

	QueueDestory(&q);
}

趁热打铁：

1.某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为（ ）
A ABDHECFG
B ABCDEFGH
C HDBEAFCG
D HDEBFGCA
2.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树根结点为（）
A E
B F
C G
D H
3.设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为____。
A adbce
B decab
C debac
D abcde
4.某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同一层从左到右）的序列
为
A FEDCBA
B CBAFED
C DEFCBA
D ABCDEF

答案：
1.A
2.A
3.D
4.A

4.3 二叉树结点个数

4.3.1 二叉树总结点个数

结点不为空，就+1，然后递归下去。
为空，返回0.

// 二叉树总结点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	//结点不为空，就+1，然后递归
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

4.3.2 二叉树叶子结点个数

当前结点不为空，且左右子树均为空，就+1，否则+0。
然后递归。

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	//该结点不为空，且左右子树均为空，那么该结点就是叶子结点，就+1，然后递归
	return ((!root->left && !root->right) ? 1 : 0)
		 + BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

4.3.3 二叉树第k层结点个数

保证当前层数是正数。
只有一层，1个结点
然后递归。每次递归，层数k需要减1。

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

	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

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

当前结点为NULL，返回NULL。
当前结点不为NULL
- 当前结点值为目标值，返回当前结点。程序结束。
- 否则，递归下去。先递归左树，找到了就结束；找不到，就再对右树递归；若左右子树都没有找到，就返回NULL。

// 二叉树查找值为x的节点
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)
		return left;
	BTNode* right = BinaryTreeFind(root->right, x);
	if (right)
		return right;

	return NULL;
}

4.4 二叉树高度

比较左子树和右子树的高度，大的那个高度+1就是二叉树高度。（+1是加当前结点所在的一层）

int BinaryTreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;

	int leftHeight = BinaryTreeHeight(root->left);
	int rightHeight = BinaryTreeHeight(root->right);

	return 1 + (leftHeight < rightHeight ? rightHeight : leftHeight);

}

4.5 二叉树的销毁

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

	if (*root)
	{
		BinaryTreeDestory(&(*root)->left);
		BinaryTreeDestory(&(*root)->right);

		free(*root);
		*root = NULL;
	}
}

因为我们是用一个指针变量来接收创建好的二叉树，所以要销毁二叉树，就要把这个数组释放掉，并且置为NULL（防止成为野指针）。而改变一级指针变量，就需要二级指针，因此，传参传的是一级指针的地址，也就是二级指针。

4.6 判断完全二叉树

层序遍历。
判断空结点后续结点是否存在非空。若存在，则不是完全二叉树。

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		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 != NULL)
		{
			QueueDestory(&q);
			return false;
		}
	}
	QueueDestory(&q);
	return true;
}

4.7 二叉树源码

Tree.h：二叉树相关声明

#pragma once

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

typedef char BTDataType;

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

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);
//二叉树高度
int BinaryTreeHeight(BTNode* root);

Queue.h：队列相关声明 （层序遍历和判断完全二叉树需要用到队列）

#pragma once

#include "Tree.h"

typedef BTNode* QDateType;
//结点
typedef struct QueueNode
{
	QDateType data;
	struct QueueNode* next;
	//int size;
}QNode;

//封装的结点指针
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestory(Queue* pq);
//插入
void QueuePush(Queue* pq, QDateType x);
//删除
void QueuePop(Queue* pq);
//取头部数据
QDateType QueueFront(Queue* pq);
//取尾部数据
QDateType QueueBack(Queue* pq);
//判空（容量）
bool QueueEmpty(Queue* pq);
//大小
int QueueSize(Queue* pq);

Queue.c：队列实现

#include "Queue.h"

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = pq->tail = NULL;
}
//销毁
void QueueDestory(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		//code-1
		/*pq->head = cur->next;
		free(cur);
		cur = pq->head;*/
		//code-2
		QNode* del = cur;
		cur = cur->next;
		free(del);
	}

	pq->head = pq->tail = NULL;
}
//插入
void QueuePush(Queue* pq, QDateType x)
{
	assert(pq);
	//开辟新节点
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	else
	{
		newNode->data = x;
		newNode->next = NULL;
	}
	//插入
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newNode;
	}
	else
	{
		pq->tail->next = newNode;
		pq->tail = newNode;
	}
}
//删除
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* del = pq->head;
		pq->head = pq->head->next;
		free(del);
	}
}
//取头部数据
QDateType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}
//取尾部数据
QDateType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}
//判空（容量）
bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->head == NULL && pq->tail == NULL;
}
//大小
int QueueSize(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	int n = 0;
	while (cur)
	{
		n++;
		cur = cur->next;
	}

	return n;
}

Tree.c ：二叉树相关实现

//#include "Tree.h"
#include "Queue.h"

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* src, int n, int* pi)
{
	if (src[*pi] == '#' || *pi >= n)
	{
		(*pi)++;
		return NULL;
	}

	BTNode* cur = (BTNode*)malloc(sizeof(BTNode));
	if (cur == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	cur->data = src[*pi];
	(*pi)++;

	cur->left = BinaryTreeCreate(src, n, pi);
	cur->right = BinaryTreeCreate(src, n, pi);

	return cur;
}
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	assert(root);

	if (*root)
	{
		BinaryTreeDestory(&(*root)->left);
		BinaryTreeDestory(&(*root)->right);

		free(*root);
		*root = NULL;
	}
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	return ((!root->left && !root->right) ? 1 : 0)
		 + BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	assert(k > 0);

	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
// 二叉树查找值为x的节点
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)
		return left;
	BTNode* right = BinaryTreeFind(root->right, x);
	if (right)
		return right;

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

	printf("%c", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("#");
		return;
	}

	BinaryTreePrevOrder(root->left);
	printf("%c", root->data);
	BinaryTreePrevOrder(root->right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("#");
		return;
	}

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

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		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");

	QueueDestory(&q);
}
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		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 != NULL)
		{
			QueueDestory(&q);
			return false;
		}
	}
	QueueDestory(&q);
	return true;
}

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

	int leftHeight = BinaryTreeHeight(root->left);
	int rightHeight = BinaryTreeHeight(root->right);

	return 1 + (leftHeight < rightHeight ? rightHeight : leftHeight);
}

test.c

#include "Tree.h"

void Test()
{
	BTDataType arr[] = "ABD##E#H##CF##G##";
	int len = strlen(arr);
	int i = 0;
	BTNode* root = BinaryTreeCreate(arr, len, &i);

	BinaryTreePrevOrder(root);
	printf("\n");

	printf("结点个数：%d\n", BinaryTreeSize(root));
	printf("叶结点个数：%d\n", BinaryTreeLeafSize(root));
	printf("二叉树高度：%d\n", BinaryTreeHeight(root));
	printf("二叉树第k层结点个数：%d\n", BinaryTreeLevelKSize(root, 4));
	printf("二叉树值为x的结点地址：%p\n", BinaryTreeFind(root,'A'));
	printf("is BinaryTreeComplete: %d\n", BinaryTreeComplete(root));
	BinaryTreeLevelOrder(root);

	BinaryTreeDestory(&root);
}
int main()
{
	Test();//建议测试时，使用接口测试
	return 0;
}

4.6 二叉树OJ练习

到这里，相信小伙伴们已经对二叉树有了一定的了解，那就趁热打铁，上手一些OJ题试试吧：

单值二叉树。Oj链接
检查两颗树是否相同。OJ链接
对称二叉树。OJ链接
二叉树的前序遍历。 OJ链接
二叉树中序遍历。OJ链接
二叉树的后序遍历。OJ链接
另一颗树的子树。OJ链接
二叉树的构建及遍历。OJ链接

【数据结构】详解二叉树（两万字总结）

文章目录

数据结构之二叉树

1. 树

1.1 树的概念

1.2 与树有关的概念

1.3 树的表示

1.4 树在实际情况中的应用

2. 二叉树

2.1 二叉树的概念

2.2 特殊的二叉树

2.3 二叉树的性质

2.4 二叉树的存储结构

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

3.1 二叉树的顺序结构

3.2 堆的概念及结构

3.3 堆的实现

3.3.1 堆的相关声明

3.3.2 堆的向下调整算法

3.2.3 堆的创建

3.2.3 建堆时间复杂度

3.2.4 堆的插入

3.2.5 堆的删除

3.2.6 堆的应用之堆排序

3.2.7 Top-K问题

3.2.8 堆的源代码

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

4.1 创建二叉树

4.2 二叉树的遍历

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

4.2.2 层序遍历

4.3 二叉树结点个数

4.3.1 二叉树总结点个数

4.3.2 二叉树叶子结点个数

4.3.3 二叉树第k层结点个数

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

4.4 二叉树高度

4.5 二叉树的销毁

4.6 判断完全二叉树

4.7 二叉树源码

4.6 二叉树OJ练习

网站公告

今日签到

热门文章

最新发布