首页 > 其他分享 >二叉树的基本功能（代码实现）

二叉树的基本功能（代码实现）

时间：2024-05-26 17:31:20浏览次数：22  
标签：遍历 代码 BTNode 基本功能 二叉树 NULL root 节点

1.二叉树的概念

在对树的介绍一文中，有明确的介绍。

如有兴趣可移步至：

数据结构：树的介绍-CSDN博客

2.二叉树的代码实现

2.1二叉树的结构体

typedef int BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

  这里我使用的是 二叉链，只用左孩子和右孩子。

2.2申请新的节点

//申请节点
BTNode* BuyNode(BTDataType x);

参数：需调添加的该节点数据的类型

实现代码 

//申请节点
BTNode* BuyNode(BTDataType x)
{
	BTNode* ret = (BTNode*)malloc(sizeof(BTNode));
	if (ret == NULL)
	{
		perror("BuyNode::malloc");
		exit(1);
	}
	
	ret->data = x;
	ret->left = ret->right = NULL;
	return ret;
}

2.3通过前序遍历构建二叉树

 // 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);

参数：根节点的指针，数组的大小，用于遍历的变量i的地址

实现代码：

//申请节点
BTNode* BuyNodenew(BTDataType x)
{
	if (x == '#')
		return NULL;

	BTNode* ret = (BTNode*)malloc(sizeof(BTNode));
	if (ret == NULL)
	{
		perror("BuyNode::malloc");
		exit(1);
	}

	ret->data = x;
	ret->left = ret->right = NULL;
	return ret;
}

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	BTNode* tmp = BuyNodenew(a[(*pi)++]);
	if (tmp == NULL)
		return NULL;

	tmp->left = BinaryTreeCreate(a, n - 1, pi);

	tmp->right = BinaryTreeCreate(a, n - 1, pi);

	return tmp;
}

2.4二叉树的四种基本的遍历

2.4.1前序遍历

遍历的顺序为：根节点，左子树，右子树 

这个二叉树的按前序遍历就是：1,2,3,4,5,6

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);

参数：根节点的指针

前序，中序和后序遍历都是用递归实现的。 

实现代码：

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		/*显示空节点，可加可不可*/
		//printf("N ");
		return;
	}
	printf("%d ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
	return;
}

2.4.1中序遍历

中序遍历：左子树，根节点，右子树 

这个二叉树的按中序遍历就是：3,2,1,5,4,6

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root); 

参数：根节点的指针

代码实现：

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		/*显示空节点，可加可不可*/
		//printf("N ");
		return;
	}

	BinaryTreeInOrder(root->left);
	printf("%c ", root->data);
	BinaryTreeInOrder(root->right);
	return;
}

2.4.3后序遍历

后序遍历：左子树，右子树，根节点 

这个二叉树的按后序遍历就是：3,2,5,6,4,1

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root); 

参数：根节点的指针

代码实现：

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

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

2.4.4层序遍历

层序遍历：一层一层的遍历 

这个二叉树的按层序遍历就是：1,2,4,3,5,6

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root); 

参数：根节点的指针

层序遍历需要使用队列，层序遍历是一种广度优先遍历。

根节点出队列时，将左右不为空的孩子节点依次添加到队列中。那上面的二叉树举列子：1出队列时会将2和4添加到队列中。

实现代码：

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	int num = BinaryTreeSize(root);
	//使用队列实现
	BTNode** arr = (BTNode**)malloc(num*sizeof(BTNode*));
	if (arr == NULL)
	{
		perror("BinaryTreeLevelOrder::malloc");
		exit(1);
	}
	//队列的前后指针
	int front = 0;
	int rear = 0;
	//将根节点加入队列
	arr[rear++] = root;
	while (front < rear)
	{
		//输出
		printf("%d ", arr[front]->data);
		//输出父节点时，同时加入左右节点
		//将左右子节点加入到队列中，先加入左节点
		//不为空，添加到队列中
		if(arr[front]->left!=NULL)
		arr[rear++] = arr[front]->left;

		if (arr[front]->right != NULL)
		arr[rear++] = arr[front]->right;

		front++;
	}
	free(arr);
	arr = NULL;
}

上面使用了 BinaryTreeSize（）这个函数，这个函数是用来统计二叉树的节点的个数的，下面也是会介绍这个函数的的实现的。

2.5统计二叉树的节点数

  //二叉树节点个数
int BinaryTreeSize(BTNode* root);

