树的基本概念

父结点、子结点： 

兄弟结点： 具有同一父结点的结点

结点的度： 一个结点包含子树的数量

树的度： 该树所有结点中最大的度

叶结点： 树中度为0的结点

分支结点： 树中度不为0的结点

结点的层数： 根结点第一层，依次向下

树的深度： 树中结点的最大层数

有序树： 树中各结点的子树是按照一定次序从左到右排列的

无序树： 非有序树

森林（forest）： n 颗互不相交的树的集合

层次括号法：

    根结点放在一对圆括号中；

    根结点的子树由左到右的顺序放入括号中；

    子树处理同上。

（A(B(E)),C(F(G)),D(H,I)）

任意的树都可以转换成对应的二叉树。转换规则： 将结点的孩子放在左子树，结点的兄弟放在右子树

满二叉树： 在二叉树中除最下层的叶结点外，每层的结点都有两个子结点。

完全二叉树： 二叉树中除最后一层外，其它各层的节点数都达到最大个数，且最后一层叶结点按照从左到右的顺序连续存在，只缺最后一层右侧若干结点。

完全二叉树的性质：

   若树中包含n个结点，假设这些结点按照顺序方式存储，那么对于任意一个结点m来说

    ① 如果m!=1，则m的父结点编号为m/2

    ② 如果2*m<=n，则结点m的左子树根结点的编号为2*m。反之，则无左子树，也无右子树

    ③ 如果2*m+1<=n，则结点m的左子树根结点的编号为2*m+1。反之，则无右子树

顺序存储方式一般只适用于完全二叉树的情况，对于其他情况，一般采用链式存储方式