[数据结构与算法]树的双亲表示法(链表实现) -A

简述说明

可以参考: 树的双亲表示法(数组实现) -A

• 采用链表实现树的双亲表示法(带头结点).
• 树结点: 数据域 & 双亲域 & id标识.
• 树结点的id标识按顺序记录.
• 修改数据域数据类型则需要修改部分代码使兼容.
• 树结点按层序序列存储.
• 当最大结点数(T->maxsize)为0时, 则不限制最大结点数.

存储结构

c语言实现代码

• main.c

#include <stdio.h>
#include <stdlib.h>
#include "ParentTree.h"

/*********************************/
#define STR_MAXSIZE 1024

#if _WIN32
    #define CLEARSCREEN "cls"
#elif __linux__
    #define CLEARSCREEN "clear"
#endif
/*********************************/



/*=============== 树的双亲存储结构函数测试列表 ===============*/
void PrintMenu(void);
void ClearStdin(void);
void Pause(void);

void InitTree_Test(PTree *T);
void CreateTree_Test(PTree *T);
void PrintTree_Test(const PTree *T);
void ClearTree_Test(PTree *T);
void DestroyTree_Test(PTree *T);
void TreeEmpty_Test(const PTree *T);
void TreeDegree_Test(const PTree *T);
void TreeDepth_Test(const PTree *T);
void RootValue_Test(const PTree *T);
void Value_Test(const PTree *T);

void Order_Test(const PTree *T);
void Assign_Data_Test(const PTree *T);
void Assign_Id_Test(const PTree *T);
void ChildValue_Data_Test(const PTree *T);
void ChildValue_Id_Test(const PTree *T);
void Sibling_Data_Test(const PTree *T);
void Sibling_Id_Test(const PTree *T);
void ChildCount_Data_Test(const PTree *T);
void ChildCount_Id_Test(const PTree *T);
void ChildSeat_Data_Test(const PTree *T);
void ChildSeat_Id_Test(const PTree *T);

void InsertChild_Data_Test(PTree *T);
void InsertChild_Id_Test(PTree *T);
void InsertTree_Data_Test(PTree *T);
void InsertTree_Id_Test(PTree *T);
void DeleteTree_Data_Test(PTree *T);
void DeleteTree_Id_Test(PTree *T);
/*====================================================*/



void PrintMenu(void) {
    system(CLEARSCREEN);
    puts("1.InitTree \n");
    puts("2.CreateTree \n");
    puts("3.PrintTree \n");
    puts("4.ClearTree \n");
    puts("5.DestroyTree \n");
    puts("6.TreeEmpty \n");
    puts("7.TreeDegree \n");
    puts("8.TreeDepth \n");
    puts("9.RootValue \n");
    puts("10.Value \n");

    puts("11.Order \n");
    puts("12.Assign_Data \n");
    puts("13.Assign_Id \n");
    puts("14.ChildValue_Data \n");
    puts("15.ChildValue_Id \n");
    puts("16.Sibling_Data \n");
    puts("17.Sibling_Id \n");
    puts("18.ChildCount_Data \n");
    puts("19.ChildCount_Id \n");
    puts("20.ChildSeat_Data \n");
    puts("21.ChildSeat_Id \n");

    puts("22.InsertChild_Data \n");
    puts("23.InsertChild_Id \n");
    puts("24.InsertTree_Data \n");
    puts("25.InsertTree_Id \n");
    puts("26.DeleteTree_Data \n");
    puts("27.DeleteTree_Id \n");

    puts("0.Exit \n");
    printf("Input: ");
}

void ClearStdin(void) {
    char ch;
    while(ch=getchar(), ch!='\n');
}

void Pause(void) {
    puts("Press enter to continue.");
    ClearStdin();
}

void InitTree_Test(PTree *T) {
    system(CLEARSCREEN);

    Size_T n;
    printf("Input n: ");
    scanf("%u", &n);
    ClearStdin();

    if(InitTree_P(T, n))
        puts("Error. ");
    else
        puts("Ok. ");

    Pause();
}

void CreateTree_Test(PTree *T) {
    system(CLEARSCREEN);

    TElemType_P ch, str[STR_MAXSIZE];
    printf("Input str: ");
    for(Size_T i=0; i<STR_MAXSIZE; i++) {
        if(ch=getchar(), ch=='\n') {
            str[i] = '\0';
            break;
        }
        str[i] = ch;
    }
    str[STR_MAXSIZE-1] = '\0';

    if(CreateTree_P(T, str))
        puts("Error. ");
    else
        puts("Ok. ");

    Pause();
}

