【初阶数据结构】二叉树链式结构的实现和遍历

 =========================================================================

个人主页

代码仓库

C语言专栏

初阶数据结构专栏

Linux专栏

 =========================================================================

目录

前言

二叉树链式结构的实现

二叉树的遍历

前序、中序和后序遍历

前序遍历

中序遍历

后序遍历

求结点个数

求总的结点个数 

创建变量求结点

创建静态修饰变量

拆分左右子树加根

求叶子节点的个数

求第K层结点个数

---

前言

在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入，为了降低大家学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。

---

二叉树链式结构的实现

我们可以将一个二叉树分成左右两个子树，两个子树又一次分成两个子树，这样一个二叉树就可以被我们拆解左右拆解开来，如果没有左/右孩子记作空。

代码实现

typedef struct BinaryTreeNode 
{
	struct BinaryTreeNode * left;
	struct BinaryTreeNode* right;
	int  val;
}BTNode;
BTNode* BuyBTNode(int x)
{
	BTNode* tmp = (BTNode*)malloc(sizeof(BTNode));
	if (tmp == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}
	tmp->val = x;
	tmp->left = NULL;
	tmp->right = NULL;
	return tmp;
}
int main()
{
	BTNode* node1 = BuyBTNode(1);
	BTNode* node2 = BuyBTNode(2);
	BTNode* node3 = BuyBTNode(3);
	BTNode* node4 = BuyBTNode(4);
	BTNode* node5 = BuyBTNode(5);
	BTNode* node6 = BuyBTNode(6);
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	return 0;
}

创建一个结构体里面有左右两个结构体指针分别指向自己左右孩子 ，像这样上面那个二叉树就使用代码实现了。

注意：上述代码并不是创建二叉树的方式，真正创建二叉树方式后序详解重点讲解。
再看二叉树基本操作前，再回顾下二叉树的概念，二叉树是：
1. 空树
2. 非空：根节点，根节点的左子树、根节点的右子树组成的。

从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。

---

二叉树的遍历

前序、中序和后序遍历

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

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：
1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。 

简单点来说：

前序遍历：先访问根，在访问左子树，最后访问右子树。

中序遍历：先访问左子树，在访问根，最后访问右子树。

后序遍历：先访问左子树，在访问右子树，最后访问根。

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

这里的N代表空（NULL）。

前序遍历

二叉树的遍历是使用函数递归实现的，从根开始一次分为左右子树向下遍历左右子树左右子树不存在的话为空（NULL）。

前序遍历图解

 实现代码

void PrevOrder(BTNode* node)
{
	if (node == NULL)
	{
		printf("NULL ");
		return ;
	}
	printf("%d ", node->val);
	PrevOrder(node->left);
	PrevOrder(node->right);
}

首先判断根节点是否为空，如果为空则代表空树返回NULL；前序遍历是先访问的根，因此直接打印数据，在依次进入左右子树。这里文字很难讲解清楚，我们直接上函数递归调用图。

中序遍历

这里我就不给大家图解了，大家可以自己尝试画一下。

实现代码 

void InOrder(BTNode* node)
{
	if (node == NULL)
	{
		printf("NULL ");
		return ;
	}
	InOrder(node->left);
	printf("%d ", node->val);
	InOrder(node->right);
}

首先判断根节点是否为空，如果为空则代表空树返回NULL；中序遍历是先访问的左子树，因此一直遍历到最后一个根指向的左子树为空时，打印此时根的数据，在依次进入左右子树。

后序遍历

实现代码

void PostOrder(BTNode* node)
{
	if (node == NULL)
	{
		printf("NULL ");
		return ;
	}
	PostOrder(node->left);
	PostOrder(node->right);
	printf("%d ", node->val);
}

首先判断根节点是否为空，如果为空代表空树返回NULL；后序遍历也是先访问左子树，因此一直遍历到最后一个根指向的左子树为空时打印此时根的数据，在打印其父亲指向的右子树的数据，最后打印左右子树父亲的数据。

---

求结点个数

求总的结点个数 

创建变量求结点

很多小伙伴，会想到创建一个变量函数递归依次就代表一个结点，每次递归就加加一次，这样根本

不对，因为变量是开辟在栈区上的函数每次调用都会创建，出函数也都会销毁，这种办法根本行不通。

创建静态修饰变量

