链式二叉树是链式树集合中的一种，该树的每个根节点最多只有两个孩子节点，我们一般用左右孩子来称呼，在初学链式二叉树时，由于大家对链式二叉树的结构掌握还不够深入，为了降低本章的学习难度及成本，我们先手动创建一棵简易二叉树，快速进入二叉树的操作学习中，等所有基本操作大家都掌握后，我们再来了解如何创建链式二叉树。

        对于链式二叉树的结构代码如下：

        接下来是手动创建一棵简易二叉树：

        构建的二叉树结构如图;

我们先来回顾一下二叉树的概念，二叉树是：

1. 空树。

2. 非空：根结点，根结点的左子树、根结点的右子树组成的。

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

        学习二叉树结构，最简单的方式就是遍历。，所谓二叉树遍历(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); 

        前序遍历的代码很简单，但因为是通过递归来实现的，所以思维量较大，我们通过代码讲解一下：

        各位看到代码是否有眼前一亮呢，为何代码如此简单，别急，我们来通过图分析分析：

        前序遍历的要求是先遍历根节点，然后遍历左子树，最后遍历右子树。开始时，根节点的值为1，首先打印到控制台上，随后进入左子树进行遍历，左子树的根节点值为2，打印到控制台上，进入左子树进行遍历， 左子树的根节点值为3，打印到控制台上，进入左子树进行遍历，发现左子树的根节点为空，返回，进入到右子树进行遍历，发现右子树的根节点为空，返回。根节点值为3的函数已经运行结束，返回到根节点值为2的子树进行该子树的右子树遍历，根节点为空，返回。根节点为2的函数运行结束，返回到根节点值为1的二叉树中向下运行，进入右子树遍历，右子树根节点的值为4，打印到控制台上，进入左子树遍历，左子树的根节点值为5，打印到控制台上，进入左子树进行遍历， 左子树的根节点为空，返回，进入右子树遍历，右子树的根节点为空，返回。根节点值为5的函数运行结束，返回到根节点为4的函数中继续向下执行，进入右子树遍历，右子树根节点为6，打印到控制台上，进入左子树遍历，左子树的根节点为空，返回，进入右子树遍历，右子树的根节点为空，返回。根节点为6的函数执行结束，返回，根节点为4的函数执行结束，返回，根节点为1的函数执行结束，返回，函数结束。当然，之前节点为空的再返回之前会打印N字符表示该节点为空。

        聊到这里，我们不妨来了解一下递归函数中栈帧的创建和销毁过程，函数栈帧创建时需要内存提供空间存放栈帧，且存放是由高地址向低地址存放，由esp和ebp来记录函数栈帧两端的地址。通过不同的指令对寄存器进行操作，从而完成了函数栈帧的创建和销毁。

        具体细节各位可以看本篇文章：函数栈帧的创建和销毁（编程底层原理）-CSDN博客

        在这里我想要强调的是，每一个函数栈帧的开辟都需要开辟相应的空间，而函数递归是一种减少代码量，增加思维量和计算机指令的方式，如果递归层数过大可能会导致栈溢出(Stack Overflow)等问题，因此我们在后续解决递归问题时应尽可能的减少递归层次以避免该问题。

        还有一点各位要了解：我们调用的函数栈帧销毁是会将那块空间返还给内存，当进行下一次调用时，我们使用的空间是即是刚销毁的那块空间，也就是说，函数栈帧开辟销毁的空间是可以重复利用的。

void InOrder(BTNode* root);

        代码如下：

        中序遍历的要求为先遍历左子树，然后遍历根节点，最后遍历右子树。

         通过前序遍历，我想各位已经对递归函数的过程有了一定的了解，我希望各位可以了解前序遍历的过程后，独立去画一下中序遍历的过程，来加深印象和理解。