void PrintTree_Test(const PTree *T) {
    system(CLEARSCREEN);
    PrintTree_P(T);
    Pause();
}

void ClearTree_Test(PTree *T) {
    ClearTree_P(T);
}

void DestroyTree_Test(PTree *T) {
    DestroyTree_P(T);
}

void TreeEmpty_Test(const PTree *T) {
    system(CLEARSCREEN);
    if(TreeEmpty_P(T))
        puts("The tree is empty. ");
    else
        puts("The tree is not empty. ");
    Pause();
}

void TreeDegree_Test(const PTree *T) {
    system(CLEARSCREEN);
    printf("Degree: %u \n", TreeDegree_P(T));
    Pause();
}

void TreeDepth_Test(const PTree *T) {
    system(CLEARSCREEN);
    printf("Depth: %u \n", TreeDepth_P(T));
    Pause();
}

void RootValue_Test(const PTree *T) {
    system(CLEARSCREEN);
    printf("RootValue: %c \n", RootValue_P(T));
    Pause();
}

void Value_Test(const PTree *T) {
    system(CLEARSCREEN);

    PTNode *p;
    Size_T k;
    printf("Input k: ");
    scanf("%u", &k);
    ClearStdin();

    if(p = Value_P(T, k))
        printf("T->nodes[%u] = %c \n", k, p->data);
    else
        printf("T->nodes[%u] = NULL \n", k);
    
    Pause();
}

void Order_Test(const PTree *T) {
    system(CLEARSCREEN);

    TElemType_P ch;
    printf("Input ch: ");
    ch = getchar();
    ClearStdin();
    printf("T->nodes[%u] = %c \n", Order_P(T, ch), ch);

    Pause();
}

void Assign_Data_Test(const PTree *T) {
    system(CLEARSCREEN);

    TElemType_P ch, value;
    printf("Input ch & value: ");
    scanf("%c %c", &ch, &value);
    ClearStdin();

    if(Assign_Data_P(T, ch, value))
        puts("Error. ");
    else
        puts("Ok. ");

    Pause();
}

void Assign_Id_Test(const PTree *T) {
    system(CLEARSCREEN);

    Id_P id;
    TElemType_P value;
    printf("Input id & value: ");
    scanf("%u %c", &id, &value);
    ClearStdin();

    if(Assign_Id_P(T, id, value))
        puts("Error. ");
    else
        puts("Ok. ");

    Pause();
}

void ChildValue_Data_Test(const PTree *T) {
    system(CLEARSCREEN);

    PTNode *p;
    Size_T k;
    TElemType_P ch;
    printf("Input ch & k: ");
    scanf("%c %u", &ch, &k);
    ClearStdin();

    if(p = ChildValue_Data_P(T, ch, k))
        printf("The data is %c. \n", p->data);
    else
        puts("The data is NULL. ");

    Pause();
}

void ChildValue_Id_Test(const PTree *T) {
    system(CLEARSCREEN);

    PTNode *p;
    Id_P id;
    Size_T k;
    printf("Input id & k: ");
    scanf("%u %u", &id, &k);
    ClearStdin();

    if(p = ChildValue_Id_P(T, id, k))
        printf("The data is %c. \n", p->data);
    else
        puts("The data is NULL. ");

    Pause();
}

void Sibling_Data_Test(const PTree *T) {
    system(CLEARSCREEN);

    PTNode *p;
    TElemType_P ch;
    char mark;
    printf("Input ch & mark: ");
    scanf("%c %c", &ch, &mark);
    ClearStdin();
    p = Sibling_Data_P(T, ch, mark);
    
    switch(mark) {
        case LEFTSIB:
            if(p)
                printf("The leftsib of %c is %c. \n", ch, p->data);
            else
                printf("The leftsib of %c is NULL. \n", ch);
            break;
        case RIGHTSIB:
            if(p)
                printf("The rightsib of %c is %c. \n", ch, p->data);
            else
                printf("The rightsib of %c is NULL. \n", ch);
    }

    Pause();
}

