当前位置：首页 > news >正文

C语言描述数据结构 —— 二叉树(3)普通二叉树

news 来源：原创 2024/5/1 1:19:19

1.完全二叉树与普通二叉树的对比

我们前面介绍过完全二叉树以及堆(一种完全二叉树)，并且实现了堆用顺序结构存储的数据结构。还介绍了两个基本算法：向上调整算法、向下调整算法。在此基础上使用堆解决了 Top-K 问题，以及堆排序。我们通过完全二叉树的规律可以发现，完全二叉树如果不看最后一层，那么它是一棵满二叉树；最后一层的节点必须是上一层连续节点并且依次是左孩子、右孩子。那么现在要介绍的是普通二叉树。普通二叉树只满足二叉树的基本定义，它不满足完全二叉树的定义。那么普通二叉树的结构可能是下面这几种：

可以发现普通二叉树的结构没有规律，如果用顺序结构存储的话那么物理空间不一定是连续的。

如果是这样，那么数据的存储就没有意义。我们可以试想一下，当我们真正进行数据存储的时候，我们会把数据不连续的存储起来吗？这样做的意义只有增加工作量、难度而已。不单单是存储数据没有意义，就连删除也没有意义。我们想要访问二叉树的节点时候也是一个难题。所以普通二叉树我们一般使用链式结构，即用链表串联起来，需要注意，这样做的目的不是赋予它适合增删查改的能力，而是使用链式结构可以实现我们从来没有接触过的功能。例如二叉搜索树：

我们使用百科上面的例子做一个分析：

当然我们现在是简单的举一些普通二叉树的应用，本篇介绍的目的是为了打好基础，做好铺垫，为以后的学习打下地基。

2.二叉树的性质

我们实现过堆用顺序结构存储的数据结构，里面也涉及到了不少的二叉树性质。那么现在将详细介绍二叉树的性质。

1.若规定根节点的层数为1，那么一颗非空二叉树的第k层最多有 2^(k-1) 个节点

2.若规定根节点的层数为1，那么深度(高度)为h的二叉树最多一共有 2^h-1 个节点

3.对任意一颗二叉树而言，如果度为2的节点个数为n2，度为0的节点个数为n0，那么有n0=n2+1

4.如果规定根节点的层数为1，那么总共有n个节点的满二叉树的深度就为h=log(n+1)

对应这条性质的解释就是数学公式，总节点数为 2^h-1 ,在这个表达式上计算 h ，就用到了对数。

5.在用顺序结构存储的完全二叉树中有下面几个规律：

1.如果 child != 0 ，那么 parent = (child-1)/2 ；如果 child = 0，那么这个节点为根节点

2.如果总节点个数为 n，假设 parent*2+1<n ，那么 parent*2+1 的值就是左孩子的下标

3.如果总节点个数为 n，假设 parent*2+2<n ，那么 parent*2+2 的值就是右孩子的下标

这三条性质在我们实现堆的顺序结构的时候使用过，当然也是基于数学上得来的公式。

2.1二叉树性质有关练习

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（）

A 不存在这样的二叉树

B 200

C 198

D 199

答案： A 。根据公式 n0=n2+1 可知，度为 0 的节点个数比度为 2 的节点个数多一个。

2. 下列数据结构中，不适合采用顺序存储结构的是（）

A 非完全二叉树

B 堆

C 队列

D 栈

答案：A。即使队列不推荐使用顺序结构存储，但即使使用，也比非完全二叉树效率高。

3. 在具有 2n 个结点的完全二叉树中，叶子结点个数为（）

A n

B n+1

C n-1

D n/2

答案： A 。在二叉树中，节点的分类只有三种，即度为2的节点，度为1的节点和度为0的节点。那么表达式就为 2n = n2+n1+n0 ，又因为 n2=n0+1 ，所以 2n = 2n0-1+n1；又因为 2n 的结果只能是整数，所以 n1 必须等于 1。故n0 = n。

4. 一棵完全二叉树的节点数位为 531 个，那么这棵树的高度为（）

A 11

B 10

C 8

D 12

答案： B 。完全二叉树的节点个数在 [2^(h-1),2^h-1] 这个区间内。那么将 10 带入这个表达式之中，那么区间就为 [512,1023] ，恰好 531 在这个区间之内，所以高度为 10。

5. 一个具有 767 个节点的完全二叉树，其叶子节点个数为（）

A 383

B 384

C 385

D 386

答案： B 。n2+n1+n0=767，因为n2=n0+1，所以得 2n0-1+n1=767，即2n0+n1=768，因为 2n0 的结果必为偶数，所以n1必为0( 完全二叉树特性，度为1的节点个数要不为0要不为1 )，所以n0=384。