void PostOrder(BTNode* root)；

        代码如下： 

        后序遍历的要求为先遍历左子树，然后遍历右子树，最后遍历根节点。开始时，根节点的值为1，进入到左子树遍历，左子树根节点的值为2，进入到左子树遍历，左子树的根节点值为3，进入到左子树遍历，根节点为NULL，打印N返回，进入到右子树遍历，根节点为NULL，打印N返回，随后打印值为3的根节点，返回上层函数，进入右子树，为空返回，打印2，返回到根节点为1的函数，进入右子树，根节点为4，进入左子树，根节点为5，进入左子树，为空返回，进入右子树为空返回，打印5，返回到根节点为4的函数，进入右子树，根节点为6，进入左子树，为空返回，进入右子树，为空返回，打印6返回，打印4返回，打印1，结束。

        这样我们的三种遍历方式就结束了，接下来我们先看四个基本操作：

// 二叉树结点个数 int BinaryTreeSize(BTNode* root); // 二叉树叶子结点个数 int BinaryTreeLeafSize(BTNode* root); // 二叉树第k层结点个数 int BinaryTreeLevelKSize(BTNode* root, int k); // 二叉树查找值为x的结点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

        这道题的思路有很多种，我们来一 一对比这几种方法的优劣：

        法一：全局变量 / (static 局部变量)法

        这两种方法比较相似，我们一起看：

        这两种方式都存在一个很大的弊端，如果我们通过printf多次调用本函数，会发现节点的个数会成倍增加，只有第一次调用函数的结果是对的，因此我不建议各位使用法一去解决此类问题。

        法二： 传参计算法：        

        法二解决了法一中的问题，但是代价为法二多传了一个指针变量，并且，我们需要再调用函数之前将变量赋值为0。这样代码依旧略显冗余，因此就有了法三。

        法三：

        思路为当根节点为空时，返回0。根节点非空就返回根节点(1) + 左子树中的节点数 + 右子树中的节点数，在进行多次递归之后，我们就能得到节点的个数。代码如下： 

        这个操作与上面类似，只是之前是根节点存在加1，现在改成了，根节点存在且根节点不存在子树时加1。代码如下：

        我们要将操作分为三个过程。

1.根节点为空时，返回0。

2.根节点不为空，如果k为1，直接返回1。

3.根节点不为空，如果k>1，返回该二叉树的左子树第k-1层的节点个数与右子树第k-1层的节点个数。

代码如下： 

        这个操作在细节上非常容易出问题，我们将操作分为四步：

1. 根节点为空，返回NULL。

2. 根节点不为空，且根节点的值等于要查找的值，返回根节点。

3. 如果上方条件不成立，进入左子树寻找x节点，若找到，返回；没找到进入右子树寻找。

4. 遍历二叉树后，没有找到，返回NULL。

        这里要注意的是，很多人不明白为什么要用指针变量去接收函数的返回值之后再返回，因为我们在开始第三步后，如果找到了想要的节点，就会返回，而如果没有变量接收该节点继续返回上一层函数，就会继续往下执行操作，最终可能返回的依旧是NULL，因此接收返回值的操作至关重要，不仅能在找到节点后迅速返回，还避免了多层嵌套可能导致的栈溢出风险。

代码如下： 

        下面我们来看一些题目巩固一下所学的知识：

        如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时，才返回 true；否则返回 false。

提示：

解：

        既然要判断是否是单值二叉树，那根节点的值就必然要与它的子节点的值相同，因为我们知道a==b，b==c，则a==c的道理，我们就可以通过递归继续向下比较根与子节点的值，如果不相等就返回false，直到子树的根节点为空，返回true。又因为是整棵树的值都相等是才算单值，因此我们判断左右子树时用到的是&&符号。代码如下：

         给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

 提示：

        给你一个二叉树的根节点 root ， 检查它是否轴对称。

提示：

        给你二叉树的根节点 root ，返回它节点值的前序遍历。 

