1. UU电玩城首页
  2. > 编程日记

数据结构——二叉树的实现

C++代码之家 • • 1年前 • 编程日记 • 阅读(3) • 违法举报

什么是二叉树？

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。
在这里插入图片描述

1.通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树

在这里插入图片描述
这段代码实现了根据前序遍历的数组构建二叉树的过程。其原理是通过递归实现的，对于当前节点，如果它是空节点或者数组已经遍历完，那么返回NULL，否则创建新节点并赋初值，然后递归构建左子树和右子树。具体实现如下：

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	//如果数组已经遍历完或者当前节点是空节点，返回空指针
	if (*pi >= n || a[*pi] == '#')
	{
		//当前节点为空，返回NULL
		(*pi)++;
		return NULL;
	}
	//创建新节点并赋初值
	BTNode* root = new BTNode;
	root->_data = a[*pi];
	root->_left = NULL;
	root->_right = NULL;
	//递归构建左子树和右子树
	(*pi)++;
	root->_left = BinaryTreeCreate(a, n, pi);
	(*pi)++;
	root->_right = BinaryTreeCreate(a, n, pi);
	return root;
}

其中，a表示前序遍历的数组，n表示数组的长度，pi表示数组的当前位置。如果数组已经遍历完或者当前节点是空节点，那么返回空指针。否则，创建一个新节点，并将当前位置向后移动一位，然后递归构建左子树和右子树。最终返回根节点，即构建好的二叉树。

2.二叉树销毁

这段代码实现了二叉树的销毁过程。其原理是通过递归实现的，对于当前节点，如果它为空节点，直接返回；否则递归销毁左子树和右子树，最后释放当前节点的内存。具体实现如下：

// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
		//如果当前节点为空，直接返回
		return;
	//递归销毁左子树和右子树
	BinaryTreeDestory(&((*root)->_left));
	BinaryTreeDestory(&((*root)->_right));
	//释放当前节点的内存
	free(*root);
	*root = NULL;
}

其中，root表示当前节点的指针，如果当前节点为空，直接返回；否则递归销毁左子树和右子树，最后释放当前节点的内存，并将当前节点的指针设置为NULL。递归过程会一直向下遍历二叉树，直到叶子节点，然后逐层返回，将每个节点释放，并将其左右子节点的内存全部释放。最终得到一个空的二叉树。

3.二叉树节点个数

在这里插入图片描述

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		//如果当前节点为空返回0
		return 0;
	//返回左子树节点个数加上右节点个数再加上1（当前节点）
	return BinaryTreeSize(root->_left) +
		BinaryTreeSize(root->_right) + 1;
}

4.二叉树叶子节点个数

这段代码实现了计算二叉树节点个数的过程。其原理是通过递归实现的，对于当前节点，如果它为空节点，直接返回0；否则返回左子树节点个数加上右子树节点个数再加上1（当前节点）。具体实现如下：

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		//如果当前节点为空，返回0
		return 0;
	if (root->_left == NULL && root->_right == NULL)
	{
		//如果当前节点是叶子节点，返回1
		return 1;
	}
	// 返回左子树叶子节点个数加上右子树叶子节点个数
	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

其中，root表示当前节点，如果当前节点为空，直接返回0；否则递归计算左子树节点个数和右子树节点个数，最终返回左子树节点个数加上右子树节点个数再加上1（当前节点），即整棵二叉树的节点个数。递归过程会一直向下遍历二叉树，直到叶子节点，然后逐层返回，并将每个节点的左右子树节点个数相加，最终得到整棵二叉树的节点个数。

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

这段代码实现了计算二叉树叶子节点个数的过程。其原理是通过递归实现的，对于当前节点，如果它为空节点，直接返回0；如果它是叶子节点，返回1；否则返回左子树叶子节点个数加上右子树叶子节点个数。具体实现如下：

//二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root==NULL)
		//如果当前节点为空，返回0
		return 0;
	if (k == 1)
		//如果当前节点是第k层节点，返回1
		return 1;
	// 返回左子树第 k-1 层节点个数加上右子树第 k-1 层节点个数
	int leftk = BinaryTreeLevelKSize(root->_left, k - 1);
	int rightk = BinaryTreeLevelKSize(root->_right, k - 1);
	return leftk + rightk;
}