3.二叉树的递归遍历

我们再回顾一下二叉树的性质，我们提到过二叉树是递归定义的。

在任意一颗二叉树中，只有两种可能：要不为空；要不就为根节点、左子树和右子树组成。

了解了递归定义之后，我们就着手前序遍历、中序遍历和后序遍历。

前序遍历，在每一颗树中，它的遍历顺序总为：根节点、左子树、右子树。
中序遍历，在每一颗树中，它的遍历顺序总为：左子树、根节点、右子树。
后序遍历，在每一颗树中，它的遍历顺序总为：左子树、右子树、根节点。

注意我的用词，在每一颗树中。每一颗树，相当于左子树是一棵树，左子树当中又分为根节点、左子树和右子树，左子树的左子树又是一颗树，它又分为根节点、左子树和右子树……

我们先画一下前序遍历的顺序图。

就像这样层层递归，就可以完成遍历。那么中序遍历、后序遍历和前序遍历一样，那么这里的顺序图就省略了，我们直接看结果：

清楚了遍历顺序之后，就可以开始着手代码。这里注意，因为现在的部分是为了后续学习打基础，所以在这里手动构造与例子相同的二叉树。

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

typedef int BinaryData;
typedef struct Node
{
	BinaryData val;
	struct Node* left;
	struct Node* right;
}Node;

Node* CreateNode()
{
	Node* n1 = (Node*)malloc(sizeof(Node));
	assert(n1);
	Node* n2 = (Node*)malloc(sizeof(Node));
	assert(n2);
	Node* n3 = (Node*)malloc(sizeof(Node));
	assert(n3);
	Node* n4 = (Node*)malloc(sizeof(Node));
	assert(n4);
	Node* n5 = (Node*)malloc(sizeof(Node));
	assert(n5);
	Node* n6 = (Node*)malloc(sizeof(Node));
	assert(n6);

	n1->val = 1;
	n2->val = 2;
	n3->val = 3;
	n4->val = 4;
	n5->val = 5;
	n6->val = 6;

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

	return n1;
}

//前序遍历
void PreTraval(Node* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->val);
	PreTraval(root->left);
	PreTraval(root->right);
}

//中序遍历
void MidTraval(Node* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	MidTraval(root->left);
	printf("%d ", root->val);
	MidTraval(root->right);
}

//后序遍历
void PosTraval(Node* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PosTraval(root->left);
	PosTraval(root->right);
	printf("%d ", root->val);
}

int main()
{
	Node* root = CreateNode();
	PreTraval(root);
	printf("\n");
	MidTraval(root);
	printf("\n");
	PosTraval(root);
	printf("\n");
	return 0;
}

4.递归遍历的衍生问题

了解了遍历之后，现在有很多衍生问题：怎么求节点个数？怎么求第k层的节点个数？如何求叶节点个数？如何查找值为x的节点？

4.1节点个数

我们逐个分析，如何求节点个数。求个数呢，通用方法是计数法，那么计数法在我们的递归上面也可以使用。

//求节点个数
int count = 0;//使用全局变量
int NodeSize(Node* root)
{
	if (root == NULL)
	{
		return 0;
	}
	//static int count = 0;//使用static修饰的静态变量
	count++;
	NodeSize(root->left);
	NodeSize(root->right);
	return count;
}

int main()
{
	Node* root = CreateNode();
	/*PreTraval(root);
	printf("\n");
	MidTraval(root);
	printf("\n");
	PosTraval(root);
	printf("\n");*/

	printf("NodeSize = %d\n", NodeSize(root));
	printf("NodeSize = %d\n", NodeSize(root));
	return 0;
}

可以看到我们使用计数法是可以帮助我们完成任务的，但是当我们第二次调用这个函数就出现了问题。原因是全局变量和static修饰的静态变量只能被初始化一次。所以我们的计数方法是不够好的，那我们就要着手递归的方法了。

//求节点个数
int NodeSize(Node* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return NodeSize(root->left) + NodeSize(root->right) + 1;
}
//int count = 0;//使用全局变量
//int NodeSize(Node* root)
//{
//	if (root == NULL)
//	{
//		return 0;
//	}
//	//static int count = 0;//使用static修饰的静态变量
//	count++;
//	NodeSize(root->left);
//	NodeSize(root->right);
//	return count;
//}

int main()
{
	Node* root = CreateNode();
	/*PreTraval(root);
	printf("\n");
	MidTraval(root);
	printf("\n");
	PosTraval(root);
	printf("\n");*/

	printf("NodeSize = %d\n", NodeSize(root));
	printf("NodeSize = %d\n", NodeSize(root));
	return 0;
}

