W...Y的主页 😊

代码仓库分享 💕

之前我们实现了用顺序表完成二叉树(也就是堆)，顺序二叉树的实际作用就是解决堆排序以及Topk问题。

今天我们要学习的内容是链式二叉树，并且实现链式二叉树，这篇博客与递归息息相关！

链式存储

二叉树链式结构的实现

链式二叉树的快速创建

二叉树的遍历

前序、中序以及后序遍历

前序遍历的实现

中序遍历的实现

后序遍历实现

节点个数以及高度

总结点个数

叶子节点个数

第k层节点个数

整个代码模板以及验证

链式存储

什么是链式存储，就是用链来指示元素的逻辑关系。链式结构又分为二叉链和三叉链，而我们今天学习的是二叉链表，又称链式二叉树。

我们一般用链表来表示一棵二叉树，通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{struct BinTreeNode* _pLeft; // 指向当前节点左孩子struct BinTreeNode* _pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域
}

对于链式二叉树，我们与其他前面的链表、顺序表、堆……数据结构有所不同，我们针对这一块并不是增删查改，为什么呢?

因为链式二叉树的存储方式，就是把每一个节点封装在结构体中然后进行链接，而我们进行增删查改没有必要在这么复杂的结构中实现，当我有每个节点的左右指针时，我可以随心所欲，在哪里都可以进行插入删除。如果非得使用增删查改，我们就可以使用简单一些的数据结构进行。

所以我们学习链式二叉树是为了给我们后面的高级数据结构AVL、红黑树打基础的。所以我们也要认真学！！！

二叉树链式结构的实现

链式二叉树的快速创建

我们为了快速实现链式二叉树，从中感受到链式二叉树的结构，我们快速手动生成一个链式二叉树。

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;struct BinaryTreeNode* right;int val;
}BTNode;
BTNode* BuyNode(int x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");exit(-1);}node->val = x;node->left = NULL;node->right = NULL;return node;
}
int main(void)
{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 0;
}

我们创建了链式二叉树的基本结构，左指针右指针以及存储的值，然后开辟空间将里面的所有内容初始化。在main函数中手动插入了1、2、3、4、5、6封装在结构体中，然后依照下图进行链接快速得到一个链式二叉树。

下面依照创建完成的链式二叉树继续学习。

二叉树的遍历

前序、中序以及后序遍历

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(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){return;}printf("%d ", root->val);PrevOrder(root->left);PrevOrder(root->right);
}

在前序遍历中，我们使用递归进行。如果root为NULL证明树为空，直接返回即可。当进入下面代码时，前序遵循的是根、左树、右树。所以我们先将根打印出来，然后遍历左树。当进入左树递归时，root->left进入左树，那根的左子节点就变成了左树的根，打印出来继续递归，依次类推。而右树也是一样的，将左树遍历完后，我们将递归右数，先将左树递归的所有函数销毁，进入root->right中进行递归，根的右子节点成为右树的根，打印出进行递归，一直遵循根、左树、右树进行。

递归图解如下：

虽然代码非常简洁，但是理解起来不太容易，我们不能只记住代码如何写，应该理解其中的原理才行。

中序遍历的实现

只要我们理解了前序遍历，那么中序后序都是非常简单的存在。只需记住：左树、根、右树，然后写出递归即可

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

有没有发现这串代码与前序遍历非常相似，只是将两行代码交换位置就可以实现。我们先将左树的内容递归完然后打印，再打印根的，最后再打印右树的即可。可以参考前置遍历进行推理。

这里如果实在理解不了的可以认为调用InOrder(root->left)是遍历打印左树，printf是打印根，而调用递归InOrder(root->right)是为了遍历打印右树。

后序遍历实现

我相信大家已经知道函数怎么写了，那我就直接给模板：

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

下面我们更进一步的学习链式二叉树的结构，上强度！！！

节点个数以及高度

总结点个数

