双亲表示法树的存储结构之双亲表示法的表头结构超详细简单易懂~~

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)
{
///注意双亲表示法很容易找到双亲是真，但是很难找到各结点的孩子
}

c语言数据结构

更多相关内容
树的三种表示法：双亲表示法、孩子表示法、孩子兄弟表示法
千次阅读 2020-03-25 13:48:52
介绍三种不同的表示法：双亲表示法、孩子表示法、孩子兄弟表示法。 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
收起
展开全文

树的双亲表示法(链表实现) -A

2021-11-15 23:19:07

采用链表实现树的双亲表示法(带头结点). 树结点: 数据域 & 双亲域 & 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

收起

展开全文

数据结构 c语言

树的双亲表示法，孩子表示法以及孩子兄弟表示法

千次阅读 多人点赞 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是一棵二叉树。因此可以得出这样一个结论，即通过孩子兄弟表示法，任意一棵普通树都可以相应转化为一棵二叉树，换句话说，任意一棵普通树都有唯一的一棵二叉树于其对应。
因此，孩子兄弟表示法可以作为将普通树转化为二叉树的最有效方法，通常又被称为"二叉树表示法"或"二叉链表表示法"。

收起

展开全文

数据结构与算法分析二叉树 C语言

假设有n个结点的树T采用了双亲表示法，写出由此建立一般树的二叉树表示法的存储结构，即CS（链表）表示法。
2021-12-01 12:55:34

首先，按层序输入创建一棵由双亲表示法表示的树，然后把这棵树转化成用孩子兄弟表示法表示的树。

收起

数据结构二叉树
双亲表示法、孩子表示法、孩子兄弟表示法(二叉树表示法)，森林和二叉树的转换
万次阅读 多人点赞 2020-01-22 12:23:20

树的存储结构一、双亲表示法 一、双亲表示法 实现：定义数组结构存放树的结点，每个结点含两个域：数据域：存放结点本身数据信息。双亲域：指示本结点的双亲结点在数组中的位置。结点结构表示为： ...

收起
数据结构--树--双亲孩子表示法
千次阅读 2019-06-19 22:21:52

双亲孩子表示法就是在每一个结点中添加一个firstchild指针域用来存放孩子链表指针，而且每个节点会有一个存放双亲结点在顺序存储结构中的索引，这样可以更好的查找到每个结点的双亲。但是问题是这得提前给出该树的...

收起
树的双亲孩子表示法、二叉链表
千次阅读 2019-03-15 14:00:32

双亲孩子表示法：把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空，然后n个头指针又组成一个线性表，采用顺序存储结构，存放一个一维数组中 #...

收起
数据结构——树|N叉树之孩子双亲表示法——顺序存储结构+链表
千次阅读 2020-12-27 16:01:11

N叉树之孩子双亲表示法 左边是表头结构，相当于一个顺序存储，开始只做了一个顺序结构，发现诸多不便之处，随即开始孩子双亲表示法的学习，这个表示法，需要定义三个结构：孩子结构表头结构树的结构按理说是...

收起

数据结构
《数据结构》-树(孩子链表表示法)
千次阅读 2021-07-25 21:31:28

