由浅入深带你了解数据结构中的二叉树

1.树的概念及结构

1.1树的概念

  树是一种非线性的数据结构，它是由n(n>=0)个有限节点组成一个具有层次关系的集合。它的形状像一颗倒挂的树，因此我们把它叫做树。其特点如下所示：

  <1.>有一个特殊的节点，称为根节点，根节点没有前驱节点

  <2.>除根节点外，其余节点被分为M(M>0)个互不相交的集合，其中每个集合又是一颗结构与树类似的子树。每颗子树的根节点有且只有一个前驱，可以有0个或多个后继，因此，树是递归定义的。

注意：树形结构中，子树之间不能有交集，否则就不是树形结构

1.2.树的相关概念

节点的度：一个节点含有的子树的个数称为该节点的度，如上图：A的度为3。

叶节点或终端节点：度为0的节点被称为叶节点，如上图：E、F、G、H、I、J为叶节点。

非终端节点或分支节点：度不为0的节点。

双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点，如上图：B就是E、F的父节点。

孩子节点或子节点：一个节点含有子树的根节点称为该节点的子节点，如上图：B、C、D就是A的子节点

兄弟节点：具有相同父节点的节点互称为兄弟节点，如上图H、I、J就是兄弟节点。

树的度：一颗树中，最大节点的度称为树的度，如上图：度为3。

节点的层次：从根开始，根为第一层，根的子节点为第二层...以此类推。

树的深度或高度：树中节点的最大层次。如上图：树的高度为3。

堂兄弟节点：在同一层的节点叫做堂兄弟节点。

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

子孙：以某节点为根的子树中的任意节点都称为该节点的子孙。

1.3.树的表示

  从树的定义中我们不难发现，树的表示既要保存值域，也要保存节点和节点之间的关系。根据这一特点，我们可以有多种表示方法，如：双亲表示法、孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们在这里主要介绍最常用的孩子兄弟表示法。

typedef int BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

2.二叉树的概念及结构

2.1.概念

   一颗二叉树是节点的一个有限集合，该集合要么为空，或者由一个根节点加上两颗别称为左右子树的二叉树组成。其逻辑结构如下图所示：

  从上图我们可以看到，二叉树不存在度大于2的节点，二叉树的 子树有左右之分，次序不能颠倒，因此二叉树是有序树。

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

          1.空树  2.只有根节点  3.只有左子树  4.只有右子树  5.左右子树都存在

满二叉树：如果每一层的节点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为k，且节点个数为2^k-1,则它就是满二叉树

完全二叉树：对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

2.2.二叉树的性质

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)

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.3.二叉树的存储结构

二叉树一般使用两种数据结构来存储，一种是顺序结构，另一种是链式结构。

1.顺序结构

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

2.链式结构

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

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

3.1 堆的概念及结构

把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中的数据结构称为堆。将根节点最大的堆叫大堆（大根堆），把根节点最小的堆叫小堆（小根堆）

堆的性质如下：

1.堆中某个节点的值总是不大于或不小于其父节点的值

2.堆总是一棵完全二叉树

3.2 堆的实现

首先我们定义一个Heap.h的文件，并在里面定义堆，堆的初始化、销毁、堆的创建、堆的插入、删除、获取堆顶元素等函数接口。

堆创建如下：

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* arr;
	int size;
	int CapaCity;
}HP;

//堆的初始化
void HPInit(HP* ps);
//堆的销毁
void HPDestroy(HP* ps);
//创建堆
void HPInitArray(HP* ps, HPDataType* a, int n);

bool HPEmpty(HP* ps);
//将元素插入堆中
void HPPush(HP* ps, int x);
//堆的删除
void HPPop(HP* ps);
//获取堆顶元素
HPDataType HPTop(HP* ps);
//向上调整
void AdJustUp(HPDataType* arr, int child);
//向下调整
void AdJustDown(HPDataType* arr, int n, int parent);

 定义好接口函数之后，我们再创建一个Heap.c文件，我们将在此文件中实现各个函数。

1.堆的创建和销毁：

