什么是树

树是n(n>=0)个结点的有限集。n=0是代表是一棵空树；

非空树满足的条件(n>0)

1、有且仅有一个根节点；
2、当n>1时，其余结点又可以再分为m个有限集，并且分出来的每个有限集本身也是一棵树，称作根的子树。

树的特征

1、树是一种递归的数据结构；
2、树也是一种分层的结构；
3、除了树的根结点外，其余结点都有且仅有一个前驱结点；
4、树中的所有结点可以有零个或多个后继结点；

树的一些概念

1、度

树中一个结点的孩子结点个数的和称为度；
树中结点的最大度数称为树的度，即该树是几度树，如果树中结点的最大度数为m，则称该树为m度树；
度为m的树，指的是某棵树中最大度数为m，即其不能为空树，最少要有m+1个结点；
m叉树，指的树中不存在度大于m的树，即可以小于m甚至没有，即其可以为空树，或者退化为链表；

2、分支和叶子

度大于零则称为分支结点，度为零的则称为叶子结点；

3、高度、深度和层数

层数：是从上往下数的，即树根为第一层，以此类推；
高度：是从下往上数的，即最下面的叶子结点高度为1，以此类推；
深度：也是从上往下的一个概念；

4、森林

森林是多棵互不相交的树组成的集合，加上一个根结点可变为树，故树与森林和相互转化；

树的性质

设树的结点数为n，度为m，高度为h，树的总度树为k(总度树其实就是边的个数，因为一个度对应一条边)，则有如下性质；
1、n -1 = k（树的结点数减一等于该树的总度数），因为除根外每个结点都只有唯一一个前驱即只有一个边，于是n个结点有n个边根结点没有所以排除；
2、度为m的树中，第i层最多有m^(i-1)个结点；
3、高度为h的m叉树至多有(m^h - 1)/(m -1)个结点，计算方式就是根据2等比数列求和；
4、高度为h的度为m的树至少有h+m-1个结点；
5、有n个结点的m叉树的最小高度为[logm(n(m-1)+1)]，根据3取对数可得；

树的存储结构

双亲表示法

这种存储方式是使用顺序存储的结构，在结点中又增加了一个用于存储父结点的指针，即父结点在数组中的位置，根结点在数组中的位置为0，其父结点值设置为-1；

#define Max_Size 100
typedef struct TreeNode{
  ElemType data;
  int parentIndex;
} TreeNode;
typedef struct Tree{
  TreeNode nodes[Max_Size];
  int length;
} Tree; 

这种存储方式的优点是查询结点的双亲很方便；
缺点正好相反，查找孩子结点就比较麻烦需要遍历这个数组；

孩子表示法

这种存储方法是把顺序表和链表结合在一起的存储方法，这种存储的思想也很重要；
这种存储方式是，用数组顺序存储各个节点，每个结点中又多加一个用于存储孩子结点链表头的指针，即将各孩子在数据存储的位置用链表串起来；

typedef struct LinkNode{
  int childIndex;
  struct LinkNode *next;
}
typedef struct TreeNode{
  ElemType data;
  struct TreeNode *firstChild;
} TreeNode;
typedef struct Tree {
  TreeNode nodes[Max_Size]; 
  int length;
}

这种方式方便寻找孩子结点，但是需要父结点时需要遍历数组；

孩子兄弟表示法

这种存储方法又称为二叉树表示法，是用链表表示的存储方法；
该存储方法包含三个字段即，结点值、指向第一个孩子结点的指针(左孩子)、右指针指向兄弟结点；

typedef struct TreeNode {
  ElemType data;
  struct TreeNode *firstChild, *nextSibling;
} TreeNode, *Tree;

这种存储方法最大的优势就是，将我们不太熟悉的树结构，转化为熟悉的二叉树结构；
而且查询孩子结点是很方便的，缺点是不容易查找其父结点；