树

一对多的树型结构，有且只有一个特定的根结点。

结点的度：结点拥有子树的数量{

                                       度为0：叶子结点/终端结点。

                                       度不为0：非终端结点/分支结点（除去根结点其它称为内部结点）。}

树的度：树中所有结点的度数的最大值。

树的层次：根为第一层，以此类推。

结点的深度：根结点开始，自顶向下累加。

结点的高度：叶结点开始，自底向上累加。

树的高度（深度）：树中结点的最大层数。

 

结点关系：

祖先结点：根结点到该点的唯一路径上的任意结点。

子孙结点

双亲结点：根结点到该点的唯一路径上的最近结点。

孩子结点

兄弟结点：有相同双亲结点的结点。

 

树中的数学关系：

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

2.度为m的树中第i层上最多有m^i-1个结点。

3.高度为h的m叉树至多有（mⁿ-1）/（m-1）个结点。

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

 

树的存储结构

顺序存储结构

双亲表示法：用一组连续的存储空间存储树的结点，同时在每个结点中，用一个变量存储该结点双亲结点在数组中的位置。typedef char ElemType;

typedef struct TNode{
     ElemType data;  //结点数据
     int parent;     //该结点双亲在数组的下标
}TNode;              //结点数据类型

#define MaxSize 100
typedef struct{
     TNode nodes[MaxSize];//结点数组
     int n;//结点数量
}Tree;     //树的双亲表示结构

 

链式存储结构

孩子表示法：把每个结点的孩子结点排列起来存储成1个单链表，所以n个结点有n个链表；

                      叶子结点链表为空；

                      n个单链表的头指针又存储在一个顺序表（数组）中。

孩子链表结点代码：

typedef char ElemType;
typedef struct CNode{
   int child;         //该孩子在表头的数组下标
   struct CNode *next;//指向该结点的下一个孩子结点
}CNode,*child         //孩子结点数据类型

每个孩子链表的表头结点（存在数组中）：

typedef struct{
    ElemType data;    //结点数据域
    child first child;//指向该结点的第一个孩子结点
}TNode;               //孩子结点的数据类型

#define MaxSize 100
typedef struct{
     TNode nodes[MaxSize];//结点数据域
     int n;//树中结点数量
}Tree;     //树的孩子表示结构

孩子兄弟表示法：存储孩子结点和兄弟结点。

typedef char ElemType;
typedef struct CSNode{
   ElemType data;//该结点数据域
   struct CSNode *firsrchild,*right;//指向该结点的第一个孩子结点和该结点的右兄弟结点
}CSNode        //孩子兄弟结点数据类型