void Sibling_Id_Test(const PTree *T) {
    system(CLEARSCREEN);

    PTNode *p;
    Id_P id;
    char mark;
    printf("Input id & mark: ");
    scanf("%u %c", &id, &mark);
    ClearStdin();
    p = Sibling_Id_P(T, id, mark);

    switch(mark) {
        case LEFTSIB:
            if(p)
                printf("The leftsib of %u is %c. \n", id, p->data);
            else
                printf("The leftsib of %u is NULL. \n", id);
            break;
        case RIGHTSIB:
            if(p)
                printf("The rightsib of %u is %c. \n", id, p->data);
            else
                printf("The rightsib of %u is NULL. \n", id);
    }

    Pause();
}

void ChildCount_Data_Test(const PTree *T) {
    system(CLEARSCREEN);

    TElemType_P ch;
    printf("Input ch: ");
    ch = getchar();
    ClearStdin();
    printf("The count of %c'Child is %u. \n", ch, ChildCount_Data_P(T, ch));

    Pause();
}

void ChildCount_Id_Test(const PTree *T) {
    system(CLEARSCREEN);

    Id_P id;
    printf("Input id: ");
    scanf("%u", &id);
    ClearStdin();
    printf("The count of %u'Child is %u. \n", id, ChildCount_Id_P(T, id));

    Pause();
}

void ChildSeat_Data_Test(const PTree *T) {
    system(CLEARSCREEN);

    TElemType_P ch;
    Size_T k;
    printf("Input ch & k: ");
    scanf("%c %u", &ch, &k);
    ClearStdin();
    printf("The position of %c'Child is %u. \n", ch, ChildSeat_Data_P(T, ch, k));

    Pause();
}

void ChildSeat_Id_Test(const PTree *T) {
    system(CLEARSCREEN);

    Id_P id;
    Size_T k;
    printf("Input id & k: ");
    scanf("%u %u", &id, &k);
    ClearStdin();
    printf("The position of %u'Child is %u. \n", id, ChildSeat_Id_P(T, id, k));

    Pause();
}

void InsertChild_Data_Test(PTree *T) {
    system(CLEARSCREEN);

    Size_T k;
    TElemType_P a, b;
    printf("Input a & b & k: ");
    scanf("%c %c %u", &a, &b, &k);
    ClearStdin();
    
    if(InsertChild_Data_P(T, a, b, k))
        puts("Ok. ");
    else
        puts("Error. ");

    Pause();
}

void InsertChild_Id_Test(PTree *T) {
    system(CLEARSCREEN);

    Id_P id;
    Size_T k;
    TElemType_P ch;
    printf("Input id & ch & k: ");
    scanf("%u %c %u", &id, &ch, &k);
    ClearStdin();

    if(InsertChild_Id_P(T, id, ch, k))
        puts("Ok. ");
    else
        puts("Error. ");

    Pause();
}

void InsertTree_Data_Test(PTree *T) {
    system(CLEARSCREEN);

    PTree t;
    Size_T k;
    TElemType_P ch;

    InitTree_P(&t, 100);
    CreateTree_Test(&t);

    printf("Input ch & k: ");
    scanf("%c %u", &ch, &k);
    ClearStdin();

    if(InsertTree_Data_P(T, ch, k, &t))
        puts("Error. ");
    else
        puts("Ok. ");

    DestroyTree_P(&t);
    Pause();
}

void InsertTree_Id_Test(PTree *T) {
    system(CLEARSCREEN);

    PTree t;
    Id_P id;
    Size_T k;

    InitTree_P(&t, 100);
    CreateTree_Test(&t);

    printf("Input id & k: ");
    scanf("%u %u", &id, &k);
    ClearStdin();

    if(InsertTree_Id_P(T, id, k, &t))
        puts("Error. ");
    else
        puts("Ok. ");

    DestroyTree_P(&t);
    Pause();
}

void DeleteTree_Data_Test(PTree *T) {
    system(CLEARSCREEN);

    TElemType_P ch;
    Size_T k;

    printf("Input ch & k: ");
    scanf("%c %u", &ch, &k);
    ClearStdin();

    if(DeleteTree_Data_P(T, ch, k))
        puts("Error. ");
    else
        puts("Ok. ");

    Pause();
}

void DeleteTree_Id_Test(PTree *T) {
    system(CLEARSCREEN);

    Id_P id;
    printf("Input id: ");
    scanf("%u", &id);
    ClearStdin();

    if(DeleteTree_Id_P(T, id))
        puts("Error. ");
    else
        puts("Ok. ");

    Pause();
}



