小蓝xlanll

这个屌丝很懒，什么也没留下！

热门标签

【数据结构】二叉树——链式结构的实现（代码演示）_二叉树的存储结构及代码

作者：小蓝xlanll | 2024-05-19 11:02:54

踩

二叉树的存储结构及代码

1 二叉树的链式结构


typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

该结构包含根节点、左子树(_left)和右子树(_right)以及它们所存储的数据(data)

二叉树是：

空树
非空：根节点，根节点的左子树、根节点的右子树组成的。

2 二叉树的创建


// 通过前序遍历的数组"123###45##6##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)  
{
 
	BTNode* cur = (BTNode*)malloc(sizeof(BTNode));
	if (cur == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	if (*pi >= n || a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
 
	cur->_data = a[*pi];
	(*pi)++;
 
	cur->_left = BinaryTreeCreate(a, n, pi);
	cur->_right = BinaryTreeCreate(a, n, pi);
 
	return cur;
}

代码表示用前序遍历创建二叉树，参数a表示传进来的数组首元素地址，参数n表示数组长度，参数pi表示下标的地址，这里用指针表示，因为如果不用指针，则递归的过程中重新定义的pi已经不是原来的pi,即找不到下标了。

第一个if语句表示创建失败后执行；第二个if语句表示如果下标pi大于数组长度n或者数组元素等于'#'，下标的位置往后移动一个位置，返回值为NULL; cur->_data = a[*pi]表示将数组中下标为pi的元素赋给当前节点cur->_data；

这里创建了一个二叉树作为例子：

3 二叉树的遍历

二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

前序遍历：访问根结点的操作发生在遍历其左右子树之前。根、左子树、右子树。

中序遍历：访问根结点的操作发生在遍历其左右子树之中（间）。左子树、根、右子树。

后序遍历：—访问根结点的操作发生在遍历其左右子树之后。左子树、右子树、根。

层序遍历：先访问根节点，然后从左往右访问第二层，依次访问下面的节点。

3.1 前序遍历


 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
        printf("NULL");
		return ;
	}
//	printf("%c ", root->_data);
	printf("%d ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}

代码表示：如果节点为空，则返回空值；打印根节点的值，左子树递归，右子树递归。

这里给出运行前序遍历的完整代码：


#define  _CRT_SECURE_NO_WARNINGS
//#include"Heap.h"
#include<time.h>
#include"Quene.h"
 
//typedef char BTDataType;
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;
 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return ;
	}
//	printf("%c ", root->_data);
	printf("%d ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}
 
int main()
{
	//BTDataType a[] = { 'A','B','D','#','#','E','#','H','#','#','C','F','#','#','G','#','#' };
	BTDataType a[] = { 1,2,3,'#','#','#',4,5,'#','#',6,'#','#' };
	int n = sizeof(a) / sizeof(a[0]);
	int i = 0;
	BTNode* root = BinaryTreeCreate(a, n, &i);
 
	BinaryTreePrevOrder(root);                 //前序遍历:根，左子树，右子树
	printf("\n");
return 0;
}

3.1.1运行结果：

3.1.2代码演示图:

3.1.3 演示分析：

(跟着箭头看)首先从根节点“1”开始递归，printf("%d ",root->_data)打印根节点“1”的值;BinaryTreePrevOrder（root->_left）对左子树进行递归;打印左子树根节点 “2"的值;BinaryTreePrevOrder（root->_left）继续对左子树进行递归，打印左子树根节点“3”的值；

BinaryTreePreOrder(root->_left)继续对左子树进行递归，root==NULL,打印空值，返回空,此时函数回到调用它的地方，并销毁栈帧，即回到它的父节点"3"的BinaryTreePrevOrder(root->_left)语句哪里;接下来执行BinaryTreePreOrder(root->_right)语句，root==NULL,打印空值，返回空,此时函数回到调用它的地方，并销毁栈帧，即回到它的父节点"2"的BinaryTreePreOrder(root->_right)语句哪里；然后依此类推。

3.2 中序遍历


void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		return ;
	}
 
	BinaryTreeInOrder(root->_left);
//	printf("%c ", root->_data);
	printf("%d ", root->_data);
	BinaryTreeInOrder(root->_right);
}

其实它的代码和前序遍历差不多，只是中序遍历要先走完左子树，才走根节点，最后右子树。

运行结果：

3.3 后序遍历


void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return ;
	}
	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	//printf("%c ", root->_data);
	printf("%d ", root->_data);
}

其实后续遍历的代码和前序遍历的代码差别不大，唯一差别就是，后序遍历是递归完左子树和右子树之后才打印根节点。

3.4 层序遍历


void BinaryTreeLevelOrder(BTNode* root)
{
	Quene qu;
	QueneInit(&qu);
	if(root)
		QuenePush(&qu, root);
	while (!QueneEmpty(&qu))
	{
		BTNode* cur = QueneFront(&qu);  
//		printf("%c ", cur->_data);
		printf("%d ", cur->_data);
		QuenePop(&qu);
 
		if (cur->_left)
		{
			QuenePush(&qu, cur->_left);
		}
		if (cur->_right)
		{
			QuenePush(&qu, cur->_right);
		}
	}
	printf("\n");
	QuenDestroy(&qu);
}

