数据结构——二叉树的链式结构

03-01 1315阅读

数据结构——二叉树的链式结构

 个人主页：日刷百题

系列专栏：〖C语言小游戏〗〖Linux〗〖数据结构〗 〖C语言〗

🌎欢迎各位→点赞👍+收藏⭐️+留言📝 ​

数据结构——二叉树的链式结构

一、二叉树的创建

这里我们使用先序遍历的思想来创建二叉树，这里的内容对于刚接触二叉树的朋友可能有些难理解，不妨先看完下面的二叉树各种遍历再来看创建就会简单很多，为了保持文章的整体性，先讲二叉树的创建。

数据结构——二叉树的链式结构

当然为了后续内容能够衔接，我们先手动创建一个固定的树，就是上面这棵树，后续内容全部围绕这棵树

typedef int DataType;
typedef struct TreeNode
{
	DataType data;
	struct  TreeNode* left;
	struct  TreeNode* right;
}TreeNode;
TreeNode* BuyNode(int x)
{
	TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
	if (node == NULL)
	{
		perror("malloc fail:");
		return NULL;
	}
	node->data = x;
	node->left = node->right = NULL;
}
	
TreeNode* CreatTree()
{
	TreeNode* node1 = BuyNode(1);
	TreeNode* node2 = BuyNode(2);
	TreeNode* node3 = BuyNode(3);
	TreeNode* node4 = BuyNode(4);
	TreeNode* node5 = BuyNode(5);
	TreeNode* node6= BuyNode(6);
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	return node1;
}

现在开始讲如何用前序遍历方式来进行创建二叉树，这里给俩种创建方法。

1.1  返回根节点指针创建

注：我们用前序遍历方式输入数字，-1代表空，上面的二叉树可写为：1 2 3 -1 -1 -1 4 5 -1 -1 6 -1 -1

TreeNode* CreatTree()
{
	int i;
	scanf("%d", &i);
	
	if (i == -1)
	{
		return NULL;
	}
	TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
	if (root == NULL)
	{
		perror("malloc fail:");
		exit(-1);
	}
	root->data = i;
	root->left =  CreatTree();
	root->right = CreatTree();
	return root;
}

注：return root 是不能省略的，递归返回时，遇到空返回；或者构建完子数，返回根节点，作为上一级左子树，构建完子树，返回根节点，作为上一级右子树，依次递归回去，直到返回整个数的根节点

数据结构——二叉树的链式结构

1.2 二级指针传参创建

同样的，依然构建上面的而二叉树，用前序遍历方式输入数字，-1代表空，上面的二叉树可写为：1 2 3 -1 -1 -1 4 5 -1 -1 6 -1 -1

void CreatTree(TreeNode** root)
{
	int i;
	scanf("%d", &i);
	if (i == -1)
	{
		*root = NULL;
	}
	else
	{
		*root = (TreeNode*)malloc(sizeof(TreeNode));
		if (*root == NULL)
		{
			perror("malloc fail:");
			exit(-1);
		}
		(*root)->data = i;
		CreatTree(&((*root)->left));
		CreatTree(&((*root)->right));
	}
}

 注：二级指针传参可以改变一级指针的指向，同样的，这里创建好根节点后，创造左子树，在创造右子树，依次递归下去。

数据结构——二叉树的链式结构

二、二叉树的遍历

我们先从最简单的操作----遍历学起。所谓二叉树遍历(Traversal)就是按照某种特定的规则，依次对二叉树中的结点进行相应的操作，并且每个节点有且只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。二叉树的遍历分为四种：前序遍历、中序遍历、后序遍历和层序遍历。

2.1 前序遍历

前序遍历（Preorder Traversal）又称先根遍历，即先遍历根结点，再遍历左子树，最后遍历右子树。而对于子树的遍历，也服从上述规则。利用递归，我们可以很快地写出代码：

// 二叉树前序遍历
void PreOrder(TreeNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return ;
	}
	printf("%d ", root->data);
	 PreOrder(root->left);
	 PreOrder(root->right);
}

便于我们更好的理解，我们画出递归展开图

数据结构——二叉树的链式结构

2.2 中序遍历

中序遍历（Inorder Traversal）又称中根遍历，即先遍历左子树，再遍历根结点，最后遍历右子树。同样，子树的遍历规则也是如此。递归代码如下：

// 二叉树中序遍历
void InOrder(TreeNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return ;
	}
	
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