其中，root表示当前节点，如果当前节点为空，直接返回0；如果当前节点是叶子节点，返回1；否则递归计算左子树叶子节点个数和右子树叶子节点个数，最终返回左子树叶子节点个数加上右子树叶子节点个数，即整棵二叉树的叶子节点个数。递归过程会一直向下遍历二叉树，直到叶子节点，然后逐层返回，并将每个节点的左右子树叶子节点个数相加，最终得到整棵二叉树的叶子节点个数。

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

这段代码实现了在二叉树中查找值为x的节点的过程。其原理是通过递归实现的，对于当前节点，如果它为空节点，返回NULL；如果它的值等于x，返回指向当前节点的指针；否则在左子树中查找x，如果找到了，返回指向左子树中x的节点的指针；否则在右子树中查找x，如果找到了，返回指向右子树中x的节点的指针；如果左右子树都没有找到，返回NULL。具体实现如下：

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		//如果当前节点为空,返回NULL
		return 0;
	if (root->_data == x)
		//如果当前节点的值等于x，返回指向当前节点的指针
		return root;
	//在左子树中查找x
	BTNode* lret = BinaryTreeFind(root->_left, x);
	// 如果在左子树中找到了 x，返回指向左子树中 x 的节点的指针
	if (lret)
	{
		return lret;
	}
	//在右子树中查找x
	BTNode* rret = BinaryTreeFind(root->_right, x);
	// 如果在右子树中找到了 x，返回指向右子树中 x 的节点的指针
	if (rret)
	{
		return rret;
	}
	//否则，返回NULL
	return NULL;
}

其中，root表示当前节点，x表示要查找的值。如果当前节点为空，返回NULL；如果当前节点的值等于x，返回指向当前节点的指针；否则在左子树中查找x，如果找到了，返回指向左子树中x的节点的指针；否则在右子树中查找x，如果找到了，返回指向右子树中x的节点的指针；如果左右子树都没有找到，返回NULL。递归过程会一直向下遍历二叉树，直到找到值为x的节点或者遍历到叶子节点，然后逐层返回，找到值为x的节点或者返回NULL。

7.二叉树前序遍历

前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
这段代码实现了二叉树的先序遍历过程。其原理是通过递归实现的，对于当前节点，如果它为空节点，直接返回；否则打印当前节点的值，并递归遍历左子树和右子树。具体实现如下：

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		//如果当前节点为空，直接返回
		return;
	}
	// 打印当前节点的值，并递归打印左子树和右子树
	printf("%c ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}

其中，root表示当前节点。如果当前节点为空，直接返回；否则先打印当前节点的值，然后递归遍历左子树和右子树。递归过程会一直向下遍历二叉树，直到遍历到叶子节点，然后逐层返回，逐个打印节点的值，最终得到整棵二叉树的先序遍历序列。

8.二叉树中序遍历

中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。若二叉树为空则结束返回，否则：
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树
这段代码实现了二叉树的中序遍历过程。其原理是通过递归实现的，对于当前节点，如果它为空节点，直接返回；否则先递归遍历左子树，打印当前节点的值，再递归遍历右子树。具体实现如下：

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		// 如果当前节点为空，直接返回
		return;
	}
	// 递归打印左子树，打印当前节点的值，再递归打印右子树	
	BinaryTreePrevOrder(root->_left);
	printf("%c ", root->_data);
	BinaryTreePrevOrder(root->_right);
}

其中，root表示当前节点。如果当前节点为空，直接返回；否则先递归遍历左子树，打印当前节点的值，再递归遍历右子树。递归过程会一直向下遍历二叉树，直到遍历到叶子节点，然后逐层返回，逐个打印节点的值，最终得到整棵二叉树的中序遍历序列。

9.二叉树后序遍历

后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。即：
若二叉树为空则结束返回，
否则：
（1）后序遍历左子树
（2）后序遍历右子树
（3）访问根结点
这段代码实现了二叉树的后序遍历过程。其原理是通过递归实现的，对于当前节点，如果它为空节点，直接返回；否则先递归遍历左子树和右子树，再打印当前节点的值。具体实现如下：

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		// 如果当前节点为空，直接返回
		return;
	}
	// 递归打印左子树和右子树，再打印当前节点的值
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
	printf("%c ", root->_data);
}

其中，root表示当前节点。如果当前节点为空，直接返回；否则先递归遍历左子树和右子树，再打印当前节点的值。递归过程会一直向下遍历二叉树，直到遍历到叶子节点，然后逐层返回，最终得到整棵二叉树的后序遍历序列。

10.层序遍历