可以看到，递归的方式完美的解决了计数的"BUG"。

4.2第k层的节点个数

通过公式我们就可以发现，k是一定要被减1的，那么在递归当中也不例外。既然是要求某一层的节点个数，我们只要加一个条件：即递归到了指定层数的时候，才有返回值。

//求第k层的节点个数
int KSize(Node* root,int k)
{
	assert(k > 0);//层数大于0才有意义
	if (root == NULL)
	{
		return 0;
	}
	//加一个特定条件，必须在这一层才具有返回值
	if (k == 1)
	{
		return 1;
	}
	//否则继续往下递归找到指定层数
	return KSize(root->left,k-1) + KSize(root->right,k-1);
}

int main()
{
	Node* root = CreateNode();
	/*PreTraval(root);
	printf("\n");
	MidTraval(root);
	printf("\n");
	PosTraval(root);
	printf("\n");*/

	//printf("NodeSize = %d\n", NodeSize(root));
	//printf("NodeSize = %d\n", NodeSize(root));

	printf("KSize = %d\n", KSize(root, 3));
	printf("KSize = %d\n", KSize(root, 1));

	return 0;
}

4.3求叶节点个数

叶节点的特征为度为0，即左右孩子都为空。不言而喻，需要添加一个条件来具有返回值。

//求叶节点的个数
int LeafSize(Node* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return LeafSize(root->left) + LeafSize(root->right);
}

int main()
{
	Node* root = CreateNode();
	/*PreTraval(root);
	printf("\n");
	MidTraval(root);
	printf("\n");
	PosTraval(root);
	printf("\n");*/

	//printf("NodeSize = %d\n", NodeSize(root));
	//printf("NodeSize = %d\n", NodeSize(root));

	//printf("KSize = %d\n", KSize(root, 3));
	//printf("KSize = %d\n", KSize(root, 1));

	printf("LeafSize = %d\n", LeafSize(root));
	return 0;
}

4.4查找值为x的节点

很明显，我们需要添加一个条件来限定返回值。那么其难点在于，如果左子树当中找到了节点，那么右子树就不要遍历了；如果左子树当中没有找到指定节点才需要遍历右子树。如果左右子树都找不到指定节点才返回空。这时就要用到分治的思想。

//查找值为x的节点
Node* NodeFind(Node* root, int x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->val == x)
	{
		return root;
	}
	Node* LeftRet = NodeFind(root->left, x);
	if (LeftRet != NULL)
	{
		return LeftRet;
	}
	Node* RightRet = NodeFind(root->right, x);
	if (RightRet != NULL)
	{
		return RightRet;
	}
	return NULL;
}

int main()
{
	Node* root = CreateNode();
	/*PreTraval(root);
	printf("\n");
	MidTraval(root);
	printf("\n");
	PosTraval(root);
	printf("\n");*/

	//printf("NodeSize = %d\n", NodeSize(root));
	//printf("NodeSize = %d\n", NodeSize(root));

	//printf("KSize = %d\n", KSize(root, 3));
	//printf("KSize = %d\n", KSize(root, 1));

	//printf("LeafSize = %d\n", LeafSize(root));

	printf("NodeFind = %p\n", NodeFind(root, 1));
	printf("NodeFind = %p\n", NodeFind(root, 3));
	printf("NodeFind = %p\n", NodeFind(root, 100));

	return 0;
}

4.5二叉树的销毁

二叉树的销毁，就是销毁所有的节点。后序遍历是非常契合的。

//二叉树销毁
void BinaryDestroy(Node* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryDestroy(root->left);
	BinaryDestroy(root->right);
	free(root);
}

5.二叉树的非递归遍历

5.1层序遍历

我们可以发现，上面提到的前序、中序、后序遍历好像都在往深的地方走，走到无路可走再退回到上一层继续往深的地方走。由此我们可以总结，前序、中序、后序遍历它们都是一种深度优先遍历(DFS)。现在我们要介绍二叉树的非递归遍历，即层序遍历。层序遍历是一种广度优先遍历(BFS)。

那么层序遍历实现的思路是怎么样的呢？我们需要借助一个工具——队列。我们看图：

那么我们上手代码时要注意，在C语言的库中没有队列这个数据结构，所以我们需要将实现队列的代码CV过来。这个问题在C++中会得到解决。那么代码我们就可以这么写：