int main(void) {
    PTree T;
    int choice;

    while(TRUE) {
        choice = -1;
        PrintMenu();
        scanf("%d", &choice);
        ClearStdin();

        if(!choice) break;
        switch(choice) {
            case 1: InitTree_Test(&T); break;
            case 2: CreateTree_Test(&T); break;
            case 3: PrintTree_Test(&T); break;
            case 4: ClearTree_Test(&T); break;
            case 5: DestroyTree_Test(&T); break;
            case 6: TreeEmpty_Test(&T); break;
            case 7: TreeDegree_Test(&T); break;
            case 8: TreeDepth_Test(&T); break;
            case 9: RootValue_Test(&T); break;
            case 10: Value_Test(&T); break;

            case 11: Order_Test(&T); break;
            case 12: Assign_Data_Test(&T); break;
            case 13: Assign_Id_Test(&T); break;
            case 14: ChildValue_Data_Test(&T); break;
            case 15: ChildValue_Id_Test(&T); break;
            case 16: Sibling_Data_Test(&T); break;
            case 17: Sibling_Id_Test(&T); break;
            case 18: ChildCount_Data_Test(&T); break;
            case 19: ChildCount_Id_Test(&T); break;
            case 20: ChildSeat_Data_Test(&T); break;
            case 21: ChildSeat_Id_Test(&T); break;

            case 22: InsertChild_Data_Test(&T); break;
            case 23: InsertChild_Id_Test(&T); break;
            case 24: InsertTree_Data_Test(&T); break;
            case 25: InsertTree_Id_Test(&T); break;
            case 26: DeleteTree_Data_Test(&T); break;
            case 27: DeleteTree_Id_Test(&T); break;
        }
    }

    puts("\nOk. \n");
    return 0;
}

• ParentTree.c

#include <stdio.h>
#include <malloc.h>
#include "ParentTree.h"

Status InitTree_P(PTree *T, const Size_T N) {
    if(T) {
        T->nodes = (PTNode *)malloc(sizeof(PTNode));
        if(T->nodes) {
            T->nodes->id = 0;
            T->nodes->data = '\0';
            T->nodes->parent = NULL;
            T->nodes->next = NULL;
            T->maxsize = N;
            T->len = 0;
            return OK;
        }
    }
    return ERROR;
}

Status CreateTree_P(PTree *T, const char *str) {
    /********************************************************************
     * A.长度问题
     *      a.有效字符长度(useful)为0 ---> ERROR
     *      b.树的最大结点数(T->maxsize)<有效字符长度(useful) ---> ERROR
     *
     * B.格式问题
     *      (for循环内)
     *          a.第一个有效字符是空字符('^') ---> ERROR
     *          b.与空字符('^')相邻的字符不是空格字符 ---> ERROR
     *          c.双亲(parent)>=当前结点数(count) ---> ERROR
     *
     *      (for循环外)
     *          d.双亲(parent)!=当前结点数(count) ---> ERROR
     *******************************************************************/

    if(!T || !T->nodes || !str)
        return ERROR;

    Size_T useful = 0;
    for(Size_T i=0; str[i]; i++)
        if(str[i]!=' ' && str[i]!='^')
            useful++;
    if(!useful || (T->maxsize && T->maxsize<useful))
        return ERROR;



    PTNode *p=T->nodes, *p_parent=T->nodes;
    Size_T parent=0, count=1;
    for(Size_T i=0; str[i]; i++)
        if(str[i] == '^') {
            if(count==1 || str[i-1]!=' ' || (str[i+1] && str[i+1]!=' ')) {
                parent = 0;
                break;
            }
            parent++;
            if(p_parent->next)
                p_parent = p_parent->next;
        }else if(str[i] != ' ') {
            PTNode *node = (PTNode *)malloc(sizeof(PTNode));
            if(!node || parent>=count) {
                free(node);
                parent = 0;
                break;
            }
            p->next = node;
            p = node;

            node->data = str[i];
            node->parent = p_parent;
            node->id = count;
            node->next = NULL;
            count++;

            if(str[i+1] == ' ') {
                parent++;
                if(p_parent->next)
                    p_parent = p_parent->next;
            }
        }


    
    if(parent == count) {
        T->len = count-1;
        return OK;
    }else {
        ClearTree_P(T);
        return ERROR;
    }
}

void PrintTree_P(const PTree *T) {
    if(T) {
        printf("maxsize: %u \t length: %u \n", T->maxsize, T->len);
        printf("%s \t %s \t %s \n", "id", "parent", "data");
        if(T->nodes) {
            PTNode *p = T->nodes->next;
            while(p) {
                puts("------------------------------ ");
                printf("%u \t %u \t\t %c \n", p->id, p->parent->id, p->data);
                p = p->next;
            }
        }
    }
}

