二叉树遍历及应用

2024-01-26 18:20:14 浏览数 (2)

前言

二叉树的遍历及应用主要是运用了递归、分治的思想。在这一篇文章，小编将介绍二叉树的前序遍历、中序遍历、后序遍历，求二叉树结点个数、叶节点个数、第K层结点个数、二叉树的深度。

构建二叉树

手搓二叉树的结构

小编简单构建一个二叉树的结构，方便后面的测试

构建的方式比较简单，在树的结构中有当前结点的数据、当前结点的左节点、右节点。除此之外，还需要开辟结点。

有了 前面数据结构的学习，小编认为手搓一个二叉树的结构相对来说简单一些

代码语言：javascript复制
typedef int Tdatatype;

typedef struct Tree
{
	Tdatatype data;
	struct Tree* left;
	struct Tree* right;
}Tree;

Tree* BuyTree(Tdatatype x)
{
	Tree* node = (Tree*)malloc(sizeof(Tree));
	if (node == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

Tree* CreatTree()
{
	Tree* node1 = BuyTree(1);
	Tree* node2 = BuyTree(2);
	Tree* node3 = BuyTree(3);
	Tree* node4 = BuyTree(4);
	Tree* node5 = BuyTree(5);
	Tree* node6 = BuyTree(6);
	Tree* node7 = BuyTree(7);
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node2->right = node7;
	node4->left = node5;
	node4->right = node6;

	return node1;
}

前序遍历

若二叉树为空，则操作为空 否则： （1）访问根节点 （2）先序遍历左子树 （3）先序遍历右子树

代码语言：javascript复制
void PrevOrder(Tree* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	PrevOrder(root->left);
	printf("%d ", root->data);
	PrevOrder(root->right);
}

中序遍历

若二叉树为空，则操作为空 否则： （1）中序遍历左子树 （2）访问根节点 （3）中序遍历右子树

代码语言：javascript复制
void InOrder(Tree* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

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

后序遍历

若二叉树为空，则操作为空 否则： （1）后序遍历左子树 （2）后序遍历右子树 （3）访问根节点

代码语言：javascript复制
void PostOrder(Tree* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

二叉树的结点个数

求二叉树的结点个数还是用到递归的思想，即子问题分治，还需要有结束条件

子问题分治：左子树结点个数 右子树结点个数 1 返回条件：根节点为空

代码语言：javascript复制
int TreeSize(Tree* root)
{
	return root == NULL ? 0 : TreeSize(root->right)   TreeSize(root->right)   1;
}

二叉树的叶节点个数

求二叉树叶节点个数依然是递归思想

子问题分治：左子树叶子节点个数 右子树叶子节点个数 返回条件：根节点为空，，返回0；是叶子节点，返回1

代码语言：javascript复制
int TreeLeaSize(Tree* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	return TreeLeaSize(root->left)   TreeLeaSize(root->right);
}

二叉树的高度

子问题分治：找左子树和右子树中高度较大的那一个，并 1 返回条件：根节点为空，返回0

代码语言：javascript复制
int TreeHight(Tree* root)
{
	if (root == NULL)
		return 0;
	int left = TreeHight(root->left);
	int right = TreeHight(root->right);
	return left > right ? left   1 : right   1;
}

二叉树第K层结点个数

二叉树第k层的节点数=左子树的第k-1层的节点数 右子树第k-1层的节点数。

因为二叉树没有第0层，是从第一层开始的，所以k==1时，返回1。

代码语言：javascript复制
int TreeLevelK(Tree* root, int k)
{
	assert(k > 0);
	if (root == NULL)
		return 0;

	if (k == 1)
		return 1;

	return TreeLevelK(root->left, k - 1)
		  TreeLevelK(root->right, k - 1);
}
二叉树 root tree 遍历 递归

0 人点赞