树（基本概念及存储结构）

￡神魔★判官ぃ 2022-08-02 05:54 179阅读 0赞

树的定义—-递归（两者相联系）  
根节点：唯一  
**节点的度：节点拥有的子树数**，度为0—>称为终端节点或叶节点  
**树的度：树内各节点的度的最大值**  
内部节点：除根节点外的节点  
![这里写图片描述][20150711161456629]

孩子（child）：节点的子树的根 称为该节点的 孩子，反过来，称为双亲（parent）  
兄弟（sibling）：同一双亲的孩子之间的关系  
节点的祖先：从根到该节点所经分支上的所有节点  
**节点层次：根为第一层，根的孩子为第二层**  
**树的深度（Depth）：树中节点的最大层次**  
![这里写图片描述][20150711161612709]

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

![这里写图片描述][20150711160420869]

**树的存储结构**（简单顺序结构无法满足一对多结构的存储）  
**1）双亲表示法：**  
关键在于“除根节点外，每一个节点都有且仅有一个双亲，将树从下往上看”  
节点：data（数据） | parent（指针，指向其双亲）

/*双亲表示法：树的结构定义，这种方式找双亲很容易，但找孩子就很麻烦，需遍历整个结构*/
    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;

可对照下图理解：  
![这里写图片描述][20150711161744246]

**3）孩子兄弟表示法 ：（最常用）**  
声明一个节点，一个data域，两个指针域：一个指向孩子，另一个指向其兄弟

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

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

[20150711161456629]: /images/20220731/31e0176e53e94ca7979bacc6652631d2.png
[20150711161612709]: /images/20220731/8be383d00a4d43079e40f3351def789a.png
[20150711160420869]: /images/20220731/fe81a5a8be1642009090e23f23c602b2.png
[20150711161744246]: /images/20220731/c9e4e9e48350490aa115b410e878167d.png