[数据结构] 树

1. 树

结点的度：结点拥有的子树的数量
树的度：树中所有结点的度数的最大值

树的性质：

• 树中的结点数等于所有结点的度数加1
• 度为m的树中第i层上至多有个结点（i>=1）
• 高度为h的m叉树至多有个结点
• 具有n个结点的m叉树的最小高度为

2. 树的存储结构

• 顺序存储结构
  双亲表示法：用一组连续的存储空间存储树的结点，同时在每个结点中，用一个变量存储该结点的双亲结点在在数组中的位置。
  孩子表示法：把每个结点的孩子结点排序起来存储成一个单链表。
  孩子兄弟表示法：顾名思义就是要存储孩子结点和兄弟结点。

3. 二叉树

（1）特殊二叉树

• 斜树
• 满二叉树
• 完全二叉树

（2）二叉树性质

• 非空二叉树上叶子结点树等于度为2的结点数加1
• 非空二叉树上第k层上至多有个结点（k>=1）
• 高度为H的二叉树至多有个结点（H>=1)
• 具有N个（N>0）结点的完全二叉树的高度为或
• 对完全二叉树按从上到下、从左到右的顺序依次编号1，2，……，N，则有以下关系：
  1）当i>1时，结点i的双亲结点编号为[i/2]，即当i为偶像时，其双亲结点的编号为i/2，它是双亲结点的左孩子；当i为奇数时，其双亲结点的编号为（i-1)/2，它是双亲结点的右孩子。
  2）当2i<=N时，结点i的左孩子编号为2i，否则无左孩子。
  3）当2i+1<=N时，结点i的右孩子编号为2i+1，否则无有孩子。

（3）存储结构

• 顺序存储
  二叉树的顺序存储结构就是用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。

• 链式存储
  二叉树每个结点最多两个孩子，所以设计二叉树的结点结构时考虑两个指针指向该结点的两个孩子。