【初阶数据结构】二叉树的链式结构

前言

上一节我们介绍了树以及二叉树的相关概念，性质以及结构，这节就来具体介绍二叉树的链式结构。
根据二叉树的概念可知，对于一棵非空二叉树，它的左子树和右子树又分别是不同的二叉树，这就可以看出来了，二叉树最大的特征就是递归，在下面对二叉树的各种操作都是由递归实现。

数据结构专题学习：数据结构学习
C++专题学习：深入学习C++

二叉树的创建

二叉树的创建并不是我们学习的重点，为了后续的学习，我们可以直接简简单单手搓一棵树：

BTNode* BuyNode(int val)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->left = NULL;
	newnode->right = NULL;
	newnode->val = val;
	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; //根节点
}

二叉树的遍历

  对于二叉树这种结构，最简单的操作就是遍历，所谓二叉树的遍历就是按照某种特定的规则，依次访问二叉树中的结点。只有学会了遍历操作，才能对其它的操作更快的学会。而二叉树的遍历总共有四种，分别是：前序遍历，中序遍历，后序遍历以及层序遍历，最重要的就是前面三个。最基本的要求是对于一棵二叉树，要把这四种情况都能写出来。
  由于被访问的结点是某子树的根，所以N(Node)、L(Left subtree)、R(Right subtree)又可以解释为根、根的左子树和根的右子树。所以NLR、LNR、LRN分别又称为先根遍历，中根遍历和后根遍历。

前序遍历

  前序遍历，也称先根遍历（NLR），即访问根节点的操作发生在其遍历左右子树之前，即遍历顺序为：根、左子树、右子树。
因为二叉树是递归式的，所以遍历也用递归实现即可，代码如下：

void PreOrder(BTNode* root)
{
	if(root == NULL)
	{
		printf("空树");
		return ;
	}
	printf("%d ",root->val);  //访问根节点；
	PreOrder(root->left);     //递归遍历左子树
	PreOrder(root->right);    //递归遍历右子树
}

  想要准确的了解一个递归过程，就应该画出图来才能更好的理解，前序遍历的递归展开图如下，在图中也标注的部分顺序，大家可以试着自己画出来：

中序遍历

  中序遍历，也称中根遍历（LNR），即访问根节点的操作发生在其遍历左右子树的中间，即遍历顺序为：左子树、根、右子树。与前序遍历类似，也是递归遍历，具体代码如下：

void InOrder(BTNode* root)//中序遍历
{
	if (root == NULL)
	{
		printf("空树");
		return;
	}
	InOrder(root->left);     //递归遍历左子树
	printf("%d ", root->val);  //访问根节点；
	InOrder(root->right);    //递归遍历右子树
}

后序遍历

  后序遍历，也称后根遍历（LRN），即访问根节点的操作发生在其遍历左右子树之后，即遍历顺序为：左子树、右子树、根。与前序遍历和中序遍历类似，同样是递归遍历，具体代码如下：

void PostOrder(BTNode* root)//后序遍历
{
	if (root == NULL)
	{
		printf("空树");
		return;
	}
	PostOrder(root->left);     //递归遍历左子树
	PostOrder(root->right);    //递归遍历右子树
	printf("%d ", root->val);  //访问根节点；
}

层序遍历

  层序遍历与先，中，后序遍历有所不同。所谓层序遍历就是从二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第二层上的节点，接着是第三层的节点，以此类推，自上而下，从左至右逐层访问树的节点的过程就是层序遍历。
过程如下图所示：

对于层序遍历，就需要借助一个队列。层序遍历的思想如下：

1. 首先将根节点入队。
2. 若队列非空，则队头节点出队，并访问该节点。若它有左孩子或者右孩子，则将它的孩子依次入队。
3. 重复步骤2，直至队列为空。

具体代码如下：

void LevelOrder(BTNode* root)//层序遍历
{
	Queue q;
	QueueInit(&q);//初始化一个队列
	if (root)//如果根节点不为空，则将根节点放入队列中
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);   //取出队头元素
		printf("%d ", front->val);
		QueuePop(&q);                     //队头节点出队列
		if (front->left)
			QueuePush(&q, front->left);   //左孩子不为空，则左孩子入队
		if(front->right)
			QueuePush(&q, front->right);  //右孩子不为空，则右孩子入队
	}
	printf("\n");
	QueueDestroy(&q);
}

注：队列相关代码问题请参考：【初阶数据结构】队列。

二叉树的结点数相关问题

不仅是二叉树的遍历操作要用到递归，关于二叉树节点数相关问题也用的递归，如下面几个操作。

二叉树的结点个数

  由前面我们知道，一棵二叉树可以分为根，左子树和右子树三个部分，那么想要求二叉树的节点个数时，只要知道左子树节点个数和右子树节点个数，再加上根结点就是整棵二叉树的节点个数。
即二叉树的节点个数=左子树节点个数+右子树节点个数+1。
代码如下：

int TreeSize(BTNode* root)
{
	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层结点个数

  和上面一样的方式，当我想求第k层的节点个数时，只要知道左子树的第k-1层节点数+右子树的k-1层节点数即可。直到递推到k==1时，若还有节点则返回1，没有节点则返回0。
如对于我想求第3层的节点个数，就等于左子树第2层的节点数+右子树第2层的节点数，直到左右子树的第k=1层结束。
代码如下：

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

二叉树查找值为x的结点

  想要查找值为x的节点，其实也就是要遍历各个节点，找到相同的节点。我们可以直接将前序遍历的代码进行改造，先遍历根结点，看是否为x若不是，则去左子树找，左子树找完去右子树找。
  递归结束的两个条件：一个是如果访问的节点为空时，就返回空，另一个是如果节点与x对应，则直接返回该节点。
代码如下：

BTNode* TreeFind(BTNode* root, int x)
{
	if (root == NULL)
		return NULL;
	if (root->val == x)
		return root;
	BTNode* ret1 = TreeFind(root->left, x);
	if (ret1)
		return ret1;
	BTNode* ret2 = TreeFind(root->right, x);
	if (ret2)
		return ret2;
	return NULL;//最后找不到则返回NULL
}

二叉树的高度

  求二叉树高度也是一样的，我只要知道左子树高度和右树高度哪个更高，用高的那棵树的高度加1就是树的高度。
代码如下：

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

感谢大家观看，如果大家喜欢，希望大家一键三连支持一下，如有表述不正确，也欢迎大家批评指正。