二叉树转换成一般树（树二叉树满二叉树）

自由树

自由树是一个连通的，无回路的无向图。

令G=(V，E)为一个无向图。下面的表述是等价的。

1) G是自由树。

2) G中任意两个顶点由唯一一条简单路径得到。

3) G是连通的，但从E中去掉任何边后得到的图都是非连通的。

4) G是无回路的，且|E|=|V|-1。

5) G是连通的，且|E|=|V|-1。

6) G是无回路的，但添加任何边到E中得到的图包含回路。

二叉树

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

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。

二叉树的第i层至多有2^(i-1)个结点；

深度为k的二叉树至多有2^k-1个结点；（等比数列1 2 4 … 2^(k-1) = 2^k-1）。

对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 1。

所有内部节点都有两个子节点，最底一层是叶子节点。

性质：

1) 如果一颗树深度为h，最大层数为k，且深度与最大层数相同，即k=h;

2) 它的叶子数是： 2^(h-1)

3) 第k层的结点数是： 2^(k-1)

4) 总结点数是： 2^k-1 (2的k次方减一)

5) 总节点数一定是奇数。

6) 树高：h=log2(n 1)。

完全二叉树

完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h 层所有的结点都连续集中在最左边，这就是完全二叉树。

（大家好好理解一下上面两个定义，是等价的~~）

满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

下面是完全二叉树的基本形态：

完全二叉树的性质：

1) 深度为k的完全二叉树，至少有2^(k-1)个节点，至多有2^k-1个节点。

2) 树高h=log2n 1。

对满二叉树、完全二叉树总结点及树高的总结：