基本概念

树

定义

  树是n个结点的有限集合，n = 0 时，称为空树。在任意空树中应满足：

1. 有且仅有一个特定的称为根的结点

2. 当 n > 1时，其余结点可分为 m 个互不相交的有限集合，其中每个集合本身又是一棵树，并且成为根节点的子树。

   树的定义是递归的，也是一种递归的数据结构。有两个特点：

   1. 树的根节点没有前驱结点，除根节点外的所有结点有且只有一个前驱结点

   2. 树中所有结点可以有零的或多个后继结点

  树适合表示具有层次结构的数据。数中的某个结点最多只和上一层的一个结点有直接关系，根结点没有直接上层结点，所有在n个结点的书中有 n - 1 条边。

基本术语

  这里要注意的主要是：

  1）祖先结点 对应 子孙结点； 双亲结点 对应 孩子结点； 具有相同双亲的结点称为 兄弟结点。

  2）树中一个结点的子结点个数称为结点的度；树中结点的最大度数称为树的度。

  3）度大于0 的称为 分支结点；度为 0 的结点称为 叶子结点；

  4）结点的深度、高度和层次

    结点的层次：从根结点开始定义的，根结点第一层，一直往下推

    结点的深度：从根结点开始自顶向下逐层相加

    结点的高度：从叶结点开始自底向上逐层相加

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

  5）有序树，无序树

    有序树：树中结点的子树从左到右是有次序的，不能交换

  6）路径和路径长度

    树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。兄弟结点之间不存在路径。

  7）森林： 森林是由m棵互不相交的集合。

树的性质

  1、树中的结点数等于所有结点的度数加1

  2、度为 m 的树中第 i 层 上至多有 mi-1 结点

  3、高度为 h 的 m 叉树 至多有（mh - 1）/ ( m - 1 )个结点

  4、具有 n 个 结点的m叉树的最小高度为[logm(n(m-1) + 1)]

二叉树

定义

  二叉树的特点就是每个节点至多只有两颗子树，并且二叉树的子树有左右之分，其次序不能任意颠倒。

  五种基本形态：

  二叉树与度为2的有序树的区别：

  1）度为2的树至少有三个结点，而二叉树可以为空

  2）度为2的有序树的孩子结点左右次序是相对的，但是二叉树的结点次序是确定的。

特殊的二叉树

  1、满二叉树：一棵树高度为h，且含有2h - 1 个结点的二叉树称为 满二叉树。就是说满二叉树中的所有结点（除叶子结点）都含有两个子结点，也就是度为2。若对满二叉树从根结点编号，自上而下，自左向右，那么对于编号为 i 的结点，若有双亲，则其双亲为 i / 2 (向下取整)，若有左孩子，则左孩子为 2i , 若有右孩子，则右孩子为 2i + 1。

  2、完全二叉树：设一个高度为h，有n个结点的二叉树，当且仅当每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树。

完全二叉树的特点：

1、若 i <= n/2(向下取整)，则结点i为分支结点，否则为叶子结点。

2、叶子结点只可能在层次最大的两层上出现。对于最大层次中的叶子结点，都一次排列在该层最左边的位置上。

3、若有度为1的结点，则只可能只有一个，且该结点只有左孩子而无右孩子（重要特征）。

4、按层编号后，一旦出现某结点（编号为i）为叶子结点或只有左孩子，则编号大于i的结点均为叶子结点。

5、若n为奇数，则每个分支结点都有左右孩子；若为偶数，则编号最大的分支结点只有左孩子，没有右孩子。

  3、二叉排序树：二叉树或者是空二叉树，左子树上面的关键字都小于根节点的关键字；右子树上面的关键字都大于根节点的关键字。左子树和右子树又各是一棵二叉排序树。

  4、平衡二叉树：树上的任一结点的左子树和右子树的深度之差不超过 1。

二叉树的性质

  1）非空二叉树上的叶子结点数等于度为2的结点数加 1，即 n0 = n2 + 1。

  2）非空二叉树第k层上至多有 2k-1个结点（k >= 1）

  3）高度为 h 的二叉树 至多有 2h - 1 个结点

  4）结点 i 所在层次 为 log2i(向下取整) + 1

  5）具有n个结点的完全二叉树的高度为 log2n(向下取整) + 1 或 log2(n+1) (向上取整)。

二叉树的存储结构

  1、顺序存储结构

  二叉树的顺序存储结构是指用一组地址连续的存储但愿此意自上而下，自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在某个数组下标为 i - 1 的分量中，然后通过一些方法确定结点在逻辑上的父子和兄弟关系。

  完全二叉树和满二叉树采用顺序存储比较合适，但是对于一般的二叉树，为了数组下标能够反映二叉树中结点之间的逻辑关系，只能添加并不存在的空结点，让每个结点与完全二叉树上的结点相对照，再存储到一对数组的相应分量上中。然而，在最坏情况下，一个高度为h 且只有 h个结点的单支树却需要占据近2h - 1 个存储单元，称为树的退化。

  2、链式存储结构

  由于顺序存储空间利用率低，因此二叉树一般采用链式存储结构。链式存储结构是指用一个链表来存储一棵二叉树，二叉树中的每个结点用链表的一个结点来存储。二叉链表至少含有 3 个域：数据域data，左指针域lchild，右指针域rchild。

  二叉树的链式存储结构：

typedef struct BitNode{
    ElemType data;
    struct BitNode *lchild, *rchild;
}BitNode,*BitTree;