//堆的创建
void HPInit(HP* ps)
{
	assert(ps);

	ps->arr = NULL;
	ps->CapaCity = ps->size = 0;
}
//堆的销毁
void HPDestroy(HP* ps)
{
	assert(ps);

	free(ps->arr);
	ps->arr = NULL;
	ps->CapaCity = ps->size = 0;
}

 2.堆的向上调整

  接下来我们将实现堆的插入，在顺序表中，我们可以头插、尾插、在任意位置插入等，那么在堆这个数据结构中我们该怎么插入数据呢？事实上，我们在这里采用的是尾部插入，那么此时就存在一个问题，堆是一个有序的数据结构，分为大堆和小堆，那么我们将数据插入堆中时往往会破坏堆的顺序，为了使堆保持原状，我们就要对堆进行调整。

  因此，在堆的插入中我们要单独定义一个向上调整的函数，在完成插入这个步骤后我们就对堆进行调整，其调整的思路是将子节点和父节点相互比较，以建小堆为例，如果插入的元素比父节点小，那么就将父节点与子节点的元素相互交换，以此类推，直到将其调整为小堆，代码如下：

void Sweap(HPDataType* x, HPDataType* y)
{
	HPDataType* tmp = *x;
	*x = *y;
	*y = tmp;
}
void AdJustUp(HPDataType* arr, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[parent] > arr[child])
		{
			Sweap(&arr[parent], &arr[child]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

 有了这个向上调整函数之后我们就可以轻松将堆的插入写出来，代码如下：

void HPPush(HP* ps, int x)
{
	assert(ps);

	if (ps->CapaCity == ps->size)
	{
		int newCapaCity = ps->CapaCity == 0 ? 4 : ps->CapaCity * 2;
		HPDataType* tmp = (HPDataType*)realloc(ps->arr, sizeof(HPDataType) * newCapaCity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		ps->CapaCity = newCapaCity;
		ps->arr = tmp;
	}
	ps->arr[ps->size++];

	AdJustUp(ps->arr, ps->size - 1);
}

 3.堆的向下调整

  接下来我们将书写堆的头部删除，此时我们同样面对相同的问题：将元素删除之后我们该如何保证堆中数据的有序性？我们发现，当我们删除头部元素后，堆的顺序就全乱了，而采用尾删就可以避免这个问题，因此我们可以选择将头部元素和尾部元素互换，之后再向上调整，从而保证堆的有序性。

  向下调整顾名思义就是将堆中的元素向下交换，从而使元素到达相应的位置。那么我们该从堆的哪个位置开始调整呢？答案是从倒数第二个叶子节点的父节点开始向下调整。那么我们为什么要选择从倒数第二个叶子节点的父节点开始向下调整呢？答案是时间复杂度。因为我们将头部元素和尾部元素相互交换后，中间节点是有序的，如果从头部元素开始向下调整交换的次数远远大于从倒数第二个叶子节点的父节点开始调整，这样会造成效率的降低。有了思路之后，代码如下所示：

void Sweap(HPDataType* x, HPDataType* y)
{
	HPDataType* tmp = *x;
	*x = *y;
	*y = tmp;
}
void AdJustDown(HPDataType* arr, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child] < arr[child + 1])
		{
			child++;
		}
		if (arr[child] < arr[parent])
		{
			Sweap(&arr[parent], &arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

 有了向下调整算法之后我们就可以轻松将堆的头部删除代码写下来：

void HPPop(HP* ps)
{
	assert(ps);
	assert(ps->size > 0);

	Sweap(&ps->arr[ps->size - 1], &ps->arr[0]);
	ps->size--;

	AdJustDown(ps->arr, ps->size, 0);

}

 4.堆的创建

  在有了向下调整和向上调整算法之后我们就可以用这两种方式建立一个堆，代码如下：

void HPInitArray(HP* ps, HPDataType* a, int n)
{
	assert(ps);

	ps->arr = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (ps->arr = NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	memcpy(ps->arr, a, sizeof(HPDataType) * n);
	ps->CapaCity = ps->size = n;

	//向上调整建堆
	/*for (int i = 1; i < ps->size; i++)
	{
		AdJustUp(ps->arr, i);
	}*/
	//向下调整建堆
	for (int i = (ps->size - 1 - 1); i >= 0; i--)
	{
		AdJustDown(ps->arr, ps->size, i);
	}
}

5.判断堆是否为空

bool HPEmpty(HP* ps)
{
	assert(ps);

	return ps->size == 0;
}

 6.获取堆顶元素

HPDataType HPTop(HP* ps)
{
	assert(ps);
	return ps->arr[0];
}

 3.3 堆排序

我们在上述代码中可以看见，建堆分为向上调整和向下调整，但是哪个算法更好呢？我们将分析他们的时间复杂度。

向上调整建堆：

从上述分析我们可以看到，向上调整建堆的循环次数是(N+1)*(log(N+1)-2)+2，用大O渐近表示，向上调整算法的时间复杂度为O(NlogN)

向下调整建堆：

 从上述分析我们可以看到，向下调整建堆的循环次数是N-log(N+1)，用大O渐近表示，向上调整算法的时间复杂度为O(N)

由此我们可以看到，向下调整算法的时间复杂度远远小于向上调整算法，根据这个原理，我们可以写出堆排序这个算法，代码如下所示：

void HeapSort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

	int end = n - 1;
	while (end > 0)
	{
		Sweap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

3.4 堆的应用 

TOP-K问题：求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量比较大。比如：全球前十富豪、游戏前100活跃玩家、世界五百强等等

基本思路如下：

以求全球前十富豪为例

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

2.用剩余的N-10个元素依次与堆顶元素比较，如果比他大，就替代堆顶进堆，然后依次向下调整

3.将剩余的N-10个元素比对完后，堆中剩余的K个元素就是前十大富豪

代码如下所示：

void CreatNDate()
{
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen fail");
		return;
	}
	int n = 10000;
	for (int i = 0; i < n; i++)
	{
		int x = (rand() + i) % 10000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}

void topk()
{
	int k = 0;
	printf("请输入您要查找的前k个数据：");
	scanf("%d", &k);

	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}

	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc fail");
		return;
	}

	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
	}
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(minheap, k, i);
	}
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		if (x > minheap[0])
		{
			minheap[0] = x;
			AdjustDown(minheap, k, 0);
		}
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}
	printf("\n");
}

 分析上述代码，我们首先打开了一个文件，向其中写入了10000个随机数据，然后在Topk函数中查找前十大的数据并将其打印出来。

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

4.1 链式二叉树的创建

  和堆的创建一样，我们首先创建一个BinaryTree.h的文件，在这个文件里面我们定义链式二叉树的结构、创建、销毁、遍历等等接口，然后在BinaryTree.c文件中具体实现，如下所示：

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 n,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);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);

 二叉树的创建和销毁，代码如下：

