树的定义—-递归（两者相联系）

根节点：唯一

节点的度：节点拥有的子树数。度为0—>称为终端节点或叶节点

树的度：树内各节点的度的最大值

内部节点：除根节点外的节点

孩子（child）：节点的子树的根 称为该节点的 孩子，反过来，称为双亲（parent）

兄弟（sibling）：同一双亲的孩子之间的关系

节点的祖先：从根到该节点所经分支上的全部节点

节点层次：根为第一层，根的孩子为第二层

树的深度（Depth）：树中节点的最大层次

森林（Forest）：是m（m>0）棵互不相交的树的集合

树的存储结构（简单顺序结构无法满足一对多结构的存储）

1）双亲表示法：

关键在于“除根节点外，每个节点都有且仅有一个双亲，将树从下往上看”

节点：data（数据） | parent（指针，指向其双亲）

/*双亲表示法：树的结构定义。这样的方式找双亲非常easy，但找孩子就非常麻烦，需遍历整个结构*/typedef int ElemType;typedef struct Node{    ElemType data;    int parent;  // 数组下标，根节点的位置域存放-1} Tnode;typedef struct{    Tnode nodes[MAX_SIZE]; // 节点数组    int r,n;  // 根的位置和节点数} Tree;

2）孩子表示法：一个顺序存储结构与链式存储结构的结合

/*孩子表示法*/typedef struct Node{    int child;             // 存放一个节点的孩子的数据    struct Node *next;     // 指向该节点的还有一个孩子。假设没有置空} * Childptr;typedef struct{    ElemType data;         // 存放一个节点数据    Childptr firstchild;   // 指向他的第一个孩子的位置} Tbox;typedef struct{    Tbox nodes[MAX_SIZE];  // 上面的Tree box 用一个数组来包括。即每个Tbox节点就是一个元素    int r,n;               // 根节点的位置和节点数} Tree;

可对比下图理解：

3）孩子兄弟表示法 ：（最经常使用）

声明一个节点，一个data域，两个指针域：一个指向孩子，还有一个指向其兄弟

/*孩子兄弟表示法*/typedef struct Node{    ElemType data;    struct Node *firstchild,*rightsib;  // 一个指向孩子，还有一个指向其兄弟，还能够再加一个指针域用来指向其parent;}CSNode,* Tree;

/点滴积累，我的一小步O(∩_∩)O~/