数据结构——链式二叉树(C语言版)

链式二叉树的结构

创建链式二叉树

        由于普通的二叉树并没有插入删除的意义，所以在创建二叉树时只需要手动创建二叉树就行，因为普通二叉树没有条件限制比如：

所以在普通二叉树里并没有增删的意义，创建时只需要手动创建即可。

        创建二叉树的第一步：先写一个创建单个节点的函数，并将节点里左右指针都初始化为NULL，这样也方便后续链接操作。 第二步：手动申请7个节点，并将将节点之间进行链接。最终形成以下的逻辑图片。

链式二叉树的遍历

        前序遍历：

        中序遍历：

        后序遍历：

        层序遍历：

链式二叉树的简单算法题

        求二叉树所有节点个数：

                                                左子树展开图

                                        右子树展开图

从上图的左右子树展开图图可以看出，求节点根数需要分别递归计算根的左子树与右子树，当递归到NULL时返回0，当左右子树递归完后需要再加上1(自身),再进行返回。最终计算出该子树节点数量为7。

        求二叉树叶子节点的个数：

                                        递归展开图

        因为叶子节点的特点是左右子树都为NULL，利用这一特性，当递到根的左右子树都为NULL，就返回1表示这个节点是叶子节点。如果左节点或又节点其中一个是NULL并不会返回1，而是继续递归。当递归到叶子节点时直接返回一。最终得得出根的左子树节点数与根的右子树节点数。

        求二叉树第k层的节点个数：

                                               

                                                        递归展开图

        由上图的展开图可以看出，假设k==3，分别递归根的左子树与右子树的第k层，每一次递归的时候都让k-1，当k==1的时候就说明已经到了第k层直接返回1，当递归到第k-1层的时，只需要判断k-1层的左节点与右节点，如果为NULL就返回0，最后将k层返回的数字进行相加并return就得到第k层节点数。

        求二叉树的深度：

                                        左子树深度展开图

                                右子树深度展开图        

        想要计算二叉树的深度，就要计算根的左子树与右子树的深度，将左子树的深度与右子树的深度进行比较，并返回较大值，如上图，通过递归展开，会得知左子树的深度为3，右子树的深度为2，最终返回左子树的深度+1，所以上图二叉树的深度为4。

        二叉树查找值为x的节点：

                                递归展开图

        由上图可见，当需要找x节点时，一开始会先判断根节点是否符合条件，如果符合条件直接返回，如果不符合就先递归根的左子树，当左子树递归完后发现并没有找到值会返回NULL，此时指针为NULL，会递归根的右子树，当发现有节点符合值的时候会直接返回并给指针赋值，防止继续递归。