链式二叉树，递归的暴力美学

目录

 1.链式二叉树概念

2.链式二叉树的实现

3.先序遍历

4.中序遍历

5.后序遍历

6.求链式二叉树的结点个数

7.链式二叉树的叶子结点个数

8.求二叉树的k层的结点个数

9.链式二叉树求深度

10.求值为x的结点

11.链式二叉树的销毁

12.二叉树的层序遍历

13.判断二叉树是否为完全二叉树

---

 1.链式二叉树概念

链式二叉树和名字一样，是使用链式结构实现的二叉树，结点之间使用指针连接起来的。之前的二叉树是使用顺序结构进行存储的，不同于顺序存储，链式结构可以将各结点之间的关系表示清晰。

2.链式二叉树的实现

二叉树，首先肯定要有根节点的，然后是左右两个孩子结点，分别叫做left和right即可，通过一个结构体来实现链式二叉树。

 如图所示，一个链式二叉树的结点就是实现好了。

我们要自己手动将结点连接起来，这就实现了一个完全二叉树。

3.先序遍历

简单的几行代码就实现好了，这就是递归的魅力所在。

接下来分析一下，

递归是一定要有终止条件的，如果没有终止条件的话递归就会陷入死循环，并且占用的大量的函数栈帧，先序遍历的终止条件就是根节点为NULL，此时就结束递归，不会进入到后面的步骤，如果这个根结点不是空指针，那就打印这个结点的data，然后进入左子树进行先序遍历，如果左子树的根节点不是空指针，那就打印左子树的根结点的值，然后继续进入左子树的左子树，一直走到左子树为空，然后此时就遍历右子树，进而就实现了链式二叉树的先序遍历。

4.中序遍历

过程同先序遍历一样，只是打印的结点不同，这里不过多讲解。

5.后序遍历

同上。

6.求链式二叉树的结点个数

同样，这里也是用到了递归的思想，仅仅需要简单的几行代码，就实现了结点的计算。

终止条件还是root==NULL，根结点是空结点之后，说明此时就已经走到了一个结点的空指针的位置，没有必要计算的，直接返回0即可，下面的return1+是为了算上开始的结点，需要+1，然后就加上这个结点的左子树和右子树就实现了递归来求的链式二叉树的结点个数。

7.链式二叉树的叶子结点个数

叶子结点就是有一个父节点，然后他的左结点是空指针，他的又结点也是空指针，那这个结点就是叶子结点，要求的叶子结点个数也是通过递归实现的。

终止条件是有两个的一个是root==NULL,另一个就是左右结点都是空指针。

分析一下这两个终止条件，root==NULL,这个结点已经是空指针了没有加上去的意义，那肯定会有人有疑问了，根结点的左右结点是空指针了，怎么会向下递归呢，那就大错特错了，如果一个结点只有一个子结点的话，两个结点都进入，空结点返回0，非空返回1，这是其中一个终止条件的意义，另一个就很明显了，就是左右结点是空就返回1，没有什么过多需要解释的，如果这个结点不符合上述两个终止条件的话，就返回他的左子树+他的右子树。

8.求二叉树的k层的结点个数

k是层数，第一个终止条件就不用说了，重点是k==1时，返回1，k不等于1就返回左子树的k-1加上右子树的k-1,比如第二层，我们传入k=2，不会终止，然后进入左子树，左子树的k=1，右子树的k也等于1，加起来就是2.

9.链式二叉树求深度

求深度肯定不可能只求一边的深度就返回，要进行比较的，所以将左子树和右子树进行比较才能返回。

10.求值为x的结点

如果root的data等于x，就直接返回这个data的地址了，不等于的就看左子树，寻找左子树是否有等于这个值的结点，然后判断，如果不是空指针那一定是找到了，直接返回地址，右子树同理。

11.链式二叉树的销毁

需要修改指针的值，那就要取出指针的地址，下面的同样是递归，不过多讲述。

12.二叉树的层序遍历

需要进行层序遍历，这里需要借助队列来实现了，首先肯定是要创建一个队列的，然后队列进行初始化，写一个循环，只要队列不为空，就一直入队列，队列是先入先出的特点，入队列之后直接打印，然后队列删除队头，然后左子树右子树入队列接着打印，一直到队列为空，此时就实现了队列的层序遍历。

13.判断二叉树是否为完全二叉树

还需借助队列来完场，创建队列，将root入队，获取队列队头，然后队头删除，然后就一直入队，如果此时队头是空指针就直接跳出循环了，因为已经是空指针了，肯定没办法获取他的左右孩子。那么就进入下一个循环，循环条件是队列非空，因为如果是二叉树，在取完最后一个结点之后，队列中剩下的都是空结点，如果不是完全二叉树的话，里面就会剩下非空的，一直取到队列为空，如果取到了非空就直接返回false，一直走完循环结束，到最后没有找到，那就直接返回true,说明这是一个完全二叉树。