孩子链表定义把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作为存储结构，则 n 个结点又 n 个孩子链表(叶子的孩子链表为空表)。...双亲结点结构 typedef struct { TElemType data; ChildPtr f

收起

数据结构
树的存储结构：双亲表示法、孩子表示法、孩子兄弟法
千次阅读 2020-02-05 14:17:29

文章目录双亲表示法孩子表示法孩子兄弟法 双亲表示法 实现：定义结构数组存放树的结点，每个结点包含两个域：数据域：存放结点本身信息双亲域：指示本结点的双亲结点在数组中的位置结点结构：结点类型定义： ...

收起

数据结构
树的存储_ 双亲表示法 及双亲孩子表示法
万次阅读 多人点赞 2017-05-23 16:29:55

把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每...

收起

数据结构与算法树结构
代码实现：左孩子右兄弟表示法转换为树的双亲表示法，左孩子右兄弟表示法转化为树的孩子兄弟链表表示法，...
千次阅读 2020-12-05 22:39:59

前文提要: 【数据结构X.5】树、森林的双亲...其他的例如【孩子兄弟】链表表示法转【左孩子右兄弟】的二叉树表示法，【孩子兄弟】链表表示法转【双亲表示法】，都是类似的原理，不再赘述了。正文： 1.【左孩子右兄弟】

收起

二叉树算法树结构数据结构
树的双亲表示法（C语言实现详解版）
2021-05-19 19:12:30

前面讲了如图 1 所示，这是一棵普通的树，该如何...例如，采用双亲表示法存储图 1 中普通树，其存储状态如图 2 所示：图 2 双亲表示法存储普通树示意图图 2 存储普通树的过程转化为 C 语言代码为：#define MAX_SI...

收起
树结构的双亲孩子表示法
千次阅读 2019-02-25 11:05:58

该树的深度为3，其双亲孩子表示法如下：表中第一列为结点编号，第二列为结点数据，第三列为该节点的双亲编号（根节点双亲为-1），后面的单链表表示了该节点所有的孩子，从左至右依次进行遍历。代码实现...

收起

数据结构 C语言
数据结构之树的孩子链表表示法
千次阅读 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)); ...

收起

数据结构
数据结构之通用树（使用链表实现树的存储结构，双亲孩子表示法）
千次阅读 2017-07-28 22:39:46

树是一种非线性的数据结构，可以使用链表组织树的各个节点，描述树的一些常用操作。双亲孩子表示法是指每个结点都有一个指向其双亲的指针，每个结点都有若干个指向其孩子的指针。

收起

数据结构存储回调函数
C++ 树、树的存储结构（双亲表示法，孩子表示法，双亲孩子表示法）
千次阅读 2020-08-18 11:18:37

双亲表示法 双亲表示法的特点就是每一个节点里面除了存放节点数据之外，还存放着该节点的双亲节点位置。 #include<iostream> #define maxTree 100 using namespace std; typedef struct//双亲节点 { string ...

收起

树结构数据结构算法
树的双亲表示法，孩子表示法，孩子兄弟表示法（C语言）
2019-08-10 21:22:00

树的双亲表示法：使用顺序表 /*#include<stdio.h> #include<stdlib.h> //节点结构 typedef struct Node { char data; int parent; }Node...

收起
数据结构c语言——树的三种存储结构（双亲表示法、孩子表示法、兄弟表示法）
千次阅读 2020-06-20 12:06:06

1.双亲表示法：假设以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置,其形式说明如下: 例如，图6.13展示一棵树及其双亲表示的存储结构。这种存储结构利用了每个结点...

收起
树的双亲表示法（包含C语言实现代码）
2021-03-15 16:22:20

通常，存储具有普通树结构数据的方法有 3 种：双亲表示法；孩子表示法；孩子兄弟表示法；本节先来学习双亲表示法。双亲表示法采用顺序表(也就是数组)存储普通树，其实现的核心思想是：顺序存储各个节点的同时，给各...

收起
树的双亲表示法（C语言实现）——树的存储结构
2021-10-27 22:11:39

#include<stdio.h> #include<stdlib.h> #define MaxSize 100 ... // 双亲在数组中的下标 }TNode; typedef struct { TNode tree[MaxSize]; // 数组内存静态分配 int NodeNum; ...

收起

数据结构 c语言
树——组成层次结构的集合|双亲表示法、孩子表示法、孩子兄弟法
2020-04-24 21:27:15

双亲表示法孩子表示法孩子兄弟法（二叉树表示法，二叉链表表示法）树树（Tree）是n（n≧0）个结点的有限集。若n = 0，称为空树；若n > 0：（1）有且仅有一个特定的称为根（Root）的结点；（2）其余结点可...

收起

数据结构二叉树单链表树结构
二叉树练习（二）：树的双亲表示法及其部分算法实现
2021-10-09 18:34:28

双亲表示法，即储存树结点的同时储存其所属的父结点的表示法，通常利用顺序表（数组）实现。

收起

算法数据结构树结构
森林的双亲孩子表示法的设计与实现
2020-07-11 20:03:01

问题：仿照树的双亲孩子表示法，设计森林的双亲孩子存储结构。要求实现森林的先根、中根、后根遍历，能求森林的规模（森林中树的数目）、森林的高度（森林中树的最大高度）、森林的叶子数（森林中所有树的叶子之和）...

收起

数据结构二叉树
《数据结构》-树(双亲表示法)
2021-07-25 19:42:00

双亲表示法 对应的树为特点找双亲容易，找孩子难 C 语言的类型描述 /* 结点结构 */ struct PTNode { TElemType data; int parent; // 双亲位置域 }; /* 树结构 */ struct PTree { PTNode nodes[MAX_TREE_SIZE...

收起
树的存储(双亲表示法)
2021-08-04 10:19:54

代码及结果截图: #include #include /* 树的存储: 双亲表示法(本质上用数组实现) 孩子表示法(数组+链表) 孩子兄弟表示法(用链表存储左孩子右兄弟) */ #define ElemType char #define null NULL #define MaxSize 20...

收起
【数据结构 | C语言】树的存储结构（双亲表示法、带双亲的结点表示法、结点兄弟表示法） C语言实现
2022-01-14 15:41:38

} 带双亲的孩子表示法 定义增加孩子链表来说明结点孩子的位置该结构涉及到三种结点类型树树的结点孩子链表 # define MAX_SIZE 20 typedef char ElemType; typedef struct Child *pchild; typedef struct Node ...