void ClearTree_P(PTree *T) {
    if(T && T->nodes) {
        T->len = 0;
        while(T->nodes->next) {
            PTNode *del = T->nodes->next;
            T->nodes->next = del->next;
            free(del);
        }
    }
}

void DestroyTree_P(PTree *T) {
    if(T) {
        T->len = 0;
        T->maxsize = 0;
        while(T->nodes) {
            PTNode *del = T->nodes;
            T->nodes = del->next;
            free(del);
        }
    }
}

Bool TreeEmpty_P(const PTree *T) {
    return (T && T->len ? FALSE : TRUE );
}

Size_T TreeDegree_P(const PTree *T) {
    Size_T max = 0;

    if(T && T->nodes) {
        PTNode *parent = T->nodes;
        PTNode *p = parent->next;
        Size_T count = 0;
        while(p) {
            if(p->parent != parent) {
                count = 1;
                parent = p->parent;
            }else count++;
            if(max < count)
                max = count;
            p = p->next;
        }
    }

    return max;
}

Size_T TreeDepth_P(const PTree *T) {
    Size_T level = 0;

    if(T && T->nodes) {
        PTNode *p = T->nodes;
        while(p->next)
            p = p->next;
        while(T->nodes != p) {
            level++;
            p = p->parent;
        }
    }

    return level;
}

TElemType_P RootValue_P(const PTree *T) {
    return (T && T->len ? T->nodes->next->data : '\0' );
}

PTNode* Value_P(const PTree *T, const Size_T k) {
    if(T && T->len && k<=T->len) {
        PTNode *p = T->nodes->next;
        while(p) {
            if(p->id==k || (!k && !p->next))
                return p;
            p = p->next;
        }
    }
    return NULL;
}

Size_T Order_P(const PTree *T, const TElemType_P e) {
    Size_T index = 0;

    if(T && T->nodes) {
        PTNode *p = T->nodes->next;
        while(p) {
            if(p->data == e) {
                index = p->id;
                break;
            }
            p = p->next;
        }
    }

    return index;
}

Status Assign_Data_P(const PTree *T, const TElemType_P e, const TElemType_P value) {
    if(T && T->nodes) {
        PTNode *p = T->nodes->next;
        while(p) {
            if(p->data == e) {
                p->data = value;
                return OK;
            }
            p = p->next;
        }
    }
    return ERROR;
}

Status Assign_Id_P(const PTree *T, const Id_P id, const TElemType_P value) {
    if(T && id && id<=T->len) {
        PTNode *p = T->nodes->next;
        while(p) {
            if(p->id == id) {
                p->data = value;
                return OK;
            }
            p = p->next;
        }
    }
    return ERROR;
}

PTNode* ChildValue_Data_P(const PTree *T, const TElemType_P e, const Size_T order) {
    if(T && T->len) {
        Size_T count = 1;
        PTNode *p = T->nodes->next->next;
        while(p) {
            if(p->parent->data == e) {
                Bool flag = (p->next && p->parent==p->next->parent);
                if((count==order) || (!order && !flag))
                    return p;
                count = (flag ? count+1 : 1 );
            }
            p = p->next;
        }
    }
    return NULL;
}

PTNode* ChildValue_Id_P(const PTree *T, const Id_P id, const Size_T order) {
    if(T && id && id<T->len) {
        Size_T count = 1;
        PTNode *p = T->nodes->next->next;
        while(p && p->parent->id<=id) {
            if(p->parent->id == id) {
                Bool flag = (!p->next || p->parent!=p->next->parent);
                if((count==order) || (!order && flag))
                    return p;
                count++;
            }
            p = p->next;
        }
    }
    return NULL;
}

PTNode* Sibling_Data_P(const PTree *T, const TElemType_P e, const char mark) {
    if(!T || !T->len || (mark!=LEFTSIB && mark!=RIGHTSIB)) return NULL;

    PTNode *prior = T->nodes->next;
    PTNode *p = prior->next;
    while(p) {
        if(p->data == e) {
            switch(mark) {
                case LEFTSIB:
                    if(prior->parent == p->parent)
                        return prior;
                    break;
                case RIGHTSIB:
                    if(p->next && p->parent==p->next->parent)
                        return p->next;
            }
        }
        prior = p;
        p = p->next;
    }

    return NULL;
}