我们需要建立一个函数，求出整个二叉树所有的节点个数。

有人一定会想直接全部遍历一遍然后创建一个全局变量用来统计个数就可以了。没错这个方法是可行的，我们刚才说的二叉树的遍历，然后在这里用一遍不就拿下来了。

int size = 0;
int TreeSize(BTNode* root)
{if (root == NULL)return 0;else++size;TreeSize(root->left);TreeSize(root->right);return size;
}

我们直接遍历整棵树，先遍历左树、再遍历右数，每遍历一个节点size++即可。

但是这个函数有一个极大的缺点，当我们使用函数时，我们可以在任意一个位置去调用，全局变量是存储在静态区的，不会随着函数的结束而销毁，当我们调用过一次后，再一次去调用此函数，如果没有及时将size归零，结果将会累加起来成为错误的结果。

我们应该优化一下程序：

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

直接使用递归，将左右子树包含在返回值中，我们在后面加上1，如果递归成功将+1，然后返回最后递归之和。

我们可以做个比喻：在一个大学中校长想要统计全校的人数，校长不可能亲自挨家挨户访问查人，它会通知每个院的院长，然后院长通知每个系的系主任，由系主任通知导员，最后由导员通知每个班的班长来统计人数。一级一级的下放任务。而这个递归也是如此，统计总节点个数就是一级一级下方给各个节点计数。

叶子节点个数

需要求出链式二叉树的叶子节点个数，叶节点或终端节点：度为0的节点称为叶节点；

大致原理都是一样的，只是条件不同。我们需要叶子节点就必须是度为0的节点，所以一个节点的root->right == NULL && root->left == NULL 这是必要条件，然后我们就应该去遍历二叉树的左子树与右子树去寻找满足条件的节点。最后求出左右子树的叶子节点之和即可。

代码实现：

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

第k层节点个数

当我们需要某一层的节点个数，我们也需要创建一个函数来进行，那我们应该怎么弄呢？

还是一级一级去派遣，假设我们需要第三层的节点个数，当我们刚进入在第一层时，我们距离目标层数还有两层之差，当我们遍历到第二层时，我们距离目标还有一层，当我们进入目标层后我们就要进行遍历节点，统计出左右子树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);
}

需要注意的是我们先得使用assert进行断言，防止树为空。

整个代码模板以及验证

下面是增章全部代码以及测试用例：

#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;struct BinaryTreeNode* right;int val;
}BTNode;BTNode* BuyNode(int x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");exit(-1);}node->val = x;node->left = NULL;node->right = NULL;return node;
}void PrevOrder(BTNode* root)
{if (root == NULL){return;}printf("%d ", root->val);PrevOrder(root->left);PrevOrder(root->right);
}void InOrder(BTNode* root)
{if (root == NULL){return;}InOrder(root->left);printf("%d ", root->val);InOrder(root->right);
}
void PostOrder(BTNode* root)
{if (root == NULL){return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->val);
}
//总节点个数
//int TreeSize(BTNode* root)
//{
//	static int size = 0;
//	if (root == NULL)
//		return 0;
//	else
//		++size;
//	TreeSize(root->left);
//	TreeSize(root->right);
//	return size;
//}
//int size = 0;
//int TreeSize(BTNode* root)
//{
//	if (root == NULL)
//		return 0;
//	else
//		++size;
//	TreeSize(root->left);
//	TreeSize(root->right);
//	return size;
//}
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->right == NULL && root->left == NULL)return 1;return TreeLeafSize(root->right) + TreeLeafSize(root->left);
}
//第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(void)
{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;PrevOrder(node1);printf("\n");InOrder(node1);printf("\n");PostOrder(node1);printf("\n%d", TreeSize(node1));printf("\n%d", TreeSize(node1));printf("\n%d", TreeLeafSize(node1));printf("\n%d", TreeKLevel(node1, 2));return 0;
}

代码运行结果如下：