这段代码实现了二叉树的层序遍历过程。其原理是通过队列实现的，先将根节点入队，然后循环从队列中取出节点并打印节点的值，如果节点有左子节点，就将左子节点入队，如果节点有右子节点，就将右子节点入队，直到队列为空为止。具体实现如下：

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	if (root == nullptr) {
		return;
	}

	std::queue<BTNode*> q;
	q.push(root);

	while (!q.empty()) {
		BTNode* node = q.front();
		q.pop();

		std::cout << node->_data << " ";

		if (node->_left != nullptr) {
			q.push(node->_left);
		}

		if (node->_right != nullptr) {
			q.push(node->_right);
		}
	}
}

其中，root表示根节点。首先将根节点入队，然后循环从队列中取出节点并打印节点的值，如果节点有左子节点，就将左子节点入队，如果节点有右子节点，就将右子节点入队，直到队列为空为止。这个过程会按照层序遍历的顺序依次遍历二叉树的每一层节点，从而得到整棵二叉树的层序遍历序列。

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

这段代码实现了判断二叉树是否为完全二叉树的过程。其原理是通过层序遍历和队列实现的，在层序遍历的过程中判断每个节点是否有左右子树，如果有就将它们入队，如果没有就将一个标志位设为1，表示之后遍历到的节点必须都是叶子节点，否则该树就不是完全二叉树。如果遍历到了一个节点，发现它的左子树或右子树为空，且之前已经出现过空子树，则该树就不是完全二叉树。如果遍历到队列中所有节点，均无右子树，则该树是完全二叉树。具体实现如下：

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root) {
	if (root == NULL) {
		// 空树是完全二叉树
		return 1;
	}

	BTNode* queue[1000];
	int front = 0, rear = 0;
	queue[rear++] = root;

	int flag = 0; // 是否出现过空子树的标志

	while (front < rear) {
		BTNode* node = queue[front++];

		if (node->_left != NULL) {
			// 如果之前出现过空子树，则该树不是完全二叉树
			if (flag) {
				return 0;
			}
			queue[rear++] = node->_left;
		}
		else {
			flag = 1;
		}

		if (node->_right != NULL) {
			// 如果之前出现过空子树，则该树不是完全二叉树
			if (flag) {
				return 0;
			}
			queue[rear++] = node->_right;
		}
		else {
			flag = 1;
		}
	}

	// 如果队列中所有节点均无右孩子，则该树是完全二叉树
	return 1;
}

其中，root表示根节点。首先判断根节点是否为空，如果是，则空树是完全二叉树，直接返回1。然后定义一个队列，将根节点入队，并定义一个标志位flag表示是否出现过空子树。接下来，在队列不为空的情况下，从队列中取出一个节点，判断该节点的左右子树是否为空，如果有子树，则将子树入队；如果子树为空，则将标志位flag设为1表示之后遍历到的节点必须都是叶子节点。如果遍历到了一个节点，发现它的左子树或右子树为空，且之前已经出现过空子树，则该树就不是完全二叉树，直接返回0。如果遍历到队列中所有节点，均无右子树，则该树是完全二叉树，返回1。这个过程可以判断二叉树是否为完全二叉树。文章来源地址https://uudwc.com/A/AZvDV

12.完整代码

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string.h>
#include<assert.h>
#include<stdio.h>
#include<limits.h>
#include<stdbool.h>
#include<queue>
using namespace std;
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);

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	//如果数组已经遍历完或者当前节点是空节点，返回空指针
	if (*pi >= n || a[*pi] == '#')
	{
		//当前节点为空，返回NULL
		(*pi)++;
		return NULL;
	}
	//创建新节点并赋初值
	BTNode* root = new BTNode;
	root->_data = a[*pi];
	root->_left = NULL;
	root->_right = NULL;
	//递归构建左子树和右子树
	(*pi)++;
	root->_left = BinaryTreeCreate(a, n, pi);
	(*pi)++;
	root->_right = BinaryTreeCreate(a, n, pi);
	return root;
}
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
		//如果当前节点为空，直接返回
		return;
	//递归销毁左子树和右子树
	BinaryTreeDestory(&((*root)->_left));
	BinaryTreeDestory(&((*root)->_right));
	//释放当前节点的内存
	free(*root);
	*root = NULL;
}

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		//如果当前节点为空返回0
		return 0;
	//返回左子树节点个数加上右节点个数再加上1（当前节点）
	return BinaryTreeSize(root->_left) +
		BinaryTreeSize(root->_right) + 1;
}

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		//如果当前节点为空，返回0
		return 0;
	if (root->_left == NULL && root->_right == NULL)
	{
		//如果当前节点是叶子节点，返回1
		return 1;
	}
	// 返回左子树叶子节点个数加上右子树叶子节点个数
	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