解：

        因为前、中、后序遍历代码基本一致，这里只讲前序遍历的一道例题。

        题目给出的原函数是preorderTraversal(struct TreeNode* root, int* returnSize)，函数给了一个returnsize用于记录返回数组的长度，我们解题的第一想法通常是，遍历一个节点，++一下returnsize，这样没问题，但是有一种更好的方法，就是在创建数组之前我们遍历一遍树的根节点数，然后在开辟数组空间时就会减少不必要的空间消耗。正好也用到了我们之前的基本操作TreeSize函数，然后通过前序遍历将所有节点的val值放入数组，最后返回数组就可以了。

        这里要注意的一点是我们在给preOrder传参时，i一定要传地址，因为在递归函数中，形参的改变不会影响实参，会影响遍历过程。

        给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

        二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

 提示：

        在了解了链式二叉树的一些基本操作和经典OJ题目后，我想各位已经对二叉树有了一定的感觉，下面我们就来看看如何通过数组中存放的数据来创建链式二叉树。我们通过一道题目来给搭建演示：

        编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入描述：

        输入包括1行字符串，长度不超过100。

输出描述：

        可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。

解：

         既然要接收一行字符串，自然要先创建数组。通过scanf接收后，进行前序二叉树的创建，我在创建二叉树函数中传入了一个数组首地址和一个变量的地址，分别用于接收数组和变量 i(作为数组元素的下标使用)，进入函数后，首先判断数组当前下标的元素是否为空(#)，为空的话就++下标并返回，不为空就继续向下执行，申请节点，根节点赋值，递归创建左子树，递归创建右子树，这都是之前见过的，这里不在多说，最后返回根节点。创建好之后，进入中序遍历函数，这里前面有。最后打印节点，结束。

        在讲解之前我们需要进行一些队列代码的处理，因为之前我们队列中存储的值是int类型的，但是我们在树中的存放的节点是以链表的形式，因此在不破坏结构为前提下，我们需要将之前定义的QDataType转换为struct BinaryTreeNode*的指针类型，并把队列的头文件包含过去，这样我们就可以进行后续操作了。

        在前面将前、中、后序遍历的时候，我们采用的是递归遍历树节点的方式完成的。但是层序遍历有所不同，我们不能再顺着根节点去遍历，而是遍历完一层之后，才能去遍历下一层节点即广度优先算法。因此我们需要用到队列的功能，首先将根节点入队列，将根节点的值赋值给front之后删除队列中的节点，打印front的值，如果根节点的左孩子存在，入队列，如果根节点的有孩子存在，也入队列，继续上述操作，我们就能将所有的节点按，层序遍历的方式打印出来。代码如下：

        判断是否为完全二叉树的思路本质上和层序遍历是一样的，区别在于层序遍历找到空节点是跳过(不入队列)的，但是在判断完全二叉树时，我们要讲空节点也入队列，这是我们判断的关键条件，将根节点入队列，接着出队列时带入根节点的两个子节点，当出队列的根节点为空时，跳出循环。进入下一步，遍历队列中剩余的节点，如果都为空节点，说明是完全二叉树，如果存在非空节点，说明不是完全二叉树。

        对于其中的一些常见疑问，大家可以画图去了解，我在这里讲一个常见问题：如果遇到空节点时，还有非空节点没有入队列怎么办，这个担心是对的，但是我们一画图就能看出，这种情况的担心是多余的。

        我们从上图中可以看出，遇到第一个空节点时，即便是最下面的节点也入队列了，所以是完全可以判断的。可能大家还会想到一种情况：

        如果树节点是这样的那最后这个不就入不了队列吗，没错，但是这个节点入不入队列都是无所谓的，因为它的双亲节点能够入队列就已经证明了这棵树是否为完全二叉树，因此我们可以把它忽略不计。 

        二叉树的销毁比较简单，通过后序遍历释放根节点即可完成。代码如下：

         到此，我们的二叉树的学习就要告一段落了，但是二叉树的内容远不止于此，我们会在之后带大家走入更深层次的二叉树学习，如：AVL树、平衡搜索树、红黑树以及B树系列，敬请期待，我们下期见。