BTNode* BinaryTreeCreate(BTDataType* a, int n,int* pi)
{
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	root->_left = root->_right = NULL;
	if ((*pi) < n)
	{
		root->_data = a[(*pi)++];
		root->_left = BinaryTreeCreate(a,n, pi);
		root->_right = BinaryTreeCreate(a,n, pi);
	}
	return root;
}
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	assert(root);
	assert((*root)->_data);
	BinaryTreeDestory((*root)->_left);
	BinaryTreeDestory((*root)->_right);
	free(root);
}

 4.2 二叉树的遍历

1.前序、中序、后序

前序遍历：也叫先序遍历、深度优先遍历，其访问顺序是根、左子树右子树。

 以上述图片为例，前序遍历的结果是：A B D n n n C E n n F n n(其中N表示空节点，写上方便理解)。从上述例子中我们发现，前序遍历首先走完二叉树的左边，因此前序遍历又称深度优先遍历，第一个元素总是根节点。

中序遍历：访问顺序是左子树、根、右子树。

以上述图片为例，中序遍历的结果是：n D n B n A n E n C n F n。

后序遍历：访问顺序是左子树、右子树、根。

以上述图片为例，后序遍历的结果是：n n D n B n n E n n F C A。从上述例子我们发现，后序遍历根节点一般在末尾。

