网络知识 娱乐 二叉树的讲解《四》(链式二叉树)

二叉树的讲解《四》(链式二叉树)

  个人主页:欢迎大家光临——>沙漠下的胡杨

  各位大帅哥,大漂亮

 如果觉得文章对自己有帮助

 可以一键三连支持博主

 你的每一分关心都是我坚持的动力

 

 ☄: 本期重点:链式二叉树

  希望大家每天都心情愉悦的学习工作。 


 ☄: 本期重点:链式二叉树

二叉树的结构和概念:

二叉树的操作:

前序遍历:

中序遍历和后序遍历:

二叉树的节点个数:

求二叉树叶子结点个数:

求二叉树的深度:

在二叉树查找为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 = %dn", 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
}