使用变量可能会销毁，那我就创建静态变量改变它的生命周期，这样就可以了，求一个二叉树的总节点个数可以，但是我们有多个二叉树呢？也可以解决：在每次求总结点个数前将变量置零就可以了，这是一个可行的办法。

ps:静态变量在函数递归是只会创建一次哦！！！

拆分左右子树加根

二叉树最重要的思想就是拆分二叉树，这里我们将二叉树分成左右子树，使用递归求左右子树的结点个数每次再加上根节点是不是就是总的节点数？

实现代码

int size = 0;
int TreeSize(BTNode* root)
{
	//静态区的变量只初始化一次
	// int size=0;
    //直接使用变量不推荐
	//static int size = 0;
	//if (root == NULL)
	//{
	//	return 0;
	//}
	//else
	//{
	//	++size;
	//}
	//TreeSize(root->left);
	//TreeSize(root->right);
	//return size;
 
	//优化
	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

求叶子节点的个数

情况1：当为空树是叶子节点为空；

情况2：当左右子树为空时叶子结点为1；

情况3：还是使用拆分的方法将一个二叉树拆分，使用递归求解； 

实现代码

int TreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

求第K层结点个数

假设我们求第三层，还是使用递归拆分树的方法，拆分成左子树的第二层（k-1）加上右子树的第二层（k-1）层。

实现代码

int TreeKlevel(BTNode* root,int k)
{
	assert(k > 0);
	if (root == NULL)
	{
		return 0;
	}
 
	if (k == 1)
	{
		return 1;
	}
	return TreeKlevel(root->left, k - 1) + TreeKlevel(root->right, k - 1);
}

完整代码

#define _CRT_SECURE_NO_WARNINGS 67
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef struct BinaryTreeNode 
{
	struct BinaryTreeNode * left;
	struct BinaryTreeNode* right;
	int  val;
}BTNode;
BTNode* BuyBTNode(int x)
{
	BTNode* tmp = (BTNode*)malloc(sizeof(BTNode));
	if (tmp == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}
	tmp->val = x;
	tmp->left = NULL;
	tmp->right = NULL;
	return tmp;
}
void PrevOrder(BTNode* node)
{
	if (node == NULL)
	{
		printf("NULL ");
		return ;
	}
	printf("%d ", node->val);
	PrevOrder(node->left);
	PrevOrder(node->right);
}
void InOrder(BTNode* node)
{
	if (node == NULL)
	{
		printf("NULL ");
		return ;
	}
	InOrder(node->left);
	printf("%d ", node->val);
	InOrder(node->right);
}
void PostOrder(BTNode* node)
{
	if (node == NULL)
	{
		printf("NULL ");
		return ;
	}
	PostOrder(node->left);
	PostOrder(node->right);
	printf("%d ", node->val);
}
//求结点个数
int size = 0;
int TreeSize(BTNode* root)
{
	//静态区的变量只初始化一次
	// int size=0;
	//static int size = 0;
	//if (root == NULL)
	//{
	//	return 0;
	//}
	//else
	//{
	//	++size;
	//}
	//TreeSize(root->left);
	//TreeSize(root->right);
	//return size;
 
	//优化
	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
//求叶子结点个数
int TreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
//求第K层的结点个数
int TreeKlevel(BTNode* root,int k)
{
	assert(k > 0);
	if (root == NULL)
	{
		return 0;
	}
 
	if (k == 1)
	{
		return 1;
	}
	return TreeKlevel(root->left, k - 1) + TreeKlevel(root->right, k - 1);
}
int main()
{
	BTNode* node1 = BuyBTNode(1);
	BTNode* node2 = BuyBTNode(2);
	BTNode* node3 = BuyBTNode(3);
	BTNode* node4 = BuyBTNode(4);
	BTNode* node5 = BuyBTNode(5);
	BTNode* node6 = BuyBTNode(6);
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
 
	//前序遍历
	PrevOrder(node1);
 
	printf("\n");
	//中序遍历
	InOrder(node1);
	printf("\n");
	//后序遍历
	PostOrder(node1);
	printf("\n");
	printf("%d \n", TreeSize(node1));
	printf("%d\n", TreeLeafSize(node1));
	printf("%d\n", TreeKlevel(node1, 3));
	return 0;
}

---

总结： 二叉树的遍历是用函数递归实现的，确实比较难以理解，我们不仅仅是只做到代码实现层面，还好依据函数递归画出递归的展开图，以便于我们理解和加深印象，这块部分还得多画图。