【初阶数据结构篇】实现链式结构二叉树（二叉链）下篇

半截诗

发布于 2024-10-09 18:56:11

1430

文章被收录于专栏：学西学西

实现链式结构二叉树（二叉链）下篇

前言

接上一篇

实现链式结构二叉树（二叉链）上篇

二叉树实现方法

二叉树查找值为x的结点

分为左右子树查找，依次递推即可
结束条件为空：说明在这一路径上没有找到
结束条件找到了返回结点指针即可

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}

	BTNode* leftFind = BinaryTreeFind(root->left, x);
	if (leftFind)
	{
		return leftFind;
	}
	BTNode* rightFind = BinaryTreeFind(root->right, x);
	if (rightFind)
	{
		return rightFind;
	}
	return NULL;
}

二叉树的销毁

注意这里我们要改变root指针的指向，将本来指向根节点的root指针改为空，所以传二级指针（一级指针也可以，只不过在调用完记得把root置为空）
先销毁左右子树，最后销毁根节点
当为空时，不用销毁直接返回

void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&((*root)->left));
	BinaryTreeDestory(&((*root)->right));

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

二叉树的层序遍历

除了先序遍历、中序遍历、后序遍历外，还可以对⼆叉树进⾏层序遍历。设⼆叉树的根结点所在层数为1，层序遍历就是从所在⼆叉树的根结点出发，⾸先访问第⼀层的树根结点，然后从左到右访问第2层的结点，接着是第三层的结点，以此类推，⾃上⽽下，⾃左⾄右逐层访问树的结点的过程就是层序遍历

由于递归会沿着一边路径一直递归下去，所以显然不能使用递归！

实现层序遍历需要额外借助数据结构：队列

创建并初始化队列，注意将队列结点存储的数据类型更改
这里我们插入的是指向结点的指针，而不是结点的值，否则找不到结点的左右孩子，所以队列结点存储的数据类型为struct BTNode*
首先将指向根节点的指针入队列，保存后并打印结点的值
根节点出队列，保证每一次取到的队列的头都是新的
如果根节点左右孩子不为空就将其入队列，为空则无必要，不需要打印NULL
重复上述操作直到队列为空

//层序遍历
//借助数据结构---队列
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头，打印
		BTNode* front = QueueFront(&q);
		printf("%d ", front->data);
		QueuePop(&q);
		//队头节点的左右孩子入队列
		if (front->left)
			QueuePush(&q, front->left);
		if (front->right)
			QueuePush(&q, front->right);
	}
	//队列为空
	QueueDestroy(&q);
}

判断是否为完全二叉树

同样使用层序遍历
左右结点不管是否为空，都入队列
第一个循环用来取二叉树第一个NULL结点前的所有数据
- 如果是完全二叉树，跳出此循环后剩下的都是NULL结点
- 如果是非完全二叉树，跳出此循环后还有非空结点
于是第二个循环用来判断此时队列里是否有非空的指针
- 如果直到队列为空跳出循环说明全是空指针，返回true
- 反之返回false

//判断二叉树是否为完全二叉树
//---队列
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 != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

二叉树性质选择题

在二叉树基础概念这篇博客中讲到了二叉树叶子结点个数==度为2结点个数+1
本题选B

由二叉树的定义可知，树中必定存在度为0的结点和度为2的结点，设度为0结点有a个，根据度为0的结点(即叶子结点)总比度为2的结点多一个，得度为2的结点有a一1个。
再根据完全二叉树的定义，度为1的结点有0个或1个
假设度1结点为0个，a+0+a一1=2n，得2a=2n一1，由于结点个数必须为整数，假设不成立；
当度为1的结点为1个时，a+1+a一1=2n，得a=n，即叶子结点个数为n。
本题选A

由29-1<531<210-1
说明第九层填满，第十层没有填满
本题选B

与第二题同理
由二叉树的定义可知，树中必定存在度为0的结点和度为2的结点，设度为0结点有a个，根据度为0的结点(即叶子结点)总比度为2的结点多一个，得度为2的结点有a一1个。
再根据完全二叉树的定义，度为1的结点有0个或1个
假设度1结点为0个，a+0+a一1=767，得2a=768，即叶子结点个数为384
当度为1的结点为1个时，a+1+a一1=767，不为整数，舍去。
本题选B