//二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root==NULL)
		//如果当前节点为空，返回0
		return 0;
	if (k == 1)
		//如果当前节点是第k层节点，返回1
		return 1;
	// 返回左子树第 k-1 层节点个数加上右子树第 k-1 层节点个数
	int leftk = BinaryTreeLevelKSize(root->_left, k - 1);
	int rightk = BinaryTreeLevelKSize(root->_right, k - 1);
	return leftk + rightk;
}

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		//如果当前节点为空,返回NULL
		return 0;
	if (root->_data == x)
		//如果当前节点的值等于x，返回指向当前节点的指针
		return root;
	//在左子树中查找x
	BTNode* lret = BinaryTreeFind(root->_left, x);
	// 如果在左子树中找到了 x，返回指向左子树中 x 的节点的指针
	if (lret)
	{
		return lret;
	}
	//在右子树中查找x
	BTNode* rret = BinaryTreeFind(root->_right, x);
	// 如果在右子树中找到了 x，返回指向右子树中 x 的节点的指针
	if (rret)
	{
		return rret;
	}
	//否则，返回NULL
	return NULL;
}

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		//如果当前节点为空，直接返回
		return;
	}
	// 打印当前节点的值，并递归打印左子树和右子树
	printf("%c ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		// 如果当前节点为空，直接返回
		return;
	}
	// 递归打印左子树，打印当前节点的值，再递归打印右子树	
	BinaryTreePrevOrder(root->_left);
	printf("%c ", root->_data);
	BinaryTreePrevOrder(root->_right);
}

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		// 如果当前节点为空，直接返回
		return;
	}
	// 递归打印左子树和右子树，再打印当前节点的值
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
	printf("%c ", root->_data);
}

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	if (root == nullptr) {
		return;
	}

	std::queue<BTNode*> q;
	q.push(root);

	while (!q.empty()) {
		BTNode* node = q.front();
		q.pop();

		std::cout << node->_data << " ";

		if (node->_left != nullptr) {
			q.push(node->_left);
		}

		if (node->_right != nullptr) {
			q.push(node->_right);
		}
	}

}

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root) {
	if (root == NULL) {
		// 空树是完全二叉树
		return 1;
	}

	BTNode* queue[1000];
	int front = 0, rear = 0;
	queue[rear++] = root;

	int flag = 0; // 是否出现过空子树的标志

	while (front < rear) {
		BTNode* node = queue[front++];

		if (node->_left != NULL) {
			// 如果之前出现过空子树，则该树不是完全二叉树
			if (flag) {
				return 0;
			}
			queue[rear++] = node->_left;
		}
		else {
			flag = 1;
		}

		if (node->_right != NULL) {
			// 如果之前出现过空子树，则该树不是完全二叉树
			if (flag) {
				return 0;
			}
			queue[rear++] = node->_right;
		}
		else {
			flag = 1;
		}
	}

	// 如果队列中所有节点均无右孩子，则该树是完全二叉树
	return 1;
}
int main()
{
	BTDataType a[] = { 'A', 'B', 'D', '#', '#', 'E', '#', 'H', '#', '#', 'C', 'F', '#', '#', 'G', '#', '#' };
	int n = sizeof(a) / sizeof(a[0]);
	int i = 0;
	BTNode* root = BinaryTreeCreate(a, n, &i);
	//cout << root << endl;
	/*cout <<"BinaryTreeSize:" << BinaryTreeSize(root) << endl;
	cout << "BinaryTreeLeafSize:" << BinaryTreeLeafSize(root) << endl;
	cout <<"BinaryTreeLevelKSize:" << BinaryTreeLevelKSize(root, 1) << endl;
	cout << "BinaryTreeFind:" << BinaryTreeFind(root, 'A') << endl;*/
	 //BinaryTreePrevOrder(root);
	//BinaryTreeInOrder(root);
	//BinaryTreePostOrder(root);
	//BinaryTreeLevelOrder(root);
	//cout<<BinaryTreeComplete(root) << endl;
	//cout << BinaryTreeComplete(root) << endl;
}

原文地址:https://blog.csdn.net/weixin_51799303/article/details/131651148

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请联系站长进行投诉反馈，一经查实，立即删除！

h
上一篇 2023年07月11日 12:03
k8s实战3-使用Helm在AKS上发布应用
下一篇 2023年07月11日 12:04