树和森林与二叉树的转换

一、二叉树的性质

1. 在二叉树的第i层上至多有(2^{i-1})。

2. 深度为k的二叉树上至多含(2^k-1)。

3. 对任何一棵非空二叉树，如果它含有(n_0)个叶子结点，(n_2)个度为2的结点，那么(n_0=n_2+1)。

4. 具有n个结点的完全二叉树的深度为({log_{2}}n+1)。

5. 对有n个结点的完全二叉树编号后，则对任意一个编号为i的结点:

①若i=1，则该结点是二叉树的根，无双亲；否则，其双亲结点编号为(i/2)结点；
②若2i>n，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点；
③若2i+1>n，则该结点无右孩子结点，否则，编号为2i+1的结点为其左孩子结点；

6. 二叉树可以采用顺序存储和链式存储两种方式来实现，由于二叉树的非线性特性，大多数情况下则采用链式存储方式来实现。