PTNode* Sibling_Id_P(const PTree *T, const Id_P id, const char mark) {
    if(mark!=LEFTSIB && mark!=RIGHTSIB) return NULL;

    PTNode *prior = Value_P(T, id-1);
    if(prior && prior->next) {
        PTNode *p = prior->next;
        switch(mark) {
            case LEFTSIB:
                if(prior->parent == p->parent)
                    return prior;
                break;
            case RIGHTSIB:
                if(p->next && p->parent==p->next->parent)
                    return p->next;
        }
    }

    return NULL;
}

Size_T ChildCount_Data_P(const PTree *T, const TElemType_P e) {
    return ChildCount_Id_P(T, Order_P(T, e));
}

Size_T ChildCount_Id_P(const PTree *T, const Id_P id) {
    Size_T count = 0;

    if(T && id && id<T->len) {
        PTNode *p = T->nodes->next->next;
        while(p && p->parent->id<=id) {
            if(p->parent->id == id)
                count++;
            p = p->next;
        }
    }

    return count;
}

Size_T ChildSeat_Data_P(const PTree *T, const TElemType_P e, const Size_T k) {
    PTNode *p = ChildValue_Data_P(T, e, k);
    return (p ? p->id : 0 );
}

Size_T ChildSeat_Id_P(const PTree *T, const Id_P id, const Size_T k) {
    PTNode *p = ChildValue_Id_P(T, id, k);
    return (p ? p->id : 0 );
}

Size_T InsertChild_Data_P(PTree *T, const TElemType_P p, const TElemType_P e, const Size_T k) {
    Size_T index = 0;

    if(T && T->nodes && (!T->maxsize || T->maxsize>T->len)) {
        PTNode *ptr = T->nodes;
        while(ptr->next) {
            ptr = ptr->next;
            if(ptr->data == p)
                if(index = InsertChild_Id_P(T, ptr->id, e, k))
                    break;
        }
    }

    return index;
}

Size_T InsertChild_Id_P(PTree *T, const Id_P id, const TElemType_P e, const Size_T k) {
    PTNode *parent = Value_P(T, id);
    PTNode *prior = parent;
    Size_T index = 0;

    if(parent && (!T->maxsize || T->maxsize>T->len)) {
        if(k < 2) index = T->len+1;

        PTNode *p = parent->next;
        while(p) {
            if(p->parent->id >= id) {
                if(k < 2) index = p->id;
                break;
            }
            prior = p;
            p = p->next;
        }

        if(p && p->parent==parent) {
            Size_T i = 1;
            while(p && p->parent==parent && (i<k || !k)) {
                prior = p;
                p = p->next;
                i++;
            }
            index = (!k || i==k ? prior->id+1 : 0 );
        }
    }

    if(index) {
        PTNode *node = (PTNode *)malloc(sizeof(PTNode));
        if(!node) return 0;
        node->id = index;
        node->data = e;
        node->parent = parent;
        node->next = prior->next;
        prior->next = node;

        PTNode *p = node->next;
        while(p) {
            p->id++;
            p = p->next;
        }
        T->len++;
    }

    return index;
}

Status InsertTree_Data_P(PTree *T, const TElemType_P p, const Size_T k, const PTree *t) {
    Status flag = ERROR;

    if(T && T->nodes && t && t->len && (!T->maxsize || T->maxsize>=T->len+t->len)) {
        Size_T *index = (Size_T *)malloc(sizeof(Size_T) * t->len);
        if(!index) return ERROR;

        PTNode *ptr = t->nodes->next;
        if(index[0] = InsertChild_Data_P(T, p, ptr->data, k)) {
            Size_T k = 1;
            while(ptr->next) {
                ptr = ptr->next;
                index[k] = InsertChild_Id_P(T, index[ptr->parent->id-1], ptr->data, 0);
                k++;
            }
            flag = OK;
        }

        free(index);
    }

    return flag;
}

Status InsertTree_Id_P(PTree *T, const Id_P id, const Size_T k, const PTree *t) {
    Status flag = ERROR;

    if(T && T->nodes && t && t->len && (!T->maxsize || T->maxsize>=T->len+t->len)) {
        Size_T *index = (Size_T *)malloc(sizeof(Size_T) * t->len);
        if(!index) return ERROR;

        PTNode *ptr = t->nodes->next;
        if(index[0] = InsertChild_Id_P(T, id, ptr->data, k)) {
            Size_T k = 1;
            while(ptr->next) {
                ptr = ptr->next;
                index[k] = InsertChild_Id_P(T, index[ptr->parent->id-1], ptr->data, 0);
                k++;
            }
            flag = OK;
        }

        free(index);
    }

    return flag;
}