//层序遍历
void LayerTraval(Node* root)
{
	HeadTail q;
	QueueInit(&q);

	//为空则为空树
	if (root == NULL)
	{
		return;
	}
	//非空则入队列
	QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		Node* tmp = QueueHead(&q);
		QueuePop(&q);
		printf("%d ", tmp->val);

		if (tmp->left != NULL)
		{
			QueuePush(&q, tmp->left);
		}
		if (tmp->right != NULL)
		{
			QueuePush(&q, tmp->right);
		}
	}
	QueueDestroy(&q);
}

int main()
{
	Node* root = CreateNode();
	/*PreTraval(root);
	printf("\n");
	MidTraval(root);
	printf("\n");
	PosTraval(root);
	printf("\n");*/

	//printf("NodeSize = %d\n", NodeSize(root));
	//printf("NodeSize = %d\n", NodeSize(root));

	//printf("KSize = %d\n", KSize(root, 3));
	//printf("KSize = %d\n", KSize(root, 1));

	//printf("LeafSize = %d\n", LeafSize(root));

	//printf("NodeFind = %p\n", NodeFind(root, 1));
	//printf("NodeFind = %p\n", NodeFind(root, 3));
	//printf("NodeFind = %p\n", NodeFind(root, 100));

	LayerTraval(root);
	return 0;
}

6.层序遍历的衍生问题

6.1判断二叉树是否为完全二叉树

碰到问题我们大胆地去想，首先便是通过节点个数能不能确定二叉树是否为完全二叉树。答案很明显不可能，因为完全二叉树的最后一层需要保证节点是连续的。但是这个方法是可以确定满二叉树的。

既然我们要通过层序遍历，那我们试着遍历任意几颗完全二叉树寻找规律：

我们遍历两颗普通二叉树：

可以发现一个非常明显的规律，即完全二叉树使用层序遍历的结果 NULL 总为连续的；而普通二叉树使用层序遍历的结果 NULL 是不连续的。

那么这个规律，便是我们代码的突破口。

//判断是否为完全二叉树
bool FuncTree(Node* root)
{
	HeadTail q;
	QueueInit(&q);
	if (root == NULL)
	{
		return;
	}
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		Node* tmp = QueueHead(&q);
		QueuePop(&q);
		//一旦拿到空，就跳出循环进行判断
		//此时队列后面要不有节点，要不为空
		//不用担心二叉树的所有节点是否完全存放在队列里面
		if (tmp == NULL)
		{
			break;
		}
		QueuePush(&q, tmp->left);
		QueuePush(&q, tmp->right);
		
	}
	while (!QueueEmpty(&q))
	{
		Node* tmp = QueueHead(&q);
		QueuePop(&q);
		if (tmp != NULL)
		{
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}


int main()
{
	Node* root = CreateNode();
	/*PreTraval(root);
	printf("\n");
	MidTraval(root);
	printf("\n");
	PosTraval(root);
	printf("\n");*/

	//printf("NodeSize = %d\n", NodeSize(root));
	//printf("NodeSize = %d\n", NodeSize(root));

	//printf("KSize = %d\n", KSize(root, 3));
	//printf("KSize = %d\n", KSize(root, 1));

	//printf("LeafSize = %d\n", LeafSize(root));

	//printf("NodeFind = %p\n", NodeFind(root, 1));
	//printf("NodeFind = %p\n", NodeFind(root, 3));
	//printf("NodeFind = %p\n", NodeFind(root, 100));

	//LayerTraval(root);
	printf("FuncTree = %d\n", FuncTree(root));
	return 0;
}

8.结尾

为了方便，我把完整代码放在这里(队列各接口除外)。

//队列的声明
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>

typedef int BinaryData;
typedef struct Node
{
	BinaryData val;
	struct Node* left;
	struct Node* right;
}Node;


//链表的结点
typedef Node* QueueData;
typedef struct QueueNode
{
	QueueData val;
	struct QueueNode* next;
}QueueNode;
//存储头、尾结点地址的指针
typedef struct HeadTail
{
	QueueNode* head;
	QueueNode* tail;
	int size;//记录队列有几个元素
}HeadTail;

void QueueInit(HeadTail* p);//初始化队列
void QueuePush(HeadTail* p,QueueData x);//进入队列
QueueData QueueHead(HeadTail* p);//获取队头元素
QueueData QueueTail(HeadTail* p);//获取队尾元素
void QueuePop(HeadTail* p);//删除操作，出队
bool QueueEmpty(HeadTail* p);//检查队列是否为空
int QueueSize(HeadTail* p);//获取队列元素个数
void QueuePopTail(HeadTail* p);
void QueueDestroy(HeadTail* p);//销毁队列

#include "Queue.h"


Node* CreateNode()
{
	Node* n1 = (Node*)malloc(sizeof(Node));
	assert(n1);
	Node* n2 = (Node*)malloc(sizeof(Node));
	assert(n2);
	Node* n3 = (Node*)malloc(sizeof(Node));
	assert(n3);
	Node* n4 = (Node*)malloc(sizeof(Node));
	assert(n4);
	Node* n5 = (Node*)malloc(sizeof(Node));
	assert(n5);
	Node* n6 = (Node*)malloc(sizeof(Node));
	assert(n6);

	n1->val = 1;
	n2->val = 2;
	n3->val = 3;
	n4->val = 4;
	n5->val = 5;
	n6->val = 6;

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

	return n1;
}

//前序遍历
void PreTraval(Node* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->val);
	PreTraval(root->left);
	PreTraval(root->right);
}