2.3 后序遍历

后序遍历（Inorder Traversal）又称后根遍历，即先遍历左子树，再遍历右子树，最后遍历根结点。递归代码如下：

// 二叉树后序遍历
void PostOrder(TreeNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return ;
	}
	PostOrder(root->left);
	
	PostOrder(root->right);
	printf("%d ", root->data);
}

2.4  层序遍历

除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在 层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推， 自上而下，自左至右逐层访问树的结点 的过程就是层序遍历。 层序遍历借助队列实现，思路解析图如下： 数据结构——二叉树的链式结构
//层序遍历
void LevelOrder(TreeNode* root)
{
	Queue pq;
	QueueInit(&pq);
	if (root == NULL)
	{
     QueueDestroy(&pq);
		return;
	}
	QueuePush(&pq,root);
	while (!QueueEmpty(&pq))
	{
		TreeNode* front= QueueFront(&pq);
		printf("%d ", front->data);
		 QueuePop(&pq);
		 if (front->left!= NULL)
		 {
			 QueuePush(&pq, front->left);
			 
		 }
		 if (front->right != NULL)
		 {
			 QueuePush(&pq, front->right);
		 }
	}
	
	QueueDestroy(&pq);
}

数据结构——二叉树的链式结构

思考：当然层序遍历这里有一个变形，我们能不能将二叉树每一层打印单独放一行，该怎么做呢？

思路：

（1）设二叉树的根节点所在层数为1，第一层根节点进队列，队列元素个数为1，size==1

（2）每出队列一次，size--,根节点出完队列，俩个子节点进队列,此时队列元素个数为第二层节点个数，size==2

（3）当我们出队列size次，把第二层元素出完，队列剩下的元素是第三层节点，size==QueueSize

以此类推，以size为循环条件，则可实现每层单独打印一行

void LevelOrder(TreeNode* root)
{
	Queue pq;
	QueueInit(&pq);
	if (root == NULL)
	{
		QueueDestroy(&pq);
		return;
	}
	QueuePush(&pq,root);
	int size = 1;
	while (!QueueEmpty(&pq))
	{
		while (size--)
		{
			TreeNode* front = QueueFront(&pq);
			printf("%d ", front->data);
			QueuePop(&pq);
			if (front->left != NULL)
			{
				QueuePush(&pq, front->left);
			}
			if (front->right != NULL)
			{
				QueuePush(&pq, front->right);
			}
		}
		size = QueueSize(&pq);
		printf("\n");
	}
	
	QueueDestroy(&pq);
}

数据结构——二叉树的链式结构

三、二叉树的结点

3.1 二叉树的总结点数

一颗二叉树的结点数我们可以看作是根结点+左子树结点数+右子树结点数，那左右子树的结点数又是多少呢？按照相同的方法继续拆分，层层递归直到左右子树为空树，返回空树的结点数0即可。递归代码如下：