Status DeleteTree_Data_P(PTree *T, const TElemType_P p, const Size_T k) {
    return DeleteTree_Id_P(T, ChildSeat_Data_P(T, p, k));
}

Status DeleteTree_Id_P(PTree *T, const Size_T k) {
    if(TreeEmpty_P(T) || !k || k>T->len)
        return ERROR;

    Size_T count = 1;
    Size_T *index = (Size_T *)malloc(sizeof(Size_T) * T->len);
    if(!index) return ERROR;
    index[0] = k;

    PTNode *p = T->nodes;
    while(p->next) {
        p = p->next;
        if(p->parent->id >= k)
            for(Size_T i=0; i<count; i++)
                if(p->parent->id == index[i]) {
                    index[count] = p->id;
                    count++;
                    break;
                }
    }



    Size_T len = 1;
    p = T->nodes;
    while(p->next) {
        Bool flag = TRUE;
        for(Size_T i=0; i<count; i++)
            if(p->next->id == index[i]) {
                flag = FALSE;
                break;
            }
            
        if(flag) {
            p = p->next;
            p->id = len;
            len++;
        }else {
            PTNode *del = p->next;
            p->next = del->next;
            free(del);
        }
    }

    T->len = len-1;
    free(index);
    return OK;
}

• ParentTree.h

#ifndef PARENTTREE_H_INCLUDE
#define PARENTTREE_H_INCLUDE

/**************************************/
typedef unsigned int Size_T;
typedef char Status;    //自定义状态型
typedef char Bool;      //自定义布尔型
#define TRUE 1      //真
#define FALSE 0     //假
#define OK 0        //正常
#define ERROR -1    //异常
/**************************************/

/*_______________ 树的双亲表示法结构定义 _______________*/
#define LEFTSIB 'L'     //左兄弟
#define RIGHTSIB 'R'    //右兄弟

typedef char TElemType_P;   //树的自定义data类型
typedef Size_T Id_P;        //树的自定义id类型

/* 构造树结点 */
typedef struct PTNode {
    Id_P id;                //id标识
    TElemType_P data;       //数据域
    struct PTNode *parent;  //双亲域
    struct PTNode *next;    //指针域
} PTNode;

/* 构造树 */
typedef struct {
    PTNode *nodes;      //结点域
    Size_T len;         //结点数
    Size_T maxsize;     //最大结点数
} PTree;
/*____________________________________________________*/



/*========================================= 树的双亲存储结构函数列表 =========================================*/
Status InitTree_P(PTree *T, const Size_T N);
/*---------------
|(01) 初始化树T. |
---------------*/

Status CreateTree_P(PTree *T, const char *str);
/*--------------------
|(02) 按层序序列构造树. |
--------------------*/

void PrintTree_P(const PTree *T);
/*-------------
|(03) 打印树T. |
-------------*/

void ClearTree_P(PTree *T);
/*-------------
|(04) 清空树T. |
-------------*/

void DestroyTree_P(PTree *T);
/*-------------
|(05) 销毁树T. |
-------------*/

Bool TreeEmpty_P(const PTree *T);
/*--------------------
|(06) 判断树T是否为空. |
--------------------*/

Size_T TreeDegree_P(const PTree *T);
/*----------------
|(07) 返回树T的度. |
----------------*/

Size_T TreeDepth_P(const PTree *T);
/*------------------
|(08) 返回树T的深度. |
------------------*/

TElemType_P RootValue_P(const PTree *T);
/*---------------------
|(09) 返回树T的根结点值. |
---------------------*/

PTNode* Value_P(const PTree *T, const Size_T k);
/*-----------------------------------------------------------
|(10) 返回树T的第k个树结点(按层序序列计数), k=0定义为最后一个树结点. |
-----------------------------------------------------------*/



Size_T Order_P(const PTree *T, const TElemType_P e);
/*-----------------------------------------------------------
|(11) 返回树结点值为e的树结点在树T中的存储位置, 返回0表示无此树结点. |
-----------------------------------------------------------*/

Status Assign_Data_P(const PTree *T, const TElemType_P e, const TElemType_P value);
/*-------------------------------------------
|(12) 将树结点值为e的树结点的树结点值赋值为value. |
-------------------------------------------*/