//中序遍历
void MidTraval(Node* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	MidTraval(root->left);
	printf("%d ", root->val);
	MidTraval(root->right);
}

//后序遍历
void PosTraval(Node* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PosTraval(root->left);
	PosTraval(root->right);
	printf("%d ", root->val);
}

//求节点个数
int NodeSize(Node* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return NodeSize(root->left) + NodeSize(root->right) + 1;
}
//int count = 0;//使用全局变量
//int NodeSize(Node* root)
//{
//	if (root == NULL)
//	{
//		return 0;
//	}
//	//static int count = 0;//使用static修饰的静态变量
//	count++;
//	NodeSize(root->left);
//	NodeSize(root->right);
//	return count;
//}

//求第k层的节点个数
int KSize(Node* root,int k)
{
	assert(k > 0);//层数大于0才有意义
	if (root == NULL)
	{
		return 0;
	}
	//加一个特定条件，必须在这一层才具有返回值
	if (k == 1)
	{
		return 1;
	}
	//否则继续往下递归找到指定层数
	return KSize(root->left,k-1) + KSize(root->right,k-1);
}

//求叶节点的个数
int LeafSize(Node* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return LeafSize(root->left) + LeafSize(root->right);
}

//查找值为x的节点
Node* NodeFind(Node* root, int x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->val == x)
	{
		return root;
	}
	Node* LeftRet = NodeFind(root->left, x);
	if (LeftRet != NULL)
	{
		return LeftRet;
	}
	Node* RightRet = NodeFind(root->right, x);
	if (RightRet != NULL)
	{
		return RightRet;
	}
	return NULL;
}

//层序遍历
void LayerTraval(Node* root)
{
	HeadTail q;
	QueueInit(&q);

	//为空则为空树
	if (root == NULL)
	{
		return;
	}
	//非空则入队列
	QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		Node* tmp = QueueHead(&q);
		QueuePop(&q);
		printf("%d ", tmp->val);

		if (tmp->left != NULL)
		{
			QueuePush(&q, tmp->left);
		}
		if (tmp->right != NULL)
		{
			QueuePush(&q, tmp->right);
		}
	}
	QueueDestroy(&q);
}

//二叉树销毁
void BinaryDestroy(Node* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryDestroy(root->left);
	BinaryDestroy(root->right);
	free(root);
}

//判断是否为完全二叉树
bool FuncTree(Node* root)
{
	HeadTail q;
	QueueInit(&q);
	if (root == NULL)
	{
		return;
	}
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		Node* tmp = QueueHead(&q);
		QueuePop(&q);
		//一旦拿到空，就跳出循环进行判断
		//此时队列后面要不有节点，要不为空
		//不用担心二叉树的所有节点是否完全存放在队列里面
		if (tmp == NULL)
		{
			break;
		}
		QueuePush(&q, tmp->left);
		QueuePush(&q, tmp->right);
		
	}
	while (!QueueEmpty(&q))
	{
		Node* tmp = QueueHead(&q);
		QueuePop(&q);
		if (tmp != NULL)
		{
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}


int main()
{
	Node* root = CreateNode();
	/*PreTraval(root);
	printf("\n");
	MidTraval(root);
	printf("\n");
	PosTraval(root);
	printf("\n");*/

	//printf("NodeSize = %d\n", NodeSize(root));
	//printf("NodeSize = %d\n", NodeSize(root));

	//printf("KSize = %d\n", KSize(root, 3));
	//printf("KSize = %d\n", KSize(root, 1));

	//printf("LeafSize = %d\n", LeafSize(root));

	//printf("NodeFind = %p\n", NodeFind(root, 1));
	//printf("NodeFind = %p\n", NodeFind(root, 3));
	//printf("NodeFind = %p\n", NodeFind(root, 100));

	//LayerTraval(root);
	printf("FuncTree = %d\n", FuncTree(root));
	return 0;
}