树结构的相关概念
节点：每一个数据元素；
父节点：如图所示A是一个父节点；
子节点：如图所示BCD都是A的子节点；
兄弟节点：拥有同一个父节点的节点；
根节点：树结构中没有父节点的节点；
叶子结点：没有子节点的节点；
空树：集合本身为空的树结构，空树中没有节点；
子树：如图所示，单独看BEFKL组成的部分也是一棵树，这棵树为子树，单个节点也是一颗子树；
节点的度：一个节点拥有的子树数目为节点的度，一棵树的节点是树内各节点的度的最大值；
节点的层次：从一棵树的树根开始，树根所在层为第一层，根的孩子结点所在的层为第二层，依次类推。一棵树的深度（高度）是树中结点所在的最大的层次。图 1（A）树的深度为 4。
二叉树
本身是有序树且树中包含的各个节点的度只能是0,1,2
二叉树的性质
1.二叉树中第i层最多有个节点
2.二叉树中叶子节点数为，则度为2的节点数
，则
=
+1
推导：性质 3 的计算方法为：对于一个二叉树来说，除了度为 0 的叶子结点和度为 2 的结点，剩下的就是度为 1 的结点（设为 n1），那么总结点 n=n0+n1+n2。同时，对于每一个结点来说都是由其父结点分支表示的，假设树中分枝数为 B，那么总结点数 n=B+1。而分枝数是可以通过 n1 和 n2 表示的，即 B=n1+2n2。所以，n 用另外一种方式表示为 n=n1+2n2+1。两种方式得到的 n 值组成一个方程组，就可以得出 n0=n2+1。
二叉树分类
满二叉树：除了叶子节点，每个节点的度都为2的二叉树。具有n个节点的满二叉树的深度为(n+1)
完全二叉树：如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。
完全二叉树除了具有普通二叉树的性质，它自身也具有一些独特的性质，比如说，n 个结点的完全二叉树的深度为 ⌊log2n⌋+1。
对于任意一个完全二叉树来说，如果将含有的结点按照层次从左到右依次标号（如图 3a)），对于任意一个结点 i ，完全二叉树还有以下几个结论成立：
当 i>1 时，父亲结点为结点 [i/2] 。（i=1 时，表示的是根结点，无父亲结点）
如果 2i>n（总结点的个数） ，则结点 i 肯定没有左孩子（为叶子结点）；否则其左孩子是结点 2i 。
如果 2i+1>n ，则结点 i 肯定没有右孩子；否则右孩子是结点 2i+1
二叉树的顺序储存结构
二叉树的顺序存储，指的是使用数组存储二叉树。需要注意的是，顺序存储只适用于完全二叉树。因此，如果我们想顺序存储普通二叉树，需要提前将普通二叉树转化为完全二叉树。
完全二叉树的顺序存储，仅需从根节点开始，按照层次依次将树中节点存储到数组即可。
从顺序表中还原完全二叉树也很简单。我们知道，完全二叉树具有这样的性质，将树中节点按照层次并从左到右依次标号（1,2,3,...），若节点 i 有左右孩子，则其左孩子节点为 2i，右孩子节点为 2i+1。
http://data.biancheng.net/view/194.html
二叉树的链式储存结构
采用链式存储二叉树时，其节点结构由 3 部分构成（如图 3 所示）：
指向左孩子节点的指针（Lchild）；
节点存储的数据（data）；
指向右孩子节点的指针（Rchild）；
