树
一些概念
结点拥有的子树数称为结点的度（degree）
度为0的结点称为叶节点（Leaf）或终端结点。
度不为0的结点称为分支结点或非终端结点，除根结点外，分支结点也称为内部结点。
结点的子树的根称为结点的孩子，相应的，该结点称为孩子的双亲，同一双亲的孩子之间互称为兄弟（Silbling）
结点的祖先是从根到该结点所经分支上的所有结点。
图中，A是B和C的双亲，B和C是兄弟。
结点的层次从根开始定，根为第一层，根的孩子为第二层。其双亲在同一层的结点互为堂兄弟。
树中结点的最大层次称为树的深度（depth）或高度。下图深度为3
有序树：树中结点的各子树看成从左至右是有次序的，不能互换的。否则称为无序树
**森林（forest）**是m（m>=0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。
树的存储结构
双亲表示法
以双亲作为索引的关键词的一种存储方式。
一组连续空间存储树的结点，同时在每个节点中附设一个指示其双亲结点在数组中位置的元素。
#define MAX_TREE_SIZE 100
typedef int ElemType;
typedef struct PTNode
{
ElemType data;
int parent;
}PTNode;
typedef struct
{
PTNode node[MAX_TREE_SIZE];
int r; //根的位置
int n; //结点的数目
}PTree;
一共11个结点，采用前序遍历的方法。看A没有父母-1。B的父母是0。E的父母是B，所以是1（指向B）。
优点：可以根据某结点的parent指针找到双亲结点，时间复杂度为O(1)。索引到-1时，表示找到了树节点的根。
缺点：如果是想找某结点的孩子，则需要遍历整个树结构。
改进：
孩子表示法
树中每个结点可能有多棵子树，考虑用多重链表来实现。
方案一：
根据树的度，声明足够的空间存放子树指针的结点。
缺点：造成了浪费
方案二：
在后面加一个数据，表示需要多少个指针
缺点：克服了浪费，但每个结点的度不同，初始化和维护起来难度很大。
方案三：
数组+链表的结合。ABCDE前面的数据代表数组的下标0，1，2，3等。然后A之后的指针代表自己的孩子，有123，分别代表BCD。
双亲孩子表示法
每个数据后面多了一个元素，代表自己的双亲。
#define MAX_TREE_SIZE 100
typedef char Elemtype;
typedef struct CTNode
{
int child ; //孩子结点的下标
struct CTNode *next;// 指向下一个孩子结点的指针
}*ChildPtr;
//表头结构
typedef struct
{
Elemtype data; //存放在树中结点的数据
int parent; //存放双亲的下标
ChildPtr firstchild; //指向第一个孩子的指针
}CTBox;
//树结构
typedef struct Tree
{
CTBox nodes[MAX_TREE_SIZE];
int r,n;
}