精华内容
下载资源
问答
  • 2021-11-23 22:06:13

    #include<stdio.h>
    typedef int elemtype;
    #define maxsize 100
    //双亲表示法不需要通过链表进行实现
    //只需要通过顺序存储的parent的值就可以了
    typedef struct node
    {
    int parent;//表示其双亲结点的位置:其在数组位置的下标
    elemtype data;//树结点的数据类型
    }pnode;//注意这个结点只能表示的是一行数据哦
    typedef struct ptree//定义一颗树
    {
    int n;//n表示结点的个数
    int r;//表示根的位置
    pnode nodes[maxsize];//定义数组的最大容量
    }ptree;
    int main(void)
    {
    ///注意双亲表示法很容易找到双亲是真,但是很难找到各结点的孩子
    }

    更多相关内容
  • 介绍三种不同的表示法双亲表示法、孩子表示法、孩子兄弟表示法。 1.双亲表示法 我们假设以一段连续空间存储树的结点,同时在每个结点中,附设一个指示器指示其双亲结点到链表中的位置。也就是说,每个结点除了直到...

    抽象数据类型:

    在这里插入图片描述

    树的存储结构:

    利用顺序存储和链式存储的特点,完全可以实现对树的存储结构的表示。介绍三种不同的表示法:双亲表示法、孩子表示法、孩子兄弟表示法。

    1.双亲表示法

    我们假设以一段连续空间存储树的结点,同时在每个结点中,附设一个指示器指示其双亲结点到链表中的位置。也就是说,每个结点除了直到自己是谁外,还要直到自己的双亲在哪里。如图:
    在这里插入图片描述

    其中data就是数据域,存储结点的信息。而parent是指针域,存储该结点的双亲在数组中的下标。
    双亲表示法的结点结构定义代码:

    //树的双亲表示法结点结构定义
    #define MAX_TREE_SIZE 100
    typedef int TElemType;   //树结点的数据类型,目前暂定整形
    typedef struct PTNode{    //结点结构
    TElemType   data;  //结点数据域
    	int parent;              //双亲位置
    }PTNode;
    typedef struct{              //树结构
    	PTNode nodes[MAX_TREE_SIZE];    //结点数组
    	int  r,n;                     //根节点的位置和结点数
    }
    

    有了这样的结构定义,我们就可以实现双亲定义法了。由于跟结点没有双亲,所以我们约定根结点的位置域设置为-1,这就意味着,我们所有结点都直到他双亲的位置。如图的树结构和双亲表示法的图表。
    在这里插入图片描述

    在这里插入图片描述

    我们可以通过上面快速的找到结点的双亲。但是我们要知道结点的孩子怎么办?那就只有遍历整个结构了。
    我们能否改进一下?当然可以,我们可以给结点增加孩子域。

    2.孩子表示法

    换一种完全不同的想法。由于树中每个结点可能有很多的子树,可以考虑用多重链表,即每一个结点有多个指针域,其中每个指针指向一个子树的根节点,我们把这种方法叫做多重链表表示法。不过,树的每个结点的度,也就是它孩子个数是不同的。所以可以设计两种方案来解决。

    方案一

    指针域的个数等于树的度。(树的度是树各个结点度的最大值)。(结点拥有的子树称为结点的度)。
    在这里插入图片描述

    如图,data就是数据域,child1····是指针域,用来指向该结点的孩子结点。

    就像6-4-1的树一样,我们用这个方法来实现。如图。
    在这里插入图片描述
    我们可以看到。^这个符号就是代表当前这个指针域并没有用到。这样如果树的各结点的度差距过大的话,显然非常浪费空间。那我们为什么不按需分配空间呢?这样就有第二种方案了

    方案二

    每个结点指针域的个数等于该结点的度,我们专门来取一个位置来存储结点指针域的个数。如图。
    在这里插入图片描述

    如图,data就是数据域。degree是度域,也就是存在该结点的孩子结点数。child1····是指针域,用来指向该结点的孩子结点。

    那么对应的树图就应该是这样。
    在这里插入图片描述
    显然,方案二克服了浪费空间的缺点,但是由于各个结点的链表结构是不相同的,在加上要维护结点的度的数值,在运算上显然有损耗。
    能否有更好的方法?既可以减少浪费,又能使结点结构相同。
    我们把每一个结点放入顺序存储结构中是合理的,但是每个结点的孩子多少是不确定的,所以我们再对每个结点的孩子建立一个单链表来体现他们的关系。
    这就是我们的孩子表示法
    具体办法:把每个结点的孩子排列起来,以单链表作存储结构,则n个结点有n个孩子链表,如果是叶子结点则此单链表为空。然后n个头指针有组成一个线性表,采用顺序存储结构,存进一个一维数组。如图。
    在这里插入图片描述
    为此,设计两种结构,一个是孩子链表的孩子结点,如图。
    在这里插入图片描述

    child是数据域,存储某个结点在表头数组中的下标。next是指针域,用来存储某结点的下一孩子结点的指针。

    另一个是表头数组的表头结点。如图。
    在这里插入图片描述

    data是数据域,存储某结点的数据信息。firstchild是头指针域,存储该节点的孩子链表的头指针。

    以下是孩子表示法的结构定义代码。

    //树的孩子表示法结点结构定义
    #define MAX_TREE_SIZE 100
    typedef int TElemType;   //树结点的数据类型,目前暂定整形
    typedef struct CTNode{      //孩子结点
    	int child;          
    	struct CTNode * next;              
    }*ChildPtr;
    typedef struct{              //表头结构
    	TElemType data;
    	ChildPtr firstchild;                    
    }CTBox;
    typedef struct{              //树结构
    	CTBox nodes[MAX_TREE_SIZE];    //结点数组
    	int  r,n;                     //根节点的位置和结点数
    }
    

    我们可以改进一下。把双亲表示法和孩子表示法综合一下,加一个双亲域。如图。(双亲孩子表示法)
    在这里插入图片描述

    3.孩子兄弟表示法

    任何一棵树,它的结点的第一个孩子如果是唯一的,它的右兄弟如果存在也是唯一的,因此,我们设置两个指针,分别指向该结点的第一个孩子和此结点的右兄弟。
    结点结构如图。
    在这里插入图片描述

    data是数据域,firstchild为指针域,存储第一个孩子结点的地址,rightsib是指针域,存储该结点的右兄弟的地址。

    结构定义代码如下.

    //树的孩子兄弟表示法结构定义
    typedef struct CSNode{
    	TElemType data;
    	struct CSNode *firstchild,*rightsib;
    }CSNode,*CSTree;
    

    对于6-4-1的树来说,这种方法实现的示意图如图。
    在这里插入图片描述
    这种方法给查找某结点的某个孩子带来了方便,只需要通过firstchild 找到此结点的左儿子,然后再通过左儿子找到二弟,一直下去,知道找到具体的孩子。当然,如果想要找到双亲,完全可以增加一个parent 指针域来解决。

    参考:
    大话数据结构/程杰 著.—北京:清华大学出版社,2011.6

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

    简述说明

    其它实现方法:
    1.树的双亲表示法(数组实现) -A
    2.树的双亲表示法(数组实现) -B
    3.树的双亲表示法(链表实现) -B

    可以参考: 树的双亲表示法(数组实现) -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;
                p->next = NULL;
    
                node->id = count;
                node->data = str[i];
                node->parent = p_parent;
                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) {
                    TElemType_P parent = (p->parent!=T->nodes ? p->parent->data : ' ' );
                    puts("------------------------------ ");
                    printf("%u \t %c \t\t %c \n", p->id, parent, 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;
    
        PTNode *p = Value_P(T, 0);
        while(p && p!=T->nodes) {
            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)) {
                while(ptr->next) {
                    ptr = ptr->next;
                    index[ptr->id-1] = InsertChild_Id_P(T, index[ptr->parent->id-1], ptr->data, 0);
                }
                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)) {
                while(ptr->next) {
                    ptr = ptr->next;
                    index[ptr->id-1] = InsertChild_Id_P(T, index[ptr->parent->id-1], ptr->data, 0);
                }
                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(!T || !T->len || !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 = 0;
        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) {
                len++;
                p = p->next;
                p->id = len;
            }else {
                PTNode *del = p->next;
                p->next = del->next;
                free(del);
            }
        }
    
        T->len = len;
        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
    
    展开全文
  • 树的双亲表示法,孩子表示法以及孩子兄弟表示法

    千次阅读 多人点赞 2020-06-12 14:43:11
    文章目录树的双亲表示法树的孩子表示法树的孩子兄弟表示法 顺序存储和链式存储,本节来学习如何存储具有普通树结构的数据。 树的双亲表示法 双亲表示法采用顺序表(也就是数组)存储普通树,其实现的核心思想是:...


      如下图所示,这是一棵普通的树,该如何存储呢?通常,存储具有普通树结构数据的方法有 3 种:
      双亲表示法;
      孩子表示法;
      孩子兄弟表示法;
    在这里插入图片描述
                        图1

    树的双亲表示法

      双亲表示法采用顺序表(也就是数组)存储普通树,其实现的核心思想是:顺序存储各个节点的同时,给各节点附加一个记录其父节点位置的变量
      注意,根节点没有父节点(父节点又称为双亲节点),因此根节点记录父节点位置的变量通常置为 -1。
    在这里插入图片描述
                  图2
      双亲表示法存储普通树代码

    /*
     * @Description: 树的双亲表示法
     * @Version: V1.0
     * @Autor: Carlos
     * @Date: 2020-05-21 14:41:32
     * @LastEditors: Carlos
     * @LastEditTime: 2020-06-01 22:12:34
     */ 
    #include<stdio.h>
    #include<stdlib.h>
    //宏定义树中结点的最大数量
    #define MAX_SIZE 20
    //宏定义树结构中数据类型
    typedef char ElemType;
    //结点结构
    typedef struct Snode  
    {
        //树中结点的数据类型
        ElemType data;
        //结点的父结点在数组中的位置下标
        int parent;
    }PNode;
    //树结构
    typedef struct  
    {
        //存放树中所有结点
        PNode tnode[MAX_SIZE];
        //结点个数
        int n;                
    }PTree;
    /**
     * @Description: 节点初始化
     * @Param: PTree tree 结构体变量
     * @Return: PTree 结构体地址
     * @Author: Carlos
     */
    PTree InitPNode(PTree tree)
    {
        int i,j;
        char ch;
        printf("请输入节点个数:\n");
        scanf("%d",&(tree.n));
    
        printf("请输入结点的值其双亲位于数组中的位置下标:\n");
        for(i=0; i<tree.n; i++)
        {
            fflush(stdin);
            scanf("%c %d",&ch,&j);
            tree.tnode[i].data = ch;
            tree.tnode[i].parent = j;
        }
        return tree;
    }
    /**
     * @Description: 查找树中指定节点
     * @Param: PTree tree 结构体变量
     * @Return: 无
     * @Author: Carlos
     */
    void FindParent(PTree tree)
    {
        char a;
        int isfind = 0;
        printf("请输入要查询的结点值:\n");
        fflush(stdin);
        scanf("%c",&a);
        for(int i =0;i<tree.n;i++){
            if(tree.tnode[i].data == a){
                isfind=1;
                //找到父节点的下标数值
                int ad=tree.tnode[i].parent;
                printf("%c的父节点为 %c,存储位置下标为 %d",a,tree.tnode[ad].data,ad);
                break;
            }
        }
        if(isfind == 0){
            printf("树中无此节点");
        }
    }
    
    int main()
    {
        PTree tree;
        tree = InitPNode(tree);
        FindParent(tree);
        return 0;
    }
    
    

    树的孩子表示法

      孩子表示法存储普通树采用的是 “顺序表+链表” 的组合结构,其存储过程是:从树的根节点开始,使用顺序表依次存储树中各个节点,需要注意的是,与双亲表示法不同,孩子表示法会给各个节点配备一个链表,用于存储各节点的孩子节点位于顺序表中的位置。
      如果节点没有孩子节点(叶子节点),则该节点的链表为空链表。
      例如,使用孩子表示法存储左图中的普通树,则最终存储状态如右图所示:
    在这里插入图片描述
                        图3

    /*
     * @Description: 树的孩子表示法。三部分构成,链表,节点,树
     * @Version: 
     * @Autor: Carlos
     * @Date: 2020-05-21 14:59:47
     * @LastEditors: Carlos
     * @LastEditTime: 2020-06-01 22:47:38
     */ 
    
    #include<stdio.h>
    #include<stdlib.h>
    #define MAX_SIZE 20
    #define TElemType char
    typedef struct CTNode{
        //链表中每个结点存储的不是数据本身,而是数据在数组中存储的位置下标!!
        int child;
        struct CTNode * next;
    }ChildPtr;
    typedef struct {
        //结点的数据类型
        TElemType data;
        //孩子链表的头指针
        ChildPtr* firstchild;
    }CTBox;
    typedef struct{
        //存储结点的数组
        CTBox nodes[MAX_SIZE];
        //结点数量和树根的位置
        int n,r;
    }CTree;
    /**
     * @Description: 孩子表示法存储普通树
     * @Param: CTree tree 树的结构体变量
     * @Return: CTree tree 结构体变量
     * @Author: Carlos
     */
    CTree InitTree(CTree tree){
        printf("输入节点数量:\n");
        scanf("%d",&(tree.n));
        for(int i=0;i<tree.n;i++){
            printf("输入第 %d 个节点的值:\n",i+1);
            fflush(stdin);
            scanf("%c",&(tree.nodes[i].data));
            tree.nodes[i].firstchild=(ChildPtr*)malloc(sizeof(ChildPtr));
            tree.nodes[i].firstchild->next=NULL;
    
            printf("输入节点 %c 的孩子节点数量:\n",tree.nodes[i].data);
            int Num;
            scanf("%d",&Num);
            if(Num!=0){
                //带头结点的链表
                ChildPtr * p = tree.nodes[i].firstchild;
                for(int j = 0 ;j<Num;j++){
                    ChildPtr * newEle=(ChildPtr*)malloc(sizeof(ChildPtr));
                    newEle->next=NULL;
                    printf("输入第 %d 个孩子节点在顺序表中的位置",j+1);
                    scanf("%d",&(newEle->child));
                    p->next= newEle;
                    p=p->next;
                }
            }
        }
        return tree;
    }
    /**
     * @Description:查找节点
     * @Param: CTree tree 树的结构体,char a 要查找的节点
     * @Return: 无
     * @Author: Carlos
     */
    void FindKids(CTree tree,char a){
        int hasKids=0;
        for(int i=0;i<tree.n;i++){
            if(tree.nodes[i].data==a){
                ChildPtr * p=tree.nodes[i].firstchild->next;
                while(p){
                    hasKids = 1;
                    //打印所有孩子节点 p->child 孩子节点在数组中的位置
                    printf("%c ",tree.nodes[p->child].data);
                    p=p->next;
                }
                break;
            }
        }
        if(hasKids==0){
            printf("此节点为叶子节点");
        }
    }
    
    int main()
    {
        CTree tree;
        tree = InitTree(tree);
        //默认数根节点位于数组notes[0]处
        tree.r=0;
        printf("找出节点 F 的所有孩子节点:");
        FindKids(tree,'F');
        return 0;
    }
    
    

    树的孩子兄弟表示法

      树结构中,位于同一层的节点之间互为兄弟节点。例如,图1中的普通树中,节点 A、B 和 C 互为兄弟节点,而节点 D、E 和 F 也互为兄弟节点。
      孩子兄弟表示法,采用的是链式存储结构,其存储树的实现思想是:从树的根节点开始,依次用链表存储各个节点的孩子节点和兄弟节点
      因此,该链表中的节点应包含以下 3 部分内容:
      节点的值;
      指向孩子节点的指针;
      指向兄弟节点的指针;

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
    本文链接:https://blog.csdn.net/qq_16933601/article/details/106483088

    在这里插入图片描述
                        图4
      用 C 语言代码表示节点结构为:

    #define ElemType char
    typedef struct CSNode{
        ElemType data;
        struct CSNode * firstchild,*nextsibling;
    }CSNode,*CSTree;
    
    

      以图1为例,使用孩子兄弟表示法进行存储的结果如下图所示:
    在这里插入图片描述
                        图5
      由图5可以看到,节点 R 无兄弟节点,其孩子节点是 A;节点 A 的兄弟节点分别是 B 和 C,其孩子节点为 D,依次类推。
      实现上图中的 C 语言实现代码也很简单,根据图中链表的结构即可轻松完成链表的创建和使用,因此不再给出具体代码。
      接下来观察图 1 和图 5。图 1 为原普通树,图5 是由图 1 经过孩子兄弟表示法转化而来的一棵树,确切地说,图5是一棵二叉树。因此可以得出这样一个结论,即通过孩子兄弟表示法,任意一棵普通树都可以相应转化为一棵二叉树,换句话说,任意一棵普通树都有唯一的一棵二叉树于其对应。
      因此,孩子兄弟表示法可以作为将普通树转化为二叉树的最有效方法,通常又被称为"二叉树表示法"或"二叉链表表示法"。

    展开全文
  • 首先,按层序输入创建一棵由双亲表示法表示的树,然后把这棵树转化成用孩子兄弟表示法表示的树。
  • 树的存储结构一、双亲表示法 一、双亲表示法 实现:定义数组结构存放树的结点,每个结点含两个域: 数据域:存放结点本身数据信息。 双亲域:指示本结点的双亲结点在数组中的位置。 结点结构表示为: ...
  • 数据结构--树--双亲孩子表示法

    千次阅读 2019-06-19 22:21:52
    双亲孩子表示法就是在每一个结点中添加一个firstchild指针域用来存放孩子链表指针,而且每个节点会有一个存放双亲结点在顺序存储结构中的索引,这样可以更好的查找到每个结点的双亲。但是问题是这得提前给出该树的...
  • 树的双亲孩子表示法、二叉链表

    千次阅读 2019-03-15 14:00:32
    双亲孩子表示法: 把每个结点的孩子结点排列起来,以单链表作存储结构,则n个结点有n个孩子链表,如果是叶子结点则此单链表为空,然后n个头指针又组成一个线性表,采用顺序存储结构,存放一个一维数组中 #...
  • N叉树之孩子双亲表示法 左边是表头结构,相当于一个顺序存储,开始只做了一个顺序结构,发现诸多不便之处,随即开始孩子双亲表示法的学习,这个表示法,需要定义三个结构: 孩子结构 表头结构 树的结构 按理说是...
  • 《数据结构》-树(孩子链表表示法)

    千次阅读 2021-07-25 21:31:28
    孩子链表定义 把每个结点的孩子结点排列起来,看成是一个线性表,且以单链表作为存储结构,则 n 个结点又 n 个孩子链表(叶子的孩子链表为空表)。...双亲结点结构 typedef struct { TElemType data; ChildPtr f
  • 文章目录双亲表示法孩子表示法孩子兄弟法 双亲表示法 实现:定义结构数组存放树的结点,每个结点包含两个域: 数据域:存放结点本身信息 双亲域:指示本结点的双亲结点在数组中的位置 结点结构: 结点类型定义: ...
  • 树的存储_ 双亲表示法双亲孩子表示法

    万次阅读 多人点赞 2017-05-23 16:29:55
    把它叫做“树”是因为它起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:每个节点有零个或多个子节点;没有父节点的节点称为根节点;每一个非根节点有且只有一个父节点;除了根节点外,每...
  • 前文提要: 【数据结构X.5】树、森林的双亲...其他的例如【孩子兄弟】链表表示法转【左孩子右兄弟】的二叉树表示法,【孩子兄弟】链表表示法转【双亲表示法】,都是类似的原理,不再赘述了。 正文: 1.【左孩子右兄弟】
  • 前面讲了如图 1 所示,这是一棵普通的树,该如何...例如,采用双亲表示法存储图 1 中普通树,其存储状态如图 2 所示:图 2 双亲表示法存储普通树示意图图 2 存储普通树的过程转化为 C 语言代码为:#define MAX_SI...
  • 树结构的双亲孩子表示法

    千次阅读 2019-02-25 11:05:58
    该树的深度为3, 其双亲孩子表示法如下: 表中第一列为结点编号,第二列为结点数据,第三列为该节点的双亲编号(根节点双亲为-1),后面的单链表表示了该节点所有的孩子,从左至右依次进行遍历。   代码实现...
  • 数据结构之树的孩子链表表示法

    千次阅读 2018-11-04 08:57:58
    cout 请输入它的双亲的序号" ; cin >> tree.node[i].parent; cout 请输入它孩子的个数" ; cin >> count; if (0 == count) tree.node[i].firstchild = NULL; else { childhead = (ChildPtr)malloc(sizeof(CTNode)); ...
  • 树是一种非线性的数据结构,可以使用链表组织树的各个节点,描述树的一些常用操作。双亲孩子表示法是指每个结点都有一个指向其双亲的指针,每个结点都有若干个指向其孩子的指针。
  • 双亲表示法 双亲表示法的特点就是每一个节点里面除了存放节点数据之外,还存放着该节点的双亲节点位置。 #include<iostream> #define maxTree 100 using namespace std; typedef struct//双亲节点 { string ...
  • 树的双亲表示法:使用顺序表 /*#include<stdio.h> #include<stdlib.h> //节点结构 typedef struct Node { char data; int parent; }Node...
  • 1.双亲表示法: 假设以一组连续空间存储树的结点,同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置,其形式说明如下: 例如,图6.13展示一棵树及其双亲表示的存储结构。 这种存储结构利用了每个结点...
  • 通常,存储具有普通树结构数据的方法有 3 种:双亲表示法;孩子表示法;孩子兄弟表示法;本节先来学习双亲表示法双亲表示法采用顺序表(也就是数组)存储普通树,其实现的核心思想是:顺序存储各个节点的同时,给各...
  • #include<stdio.h> #include<stdlib.h> #define MaxSize 100 ... // 双亲在数组中的下标 }TNode; typedef struct { TNode tree[MaxSize]; // 数组内存静态分配 int NodeNum; ...
  • 双亲表示法孩子表示法孩子兄弟法(二叉树表示法,二叉链表表示法) 树 树(Tree)是n(n≧0)个结点的有限集。若n = 0,称为空树; 若n > 0: (1)有且仅有一个特定的称为根(Root)的结点; (2)其余结点可...
  • 双亲表示法,即储存树结点的同时储存其所属的父结点的表示法,通常利用顺序表(数组)实现。
  • 问题:仿照树的双亲孩子表示法,设计森林的双亲孩子存储结构。要求实现森林的先根、中根、后根遍历,能求森林的规模(森林中树的数目)、森林的高度(森林中树的最大高度)、森林的叶子数(森林中所有树的叶子之和)...
  • 双亲表示法 对应的树为 特点 找双亲容易,找孩子难 C 语言的类型描述 /* 结点结构 */ struct PTNode { TElemType data; int parent; // 双亲位置域 }; /* 树结构 */ struct PTree { PTNode nodes[MAX_TREE_SIZE...
  • 代码及结果截图: #include #include /* 树的存储: 双亲表示法(本质上用数组实现) 孩子表示法(数组+链表) 孩子兄弟表示法(用链表存储 左孩子右兄弟) */ #define ElemType char #define null NULL #define MaxSize 20...
  • } 带双亲的孩子表示法 定义 增加孩子链表来说明结点孩子的位置 该结构涉及到三种结点类型 树 树的结点 孩子链表 # define MAX_SIZE 20 typedef char ElemType; typedef struct Child *pchild; typedef struct Node ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,739
精华内容 2,695
关键字:

双亲链表表示法怎么看

友情链接: Unpacked.rar