Status Assign_Id_P(const PTree *T, const Id_P id, const TElemType_P value);
/*-----------------------------------------------------
|(13) 根据树结点的id, 赋值与其对应的树结点的树结点值为value. |
-----------------------------------------------------*/

PTNode* ChildValue_Data_P(const PTree *T, const TElemType_P e, const Size_T order);
/*----------------------------------------------------------------------------------
|(14) 返回树结点值为e的树结点的第order个孩子结点(从左至右计数), order=0定义为最后一个孩子结点. |
----------------------------------------------------------------------------------*/

PTNode* ChildValue_Id_P(const PTree *T, const Id_P id, const Size_T order);
/*----------------------------------------------------------------------------------------------
|(15) 根据树结点的id, 返回与其对应的树结点的第order个孩子结点(从左至右计数), order=0定义为最后一个孩子结点. |
----------------------------------------------------------------------------------------------*/

PTNode* Sibling_Data_P(const PTree *T, const TElemType_P e, const char mark);
/*-------------------------------------------------
|(16) 返回树结点值为e的树结点的左(右)兄弟, mark标记左右. |
-------------------------------------------------*/

PTNode* Sibling_Id_P(const PTree *T, const Id_P id, const char mark);
/*-------------------------------------------------------------
|(17) 根据树结点的id, 返回与其对应的树结点的左(右)兄弟, mark标记左右. |
-------------------------------------------------------------*/

Size_T ChildCount_Data_P(const PTree *T, const TElemType_P e);
/*-------------------------------------------
|(18) 返回树结点值为e的树结点的孩子结点(子树)个数. |
-------------------------------------------*/

Size_T ChildCount_Id_P(const PTree *T, const Id_P id);
/*-------------------------------------------------------
|(19) 根据树结点的id, 返回与其对应的树结点的孩子结点(子树)个数. |
-------------------------------------------------------*/

Size_T ChildSeat_Data_P(const PTree *T, const TElemType_P e, const Size_T k);
/*-------------------------------------------------------------------------------------
|(20) 返回树结点值为e的树结点的第k个孩子结点(层序计数)在树T中的存储位置, k=0定义为最后一个孩子结点. |
-------------------------------------------------------------------------------------*/

Size_T ChildSeat_Id_P(const PTree *T, const Id_P id, const Size_T k);
/*-------------------------------------------------------------------------------------------------
|(21) 根据树结点的id, 返回与其对应的树结点的第k个孩子结点(层序计数)在树T中的存储位置, k=0定义为最后一个孩子结点. |
-------------------------------------------------------------------------------------------------*/



Size_T InsertChild_Data_P(PTree *T, const TElemType_P p, const TElemType_P e, const Size_T k);
/*--------------------------------------------------------------------------------------------
|(22) 生成一个树结点值为e的树结点, 并插入到树结点值为p的树结点的第k棵子树(层序计数), k=0定义为最后一棵子树. |
--------------------------------------------------------------------------------------------*/

Size_T InsertChild_Id_P(PTree *T, const Id_P id, const TElemType_P e, const Size_T k);
/*--------------------------------------------------------------------------------------------------------
|(23) 生成一个树结点值为e的树结点, 并根据树结点的id, 插入到与其对应的树结点的第k棵子树(层序计数), k=0定义为最后一棵子树. |
--------------------------------------------------------------------------------------------------------*/

Status InsertTree_Data_P(PTree *T, const TElemType_P p, const Size_T k, const PTree *t);
/*----------------------------------------------------------------------
|(24) 将树t插入到树结点值为p的树结点的第k棵子树(层序计数), k=0定义为最后一棵子树. |
----------------------------------------------------------------------*/

Status InsertTree_Id_P(PTree *T, const Id_P id, const Size_T k, const PTree *t);
/*----------------------------------------------------------------------------------
|(25) 根据树结点的id, 将树t插入到与其对应的树结点的第k棵子树(层序计数), k=0定义为最后一棵子树. |
----------------------------------------------------------------------------------*/

Status DeleteTree_Data_P(PTree *T, const TElemType_P p, const Size_T k);
/*----------------------------------------------------------------
|(26) 删除树结点值为p的树结点的第k棵子树(层序计数), k=0定义为最后一棵子树. |
----------------------------------------------------------------*/

Status DeleteTree_Id_P(PTree *T, const Size_T k);
/*------------------
|(27) 删除第k棵子树. |
------------------*/
/*========================================================================================================*/
#endif //PARENTTREE_H_INCLUDE