C++链式二叉树深入分析

2024-04-02 19:04:59 709人浏览泡泡鱼

摘要

目录二叉树的结构和概念二叉树的操作前序遍历中序遍历和后序遍历二叉树的节点个数求二叉树叶子结点个数求二叉树的深度在二叉树查找为X的结点之前我们的重点学习二叉树都是完全二叉树，接下来我们

二叉树的结构和概念

二叉树概念是：

1. 空树

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

从概念中可以看出，二叉树定义是递归式的。

我们就手动创建一个二叉树，用于学习二叉树的访问吧，结构如下：

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));
	assert(NewNode);
	NewNode->data = x;
	NewNode->left = NULL;
	NewNode->right = NULL;
	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;
}

我们可以根据上述的结构进行二叉树的后续操作啦。

二叉树的操作

学习二叉树结构，最简单的方式就是遍历。

所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

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

1. 前序遍历(Preorder Traversal )——访问根结点的操作发生在遍历其左右子树之前。

2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。

3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

前序遍历

我们都知道二叉树我们可以分为根左子树右子树，这三个部分，我们先序遍历，就是先访问二叉树的根，在访问左子树，最后访问右子树，如果访问到空树我们使用 ‘*’ 代替，我们用代码控制下：

我们自己创建的二叉树的图如下：

void Preorder(BTNode* root)
{
	if (root == NULL)
	{
		printf("* ");//空树打印 * 
		return ;
	}
	printf("%d ", root->data);//先访问 根
	Preorder(root->left);//再访问左子树
	Preorder(root->right);//最后访问右子树
}

中序遍历和后序遍历

这两个遍历和上面对比就是把访问根的顺序变了，不在详细说了。

void Inorder(BTNode* root)//中序遍历
{
	if (root == NULL)
	{
		printf("* ");//空树打印 * 
		return;
	}
	Preorder(root->left);//先访问左子树
	printf("%d ", root->data);//再访问 根
	Preorder(root->right);//最后访问右子树
}
void Postorder(BTNode* root)//后序遍历
{
	if (root == NULL)
	{
		printf("* ");//空树打印 * 
		return;
	}
	Preorder(root->left);//先访问左子树
	Preorder(root->right);//再访问右子树
	printf("%d ", root->data);//最后访问 根
}

二叉树的节点个数

我们接下来要求出二叉树的节点个数。

1. 我们使用计数器进行操作。缺点：每次使用前全局变量要置为0，比较麻烦。

2. 我们使用分治的思路，转化为这个根+左子树的节点+右子树的节点

我们来一个个实现吧。

思路一：(不常用)

我们定义一个全局变量size，使用前序遍历，然后把其中打印部分去掉换成 ++size即可，我们要在每次使用该函数时，手动把我们定义的全局变量置为0。

int size；
void TreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	size++;//计数器
	TreeSize(root->left);//访问左子树
	TreeSize(root->right);//访问右子树
}
int main()
{
	BTNode* root = CreatBinaryTree();
	size = 0;
	TreeSize(root);
	printf("TreeSize = %d\n", size);
	return 0;
}

思路二：

我们可以使用分治的思想转化为求该节点的左子树+右子数+根，如果为NULL，就返回0.

int TreeSize2(BTNode* root)
{
	if (root == NULL)//为NULL返回0
	{
		return 0;
	}
	return TreeSize2(root->left) + TreeSize2(root->right) + 1;
}

求二叉树叶子结点个数

要求叶子结点，就是左右的子树都是空树，才是一个叶子节点，我们可以转化为求左子树的叶子+右子树的叶子。

int TreeLeafSize(BTNode* root)//求叶子节点
{
	if (root == NULL)//空树返回0
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)//左子树为空并且右子树为空返回1
	{
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

求二叉树的深度

我们还是采用分治的思想，我们先求出左子树的高度，再求出右子树的高度，进行对比，比较时不要忘了自身也是有高度的，最后把二叉树拆到最小的空树时返回0就好啦。

int TreeDepth(BTNode* root)
{
	if (root == NULL)//空树返回0
	{
		return 0;
	}
	int Leftdepth = TreeDepth(root->left);//求出左边高度
	int Rightdepth = TreeDepth(root->right);//求出右边高度
	return Leftdepth > Rightdepth ? Leftdepth + 1 : Rightdepth + 1;//返回时加上自身返回
}

在二叉树查找为X的结点

我们在二叉树中查找结点，可以使用前序遍历，找到该节点时我们直接返回不用在查找。整体上采用前序遍历，我们需要注意，在遍历左右子树时，我们应该保存节点的值方便返回。

BTNode* TreeFind(BTNode* root, BTDataType x)//查找二叉树中值为x的节点
{
	if (root == NULL)//为空返回空
	{
		return NULL;
	}
	if (root->data == x)//相等就返回节点
	{
		return root;
	}
	BTNode* RetLeft = TreeFind(root->left, x);//保存左节点值，方便直接返回
	if (RetLeft)
	{
		return RetLeft;
	}
	BTNode* RetRight = TreeFind(root->right, x);//保存右节点值，方便直接返回
	if (RetRight)
	{
		return RetRight;
	}
	return NULL;//都找不到返回NULL
}