层序遍历，我采用队列的链式结构对二叉树的节点的值进行存储。

思路：出上一层，带下一层

代码分析：按照思路，队头先出“1”，然后把“1”的左节点"2"和右节点"4"尾插进队列,然后出“2”，把“2”的左节点“3”尾插进队列，然后队头出“4”，把“4”的左节点“5”和右节点“6”尾插进队列。以此类推。QueneInit(&qu);表示初始化队列"qu"; QuenePush(&qu, root);表示将二叉树的值尾插到队列中；BTNode* cur = QueneFront(&qu); 表示创建一个二叉树结构体类型的节点cur来存放队列首元素的值； QuenePop(&qu);表示出队列。

4 判断是否是完全二叉树


bool BinaryTreeComplete(BTNode* root)
{
	Quene qu;
	QueneInit(&qu);
if(root)
	QuenePush(&qu, root);
 
	while (!QueneEmpty(&qu)) 
	{
		BTNode* front = QueneFront(&qu);
		QuenePop(&qu);
		if (front == NULL)               //如果当前节点不为空，则将它的左右节点放入队列
		{
			break;
		}
		else
		{
			QuenePush(&qu, front->_left);
			QuenePush(&qu, front->_right);
		}
	}
	//出到空以后，如果后面全是空，则是完全二叉树
	while (!QueneEmpty(&qu))
	{
		BTNode* front = QueneFront(&qu);
		QuenePop(&qu);
		if (front != NULL)
		{
			QuenDestroy(&qu);
			return false;
		}
	}
	QuenDestroy(&qu);
	return true;
 
}

思路：二叉树的节点出队列遇到空值以后，往后都是空值则是完全二叉树，否则不是。

代码分析：如果二叉树的当前节点不为空，入队列;如果队列不为空，先出队列，然后将它的左右节点尾插进队列；第二个while哪里，队列不为空，出队列，遇到空值后，往后都是空值，则为完全二叉树，否则不是完全二叉树。

5 二叉树节点的个数

5.1 总个数


int BinaryTreeSize(BTNode* root)
{
	//if (root == NULL)
	//{
	//	return 0;
	//}
	//int left = BinaryTreeSize(root->_left);
	//int right = BinaryTreeSize(root->_right);
 
	//return left + right +1;//返回总节点个数
	return root==NULL ? 0:BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1; 
}

思路：如果二叉树的节点为空，则返回0，否则计算出左边 + 右边 + 1。

5.2 叶子节点个数


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

思路：如果该节点为空，返回0；如果该节点的左右节点都为空，返回1；对左子树和右子树递归。

6 二叉树的深度


int TreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
 
	int leftHeight = TreeHeight(root->_left);
	int rightHeight = TreeHeight(root->_right);
 
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

这里需要注意的是要定义两个整形变量来存放左节点和右节点的个数，如果不定义直接

return TreeHeight(root->_left) >TreeHeight(root->_right) ? TreeHeight(root->_left)+1: TreeHeight(root->_right)+1;性能会下降很多，因为在"?"前面的递归只是做了比较，并没有保存比较的值，使得出现很多重复的计算，会极大的浪费资源，上一层会连累下一层，每一层都要重复计算。

7 二叉树的销毁

7.1 二级指针销毁二叉树


void BinaryTreeDestory(BTNode** root) //参数root是一个指向指针的指针，因为需要修改每个节点的指针
{
	if (*root)
	{
		BinaryTreeDestory(&(*root)->_left);
		BinaryTreeDestory(&(*root)->_right);
		free(*root);
		*root = NULL;      //防止内存泄露
	}
 
}

说明：这里使用后续遍历对二叉树的节点进行置空。

BinaryTreeDestroy(&((*root)->left)) 中的 (*root)->left 是一个指向左子树根节点的指针，它的类型为 TreeNode*。因此，我们需要先用 * 运算符解引用 root 指向的地址，得到指向二叉树根节点的指针 *root，然后再使用箭头运算符 -> 访问其左子树，并取其地址作为参数传递给 BinaryTreeDestroy() 函数。

这样做是因为我们需要修改根节点的左子树指针，使其指向空，并释放原来左子树所占用的内存。如果直接传递 (*root)->left 作为参数，则只是将一个指向左子树根节点的临时指针传递给了函数，在函数内部无法修改原来的左子树指针。

在这个函数中，使用了一个BTNode**类型的指针作为参数。这个指针指向了二叉树根结点的地址。在函数内部，首先判断当前节点是否为空，如果为空则直接返回。然后递归地销毁当前节点的左子树和右子树，直到最底层的叶子节点。最后释放当前节点所占用的内存，并将其只想空指针以避免野指针。