参数：指向根节点的指针

实现的思路：二叉树的节点可以分为：左孩子的节点数+右孩子的节点数+1（根节点的数）

这样就可以使用递归来实现。

实现代码：

//二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	//二叉树节点个数=左字树节点树+右子树节点树+1
	if (root == NULL)
	{
		return 0;
	}

	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}

	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

2.6统计二叉树的叶子节点 

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);

 参数：指向根节点的指针

实现的思路：叶子节点的度为0，其实现的思想和统计二叉树的节点数差不多。

实现代码：

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	else
		return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

2.7二叉树第k层节点个数

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);

参数： 指向根节点的指针，层数k

实现的思路：实际上，递归其实最重要的是，至少找到一个条件使递归停下来，这个也一样，如果到了第k层就停止返回，没有到第k层就持续递归。

实现代码；

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;

	if (k == 1)
	{
		return 1;

	}
	else
	{
		return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);

	}
}

注意事项：else中的函数的第二个参数，是不可以传--k的，这个会使基于同一个父节点的左右子树传入的k值不一致。

2.8二叉树的深度 

//二叉树的深度
int BinaryTreeHeight(BTNode* root); 

参数：指向根节点的指针

实现的思路：二叉树的深度=大的那个子树的深度+1

代码实现： 

//二叉树的深度
int BinaryTreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	else
	{
		int leftheight = BinaryTreeHeight(root->left);
		int rightheight = BinaryTreeHeight(root->right);
		return leftheight > rightheight ? leftheight + 1 : rightheight + 1;

	}
}

2.9二叉树查找值为x的节点

 //二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

参数：指向根节点的指针，需要查找的数据x

如果找到了就直接返回x的节点指针，没有找到就直接返回空。

实际上和前序遍历的思路是一致的，只是多加了一些判断的操作。 

代码实现：

//二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	//根节点是否存在
	if (root == NULL)
		return NULL;

	//找到直接返回根节点
	if (root->data == x)
		return root;

	//根节点不对，查找二叉树的左子树
	BTNode* x1=BinaryTreeFind(root->left, x);
	if (x1 != NULL)
		return x1;

	//根节点不对并且在左字树中没有找到，查找二叉树的右子树
	BTNode* x2 = BinaryTreeFind(root->right, x);
	if (x2 != NULL)
		return x2;

	//根节点，左字树和右字树都都没有找到
	return NULL;
}

2.10 判断二叉树是否是完全二叉树

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);

 参数：指向根节点的指针

实现思路：判断二叉树是否是完全二叉树，不要使用递归来完成，需要是要层序遍历来实现（这里的层序遍历是将空节点也添加到队列中），当出队列的是空节点时，检查队列中是否还有非空节点，如果有那就不是完全二叉树。

实现代码：

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	//使用层序遍历，广度优先
	int num = BinaryTreeHeight(root);
	int n = pow(2, num+1) - 1;
	//使用队列实现
	BTNode** arr = (BTNode**)malloc(n * sizeof(BTNode*));
	if (arr == NULL)
	{
		perror("BinaryTreeLevelOrder::malloc");
		exit(1);
	}
	//队列的前后指针
	int front = 0;
	int rear = 0;
	//将根节点加入队列
	arr[rear++] = root;
	while (front < rear)
	{
		//遇到空节点直接退出
		if (arr[front] == NULL)
			break;

		//这里需要将空节点也放入到数组中
		arr[rear++] = arr[front]->left;
		arr[rear++] = arr[front]->right;

		front++;
	}

	while (front < rear)
	{
		if (arr[front] != NULL)
		{
			free(arr);
			return false;

		}
		front++;
	}


	//全是空节点
	free(arr);
	return true;



}

2.11二叉树的销毁 

// 二叉树销毁
void BinaryTreeDestory(BTNode** root);

参数：指向根节点的二级指针

实现思路：使用后序遍历实现销毁 

代码实现： 

// 二叉树销毁（使用后序遍历删除）
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
		return;
	BinaryTreeDestory(&(*root)->left);
	BinaryTreeDestory(&(*root)->right);

	//释放节点
	free(*root);
	*root = NULL;

}

总结：

  上述就是，二叉树的一些基本的功能呢实现，如果有错误欢迎在评论区或者私信指正。 

标签：遍历,代码,BTNode,基本功能,二叉树,NULL,root,节点
From： https://blog.csdn.net/Mrlossry/article/details/139213525

相关文章

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99