分类： DataStruct

使用模版类实现栈模型的顺序存储需要用到我们之前写好的线性表顺序存储的模版，压栈、出栈、获取栈顶元素、获取栈大小等功能均是使用内部线性表顺序储存的函数实现的。没有什么技术含量，只是将线性表包装了一次。具体代码如下：

同上一篇文章，我们一样是把以前使用C语言实现的单向链表用模版实现了一次，进一步让我们对模版和C++的封装特性有了了解。对于链表的操作我们不过多介绍了，如果有还不清楚操作的，请看以前介绍链表的文章。

使用模版类来实现线性表的顺序储存将会变的非常简单，我们不必像使用C语言一样，将数据和算法分离时使用非常繁琐的类型转换了，而我们直接使用模版中的typename就可以解决这个问题。具体实现的代码如下，都有详细的标注和测试代码：

前面我们记录下来的文章都是手动创建的树，我们还从未尝试过将一组数据动态的在内存中构建成为一棵树。本文将详细介绍使用#号创建法动态的在内存中创建树的详细步骤。当然动态创建树并非就这么一种办法，我们记录的是最常用而且是最方便的方法。

二叉树的高度就是从根节点到最深的叶子节点之间的节点数，计算方法使用递归时，判断如果到了树的叶子节点那么就返回0。依次遍历左侧和右侧节点的数量，然后求出最大值再算上当前根节点的数量+1，递归循环返回后得出最终的结果。代码如下：

二叉树拷贝也相对简单，我们只需要在遍历的过程中，将每一个有效的节点依次给传递进来的新树的节点衔接起来就可以了。大致的思路我们可以总结一下。

这个题目作为一个小练习，让我们对树的概念进一步的掌握，其实思路非常简单，在遍历树的过程中，计算某个节点如果leftChile和rightChild都指向NULL，那么证明其就是一个叶子节点，我们对引用计数加一就可以了。具体代码如下：

树的遍历分很多种，经过前人总结，树的遍历其实一共就有三种方法，一种为先序遍历、一种为中序遍历、最后一种为后续遍历。他们不同的区别就是在遍历过程中查找树的根、左节点、右节点的顺序，同样由于遍历树惯用递归的方式，所以所谓的查找顺序不同就是在递归过程中打印节点数据时的代码位置不同而已，如果这句话你看的比较绕，那么在后面的代码中你将会恍然大悟。不过再看代码之前，你还是要记住下面的顺序。

二叉树细分了两种类型的二叉树，一种叫做“满二叉树”，就是每一层都挂满了节点，没有空位。另一种叫做“完全二叉树”，完全二叉树假设有n层，那么n-1层和满二叉树是一样的，但是第n层最后一个节点前边都挂满了节点。这是它们两个概念的唯一具体区别。表示图如下：

【满二叉树】

【完全二叉树】

上面的树符合最后一个节点（F节点）前都挂满了节点的规则，所以它属于一个完全二叉树。下面重点来了，二叉树具有5大性质，如下介绍。

【二叉树的五大性质】

• 性质1: 在二叉树的第i层上至多有2^i-1个结点（i>0）。
  比如第3层，那么就是 2^3-1 = 4，第3层最多有4个节点

• 性质2: 深度为k的二叉树至多有2^k-1个结点（k>0）。
  比如第3层，最多有 2³ -1 = 7 个节点

• 性质3: 对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n2＋1 （即n0=n2+1）
  度为2的节点有3个（A B C），那么 n2 = 3
  叶子数 = n2 + 1，那么就是 3 + 1 = 4 个

• 性质4: 具有n个结点的完全二叉树的深度必为log₂n(向下取整)＋1
  log₂n + 1 转换为公式是
  2x = n，此时 n 为 7 ，所以 x 约等于 2.几次方，向下取整后得 2
  深度 = x + 1，2 + 1 = 3，所以深度结果就是3

• 性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）。
  如下图：编号为3的节点是C，其左子节点的编号是2*3=6就是F，右子节点的编号是2*3+1=7就是G，双亲的编号是 3/2=1就是A

最后我们做一下总结，讲了这么多，无非我们就是希望引出二叉树是有规则的，我们将二叉树存入一个数组后，是可以恢复回来的，不像多叉树那样无法恢复。根据第五条的性质，我们很轻松就可以在一个存放在数组中的二叉树数据恢复为一个二叉树模型。

而如果是一个非满二叉树怎么办呢？我们如何把非满二叉树存放到一个数组里面呢？其实思路非常简单，我们只需把哪些缺少一个子节点的节点给他填充一个空就可以了。如下图：

在搞清楚多叉树转换为二叉树之前，我们有必要想清楚，为什么要这样转换？多叉树哪里有缺点需要我们转换为二叉树使用？我们来考虑一个问题：“如果我们将一个多叉树存放在一个数组中，然后删除了整个多叉树。我们能否通过这个仅有的数组恢复原来的多叉树呢？”