收起

数据结构 c语言

树的三种表示法：双亲表示法、孩子表示法、孩子兄弟表示法

抽象数据类型：

树的存储结构：

1.双亲表示法

2.孩子表示法

方案一

方案二

3.孩子兄弟表示法

树的双亲表示法(链表实现) -A

简述说明

存储结构

c语言实现代码

树的双亲表示法，孩子表示法以及孩子兄弟表示法

文章目录

树的双亲表示法

树的孩子表示法

树的孩子兄弟表示法

假设有n个结点的树T采用了双亲表示法，写出由此建立一般树的二叉树表示法的存储结构，即CS（链表）表示法。

双亲表示法、孩子表示法、孩子兄弟表示法(二叉树表示法)，森林和二叉树的转换

数据结构--树--双亲孩子表示法

树的双亲孩子表示法、二叉链表

数据结构——树|N叉树之孩子双亲表示法——顺序存储结构+链表

《数据结构》-树(孩子链表表示法)

树的存储结构：双亲表示法、孩子表示法、孩子兄弟法

树的存储_ 双亲表示法 及 双亲孩子表示法

代码实现：左孩子右兄弟表示法转换为树的双亲表示法，左孩子右兄弟表示法转化为树的孩子兄弟链表表示法，...

树的双亲表示法（C语言实现详解版）

树结构的双亲孩子表示法

数据结构之树的孩子链表表示法

数据结构之通用树（使用链表实现树的存储结构，双亲孩子表示法）

C++ 树、树的存储结构（双亲表示法，孩子表示法，双亲孩子表示法）

树的双亲表示法，孩子表示法，孩子兄弟表示法（C语言）

数据结构c语言——树的三种存储结构（双亲表示法、孩子表示法、兄弟表示法）

树的双亲表示法（包含C语言实现代码）

树的双亲表示法（C语言实现）——树的存储结构

树——组成层次结构的集合|双亲表示法、孩子表示法、孩子兄弟法

二叉树练习（二）：树的双亲表示法及其部分算法实现

森林的双亲孩子表示法的设计与实现

《数据结构》-树(双亲表示法)

树的存储(双亲表示法)

【数据结构 | C语言】树的存储结构（双亲表示法、带双亲的结点表示法、结点兄弟表示法） C语言实现

双亲链表表示法怎么看

树的存储_ 双亲表示法及双亲孩子表示法