// 二叉树节点个数
int TreeSize(TreeNode* root)
{
	return root == NULL? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

3.2 二叉树的叶子结点数

左右子树都为空的结点即是叶子结点。这里分为两种情况：左右子树都为空和左右子树不都为空。

（1）当左右子树都为空时，则这颗树的叶子结点数为1(根节点)。

（2）当左右子树不都为空，即根结点不是叶子结点时，这棵树的叶子结点数就为左子树叶子结点数+右子树叶子结点数（空树没有叶子结点）。

 

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

3.3 二叉树第k层结点数

一颗树第k层的结点数我们可以拆分为其左子树第k-1层结点+右子树第k-1层结点。（注：当前节点为第一层）

（1）若为空树，无论哪层节点数都是0

（2）若不是空树且k==1,则只有一个节点（根节点）

// 二叉树第k层节点个数
int TreeLevelKSize(TreeNode* root, int k)
{
	assert(k > 0);
	if (root!=NULL&&k == 1)
	{
		return 1;
	}
	if (root == NULL)
	{
		return 0;
	}
	if (k > 1)
	{
		return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
	}
}

// 判断二叉树是否是完全二叉树
bool TreeComplete(TreeNode* root)
{
	Queue pq;
	QueueInit(&pq);
	if (root == NULL)
	{
		QueueDestroy(&pq);
		return;
	}
	QueuePush(&pq, root);
	
	while (!QueueEmpty(&pq))
	{
		
			TreeNode* front = QueueFront(&pq);
			
			QueuePop(&pq);
			if (front == NULL)
			{
				break;
			}
				QueuePush(&pq, front->left);
			
				QueuePush(&pq, front->right);
			
	}
	while (!QueueEmpty(&pq))
	{
		TreeNode* front = QueueFront(&pq);
		QueuePop(&pq);
		if (front != NULL)
		{
			return false;
		}
	}
	QueueDestroy(&pq);
	return true;
}

四、二叉树的查找

二叉树的查找本质上就是一种遍历，只不过是将之前的打印操作换为查找操作而已。我们可以使用前序遍历来进行查找：

（1）先比较根结点是否为我们要查找的结点，如果是，返回根节点地址

（2）如果不是，遍历左子树，如果左子树是，直接返回节点地址；不是则遍历右子树，如果右子树是，直接返回节点地址，不是返回空，说明左右子树都没找到。

// 二叉树查找值为x的节点
TreeNode* TreeFind(TreeNode* root, DataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	TreeNode* node1 = TreeFind(root->left, x);
	if (node1)
	{
		return node1;
	}
	TreeNode* node2 = TreeFind(root->right, x);
	if (node2)
	{
		return node2;
	}
	return NULL;
}

五、二叉树的高度/深度

树中结点的最大层次称为二叉树的高度。因此，一颗二叉树的高度我们可以看作是

1(根结点)+左右子树高度的较大值。层层递归下去直到遇到空树返回0即可，

这里值得注意的是：不要写成

return TreeHeight(root->left)>TreeHeight(root->right) ? 
		TreeHeight(root->left)+1:TreeHeight(root->right)+1;
}
这里比较好左右子树较大的一颗后，又会从新递归较大那颗子树高度，会造成重复计算，时间复杂度增高。

我们要保存好左右子树层数，避免重复计算，代码如下：

//二叉树的高度
int TreeHeight(TreeNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int left = TreeHeight(root->left);
	int right = TreeHeight(root->right);
	return  left>right ? 
		left+1:right+1;
}

六、完全二叉树的判断

这里的思路利用了层序遍历，不同的是，将空节点指针也入队列，当我们遇到第一个空节点指针则退出循环，然后对队列进行检测，若第一个空节点指针以后全都是空，则为完全二叉树，反之，不为完全二叉树。

注：当在队列遇到第一个空节点指针时，二叉树中空节点指针之后所有非空节点指针全部进队列

思路解析图如下：

数据结构——二叉树的链式结构

代码如下：

// 判断二叉树是否是完全二叉树
bool TreeComplete(TreeNode* root)
{
	Queue pq;
	QueueInit(&pq);
	if (root == NULL)
	{
		QueueDestroy(&pq);
		return;
	}
	QueuePush(&pq, root);
	
	while (!QueueEmpty(&pq))
	{
		
			TreeNode* front = QueueFront(&pq);
			
			QueuePop(&pq);
			if (front == NULL)
			{
				break;
			}
				QueuePush(&pq, front->left);
			
				QueuePush(&pq, front->right);
			
	}
	while (!QueueEmpty(&pq))
	{
		TreeNode* front = QueueFront(&pq);
		QueuePop(&pq);
		if (front != NULL)
		{
			return false;
		}
	}
	QueueDestroy(&pq);
	return true;
}

 七、二叉树的销毁

7.1 一级指针传参销毁

同样的，和创建节点一样，我们给出俩个销毁方式：

(1)一种是传一级指针方式，这种方式不是改变根节点的指向，需要在销毁函数结束后，将root置为NULL

void TreeDestroy(TreeNode* root)//出来将root=NULL
{
	if (root == NULL)
	{
		return;
	}
	TreeDestroy(root->left);
	TreeDestroy(root->right);
	free(root);
}

7.2 二级指针传参销毁 

(2)另一种是传二级指针，直接在函数内部将每一个销毁的节点指针置为NULL.

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

 总结：本篇文章将二叉树的基础知识差不多囊括了，后续的话还需要大量练习做巩固加强，递归比较抽象难以理解，需要动手画递归展开图进行帮助理解。

希望大家阅读完可以有所收获，同时也感谢各位铁汁们的支持。文章有任何问题可以在评论区留言，百题一定会认真阅读！

数据结构——二叉树的链式结构

VPS购买请点击我

文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。

相关阅读

目录[+]