数据结构（七）

这是数据结构的第7篇文章

ok，那么我们来继续看看Tree。

上次讲到长子+兄弟节点表示法能够优化Tree的结构。

那我们这次来讲讲比较常用的二叉树。

什么是二叉树

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

一棵深度为k，且有2^k-1个节点的二叉树，称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。具有n个节点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树，至少有2的（k-1）次方个节点，至多有2的k次方-1个节点。

——百度百科

上图讲的就是比较极端的情况。一个是成为了一条链，另外一个是成为了满树。

满树如下图：

真二叉树

我们看上图，对于左边的树来说，把每一个节点的孩子节点数记下，贼会出现有0、1、2的取值情况，然而这对我们往后的操作造成繁琐。

因此我们考虑能不能假象添加上任意多个节点，使得每个节点的度要么取值为0，要么取值为2。这就是真二叉树。

这些假想出来的节点，并不影响后续的操作。

描述多叉树

二叉树的好处就是可以描述多叉树。

你可能会问：特例怎么能够描述普遍呢？

当然，这里并非没有任何限制条件的。有两条很重要的条件：1、有根 2、有序。

怎么做到？对的，就是用之前所讲的长子+兄弟表示法。

BinNode类

每一个BinNode节点需要有一个数据域+左孩子+右孩子。

这里也包含了动态操作如左孩子插入和右孩子插入。也包含了对子树的前序中序后序遍历。

inserAsRc / inserAsLc接口：显而易见，首先通过BinNode节点的构造方法，生成一个新的BinNode，并将他的parent引用指向上一个节点，并且完成自下而上的节点，这个思路在左子树和右子树均可使用。

size接口：统计后代的总数，也就是子树的规模。我们使用递归来完成。一般来说需要O（n）线性的时间。

updateHight方法：对于树的高度更新。高度：从根节点到叶子节点的最长的那条路径。其中有两种树值得我们关注：1、当只有一个节点时，树的高度为0， 2、当树为空树时，树的高度为-1。因此我们可以看到第一行，直接定义好空树的高度为-1。

那么对于更新树的高度而言，可以使用递归的方法，分别递归左右子树，从而返回树的高度，达到更新的效果。

Insert方法：可以调用节点中的insert接口，直接作为插入，要记得重新更新一下高度。

遍历

遍历：按照某种次序访问树中的各个节点，每个节点恰好访问一次。

一般来说，对于一个树的节点而言，他们的基本结构具有：根节点，左子树，右子树。而所谓先序遍历，中序遍历，后序遍历，他们的先、中、后的区别在于根节点位置。

先序遍历：根——左子树——右子树

中序遍历：左子树——根——右子树

后序遍历：左子树——右子树——根

递归实现

直接使用递归即可完成遍历，因为对每个节点来说都可以看成一棵以其为根节点的树。然后层层递归，直到叶子节点。