了解了前中后序遍历之后我们要考虑去实现它，那么我们该如何去实现呢？仔细分析后我们发现，用递归的方式去实现二叉树的遍历会让问题迎刃而解，于是代码如下：

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

	printf("%d ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	BinaryTreePrevOrder(root->_left);
	printf("%d ", root->_data);
	BinaryTreePrevOrder(root->_right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
	printf("%d ", root->_data);
}

2.层序遍历

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

我们对层序遍历进行分析：大致思路就是用队列实现二叉树的层序遍历，即就是：让父节点入队列，在队列中销毁父节点的数据时将左右子孩子入队列，然后依次循环遍历这样就达到了层序遍历的效果，根据这个思路，我们有了以下代码：

void BinaryTreeLevelOrder(BTNode* root)
{
	Queue* q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->_data);
		if (front->_left)
		{
			QueuePush(&q, front->_left);
		}
		if (front->_right)
		{
			QueuePush(&q, front->_right);
		}
	}
	QueueDestroy(&q);
}

 分析上述代码，首先我们创建了一个队列，并将队列初始化，然后将根节点入队列，如果节点不为空，那么就进入while循环，获取队列首元素，再将左右子孩子入队列，这样我们就完成了层序遍历。

同时为了方便理解，我在这里附上队列的代码：

队列：

首先是队列的定义，我们将队列定义在Queue.h的头文件中：

typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNote
{
	QDataType a;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;
//初始化
void QueueInit(Queue* ps);
//销毁
void QueueDestroy(Queue* ps);
//插入
void QueuePush(Queue* ps, QDataType x);
//删除
void QueuePop(Queue* ps);
//获取头部尾部元素
QDataType* QueueFront(Queue* ps);
QDataType* QueueBack(Queue* ps);

bool QueueEmpty(Queue* ps);

 我们在Queue.c文件中实现相应的接口，代码如下：

void QueueInit(Queue* ps)
{
	assert(ps);

	ps->phead = ps->ptail = NULL;
	ps->size = 0;
}
void QueueDestroy(Queue* ps)
{
	assert(ps);

	QNode* pcur = ps->phead;
	while (pcur)
	{
		QNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	
	ps->phead = ps->ptail = NULL;
	ps->size = 0;
}

void QueuePush(Queue* ps, QDataType x)
{
	assert(ps);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (ps->phead->next == NULL)
	{
		ps->phead = ps->ptail = newnode;
	}
	else
	{
		ps->ptail->next = newnode;
		ps->ptail = newnode;
	}
	ps->size++;
}
void QueuePop(Queue* ps)
{
	assert(ps);
	assert(ps->phead!=NULL);

	if (ps->phead->next == NULL)
	{
		free(ps->phead);
		ps->phead = ps->ptail = NULL;
	}
	else
	{
		QNode* next = ps->phead->next;
		free(ps->phead);
		ps->phead = next;
	}
}

QDataType* QueueFront(Queue* ps)
{
	assert(ps);
	assert(ps->phead != NULL);

	return ps->phead->a;
}
QDataType* QueueBack(Queue* ps)
{
	assert(ps);
	assert(ps->ptail != NULL);

	return ps->ptail->a;
}

bool QueueEmpty(Queue* ps)
{
	assert(ps);

	return ps->size == 0;
}

3.节点的个数及高度

<1.>二叉树节点个数

代码如下：

int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 : BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}

分析上述代码，我们采用递归的思想开始遍历整个二叉树，直到遇到空节点为止。

<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);
}

<3.> 二叉树第k层节点个数

代码如下：

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	assert(k > 0);
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}

 <4.>二叉树查找值为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;
}

 以上就是本篇博客的全部内容，受限于博主知识水平，可能文章中有些许不足，欢迎大家的指正。如果本文对您有帮助的话记得点赞收藏加关注，您的点赞就是对我最大的鼓励。文章来源地址https://www.toymoban.com/news/detail-858217.html

到了这里，关于由浅入深带你了解数据结构中的二叉树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！