【C语言】二叉树链式结构的实现，详解

原创

池央

发布于 2024-11-29 07:30:58

2660

文章被收录于专栏：好事连连好事连连

好事发生

Java面试宝典：MongoDB实战技巧作者：忆遂愿

https://cloud.tencent.com/developer/article/2466159?shareByChannel=link

文章对 MongoDB 知识的全面阐述，质量很高。从基本概念、Java 驱动使用、数据操作、安全性能问题与解决、数据一致性事务处理，到数据模型设计、技术集成和存储图片优势等方面讲解详细、条理清晰，体现出作者深入的理解。

0.前言

二叉树的基本操作的实现基本离不开一个思想——分治算法。

分治算法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这样，通过逐步缩小问题的规模，可以显著降低解决问题的复杂度。

1.一颗二叉树的创建

在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。先此处手动快速创建一棵简单的二树，快速进入二叉树操作学习，后面会详细说明二叉树真正的创建方式

一颗二叉树分为根、左子树、右子树，该二叉树根1的左边链接根2，根2的左边链接根3，根1的右边链接根4，根4的左边链接根5，根4的右边链接根6。

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->left = newnode->right = NULL;
	newnode->data = x;
	return newnode;
}
BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	return node1;
}

2.二叉树的三种遍历方式

掌握二叉树的三种遍历方式非常重要，详细思路可看文章：二叉树的三种遍历，这里只展示代码。

2.1前序遍历

void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{

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

2.2中序遍历

void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeInOrder(root->left);
	printf("%d ", root->data);
	BinaryTreeInOrder(root->right);
}

2.3后序遍历

void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%d ", root->data);
}

3.二叉树的销毁

基本思路：和后序遍历类似，先销毁根节点的左节点，再销毁根节点的右节点，再销毁根节点。

如果按前序遍历的方式销毁，先释放掉根节点，那就找不到他的左节点和右节点。当然也可以先把要是否掉的根节点存起来，但是相较于后序遍历销毁麻烦。

3.1传一级指针

此处有个缺陷，在函数里面将根节点释放掉后置为空，并不能将实参变为空。也就是形参的改变影响不了实参。我们还需在函数外面将实参置为空。

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

3.2传二级指针

此处形参的改变将会影响实参，不需要额外再将实参置空

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

4.二叉树节点个数

求二叉树节点个数，通常可以通过递归的方式来实现。递归的基本思想是：对于给定的二叉树，其节点总数等于左子树的节点数加上右子树的节点数，再加上根节点本身（1）。根节点为空是返回0.

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

5.二叉树叶子节点个数

叶子节点是没有左节点并且没有右节点的节点。

思路：如果当前节点为空返回0，当前节点存在且无左节点和右节点则是叶子节点返回1。如果当前节点不是叶子节点（即它有左子节点或右子节点），则递归地计算其左子树的叶子节点个数和右子树的叶子节点个数。将左子树的叶子节点个数和右子树的叶子节点个数相加，得到的结果即为以当前节点为根的子树的叶子节点总数。

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

6.二叉树第k层节点个数

思路：知道k-1层节点的左右节点一共有多少个就是二叉树第k层节点个数。当前节点为空返回0，当k等于1时说明到达第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);
}

7. 二叉树查找值为x的节点

7.1只是判断该值是否在二叉中

当前节点为空返回false，当前节点的值等于x返回true，没有找到则递归到左子树里面找，没找到再去右子树找

bool TreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return false;
	if (root->data == x)
		return true;
	return TreeFind(root->left, x) || TreeFind(root->right, x);
}

7.2返回第一个是该值的节点

当前节点为空返回，当前节点的值等于x返回该节点，没有找到则递归到左子树里面找，没找到再去右子树找（这里需要注意的是要先把节点存起来，如果没有存起来则返回的时候不会保留）

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return;
	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;
}

8.层序遍历

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

思路：需要借助队列来实现（C语言需要自己实现队列）

首先，检查根节点是否为空，如果不为空，则将其加入队列。然后，进入一个循环，只要队列不为空，就执行以下操作：

从队列中取出一个节点（队首元素），并访问它（打印它的值），再将队列中队头的元素（也就是该节点Pop掉）

如果该节点有左子节点，则将左子节点加入队列。

如果该节点有右子节点，则将右子节点加入队列。

这个过程会按照从上到下、从左到右的顺序遍历二叉树的所有节点。

void BinaryTreeLevelOrder(BTNode* root)
{
	Queue pq;
	QueueInit(&pq);
	if (root)
	{
		QueuePush(&pq, root);
	}
	while (!QueueEmpty(&pq))
	{
		BTNode* front = QueueFront(&pq);
		printf("%d ", front->data);
		QueuePop(&pq);
		if (front->left)
		{
			QueuePush(&pq, front->left);
		}
		if (front->right)
		{
			QueuePush(&pq, front->right);
		}
	}
	printf("\n");
	QueueDestroy(&pq);
}

9.判断二叉树是否是完全二叉树

完全二叉树：非空空。

非完全二叉树：非空空非空空

算法的思路通过层次遍历（广度优先搜索）来判断二叉树是否是完全二叉树。

首先，我们初始化一个队列，并将根节点（如果存在）加入队列中。然后，我们进入一个循环，不断地从队列中取出节点，并尝试将其左右子节点加入队列。如果在某个时刻，我们遇到了一个空节点（即该节点不存在）跳出第一个循环另外判断，不再向队列中添加任何子节点。这是因为，在完全二叉树的定义中，一旦开始遇到空节点，其后的所有节点都应该是空的。

在遍历完所有可能存在的节点后（即所有非空节点的子节点都已经被考虑过），我们再次检查队列。如果此时队列为空，说明我们之前的假设成立，即该二叉树是完全二叉树。如果队列不为空，且队列中的节点不为空，那么说明在之前遇到空节点之后，还有非空节点存在，这与完全二叉树的定义相违背，因此该二叉树不是完全二叉树。

简而言之，这个算法通过层次遍历来检查二叉树是否满足完全二叉树的性质：除了最后一层外，每一层都被完全填满，并且所有节点都尽可能地向左对齐。

bool BinaryTreeComplete(BTNode* root)
{
	Queue pq;
	QueueInit(&pq);
	if (root)
	{
		QueuePush(&pq, root);
	}
	while (!QueueEmpty(&pq))
	{
		BTNode* front = QueueFront(&pq);
		QueuePop(&pq);
		//遇到空以后跳出后续判断
		if (front == NULL)
		{
			break;
		}
		QueuePush(&pq, front->left);
		QueuePush(&pq, front->right);
	}
	//是空出队列，遇见非空则说明不是完全二叉树
	while (!QueueEmpty(&pq))
	{
		BTNode* front = QueueFront(&pq);
		QueuePop(&pq);
		if (front)
		{
			QueueDestroy(&pq);
			return false;
		}
	}
	QueueDestroy(&pq);
	return true;
}

10.二叉树的创建

按前序遍历的方式创建一颗二叉树，三个参数数组，数组长度，数组下标（初始值设为0）

当*pi>=数组越界或者数组元素等于#时数组下标+1且返回空，

把数组元素赋给节点数据，

递归，让数组的数据按照前序遍历的方式依次赋给节点。

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	if (*pi >= n || a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	root->data = a[*pi];
	(*pi)++;

	root->left = BinaryTreeCreate(a, n, pi);
	root->right = BinaryTreeCreate(a, n, pi);
	return root;
}

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

腾讯技术创作特训营S10

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

腾讯技术创作特训营S10

登录后参与评论

0 条评论

热度