(36)王道数据结构-树的存储结构

双亲表示法

每个结点中保存指向双亲的指针，采用的是顺序存储

代码结构

typedef struct {    //树结构定义
    PTNode nodes[MAX_TREE_SIZE];    //双亲表示
    int n;     //结点数
}

增删结点

新增结点

新增数据元素，无需按逻辑上的次序存储

删除结点

方案一:
待删除结点的双亲指针设为-1代表当前结点是空的

方案二:
尾部数据上移，填充空白结点

优缺点

优点

查找指定结点的双亲很方便

缺点

1.空数据导致遍历更慢(删除方案二)
2.查找指定结点的孩子只能从头遍历

孩子表示法

顺序存储各个结点，每个结点中保存孩子链表头指针，采用的是顺序加链式的存储

代码结构

struct CTNode {
    int child;  //孩子结点在数组中的位置
    struct CTNode *next;    //下一个孩子
};

typedef struct {
    ELemType data;
    struct CTNode *firstChild;  //第一个孩子
} CTBox;

typedef struct {
    CTBox nodes[MAX_TREE_SIZE];
    int n, r;   //结点数和根的位置
}CTree;

孩子兄弟表示法

孩子兄弟表示法是纯链式存储,可以利用熟悉的二叉树进行响应的操作

代码结构

typedef struct CSNode {
    ElemType data;  //数据域
    struct CSNode *firstchild, *nextsibling;//第一个孩子和右兄弟指针(可以看作左指针和右指针)
}

存储结构

graph TD;
    A(("A"));
    B(("B"));
    C(("C"));
    D(("D"));
    E(("E"));
    F(("F"));
    G(("G"));
    H(("H"));
    I(("I"));
    J(("J"));
    K(("K"));
    
    A-->B;
    A-->C;
    A-->D;

    B-->E;
    B-->F;
    C-->G;
    D-->H;
    D-->I;
    D-->J;

    E-->K;

graph TD;
    A(("A"));
    B(("B"));
    C(("C"));
    D(("D"));
    E(("E"));
    F(("F"));
    G(("G"));
    H(("H"));
    I(("I"));
    J(("J"));
    K(("K"));

    A-->B;
    B-->E;
    B-->C;

    E-->K;
    E-->F;

    C-->G;
    C-->D;

    D-->H;
    D-->N1(( ));
    H-->N2(( ));
    H-->I;
    I-->N3(( ));
    I-->J;
    style N1 fill:#f100,stroke-width:0px
    style N2 fill:#f100,stroke-width:0px
    style N3 fill:#f100,stroke-width:0px
    linkStyle 8 stroke:#0ff,stroke-width:0px
    linkStyle 9 stroke:#0ff,stroke-width:0px
    linkStyle 11 stroke:#0ff,stroke-width:0px

树森林转换

森林是m(m≥0棵互不相交的树的集合)

森林转树

graph TD;
    B(("B"));
    C(("C"));
    D(("D"));
    E(("E"));
    F(("F"));
    G(("G"));
    H(("H"));
    I(("I"));
    J(("J"));
    K(("K"));
    L(("L"));
    M(("M"));
    
    B-->E;
    B-->F;
    E-->K;
    E-->L;

    C-->G;

    D-->H;
    D-->I;
    D-->J;
    H-->M;

graph TD;
    B(("B"));
    C(("C"));
    D(("D"));
    E(("E"));
    F(("F"));
    G(("G"));
    H(("H"));
    I(("I"));
    J(("J"));
    K(("K"));
    L(("L"));
    M(("M"));
    
    B-->E;
    B-->C;
    E-->K;
    E-->F;
    C-->G;
    C-->D;

    K-->N1(( ));
    K-->L;
    D-->H;
    D-->N2(( ));

    H-->M;
    H-->I;
    I-->N3(( ));
    I-->J;
    style N1 fill:#f100,stroke-width:0px
    style N2 fill:#f100,stroke-width:0px
    style N3 fill:#f100,stroke-width:0px
    linkStyle 6 stroke:#0ff,stroke-width:0px
    linkStyle 9 stroke:#0ff,stroke-width:0px
    linkStyle 12 stroke:#0ff,stroke-width:0px

树转森林

graph TD;
    A(("A"));
    B(("B"));
    C(("C"));
    D(("D"));
    E(("E"));
    F(("F"));
    G(("G"));
    H(("H"));
    I(("I"));
    J(("J"));
    K(("K"));
    L(("L"));
    
    A-->B;
    A-->C;
    B-->D;
    C-->E;
    C-->F;

    D-->G;
    D-->H;

    E-->I;
    E-->J;
    F-->K;
    F-->L;

graph TD;
    A(("A"));
    B(("B"));
    C(("C"));
    D(("D"));
    E(("E"));
    F(("F"));
    G(("G"));
    H(("H"));
    I(("I"));
    J(("J"));
    K(("K"));
    L(("L"));
    
    A-->B;
    B-->D;
    B-->H;
    D-->G;

    C-->E;
    C-->J;
    E-->I;

    F-->K;