树的孩子表示法，树的兄弟表示法，树的存储结构详解,数据结构-树的学习（2）_以孩子兄弟表示法做存储结构,求树中结点x的第i个孩子

作者：煮酒与君饮 | 2024-08-22 02:03:37

踩

以孩子兄弟表示法做存储结构,求树中结点x的第i个孩子

树的存储结构：
孩子表示法：把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中。
为此，设计两种结点结构，一个是孩子链表的孩子结点    ||child | next|| 另一个是表头数组的表头节点 ||data | firstchild||
#define MAXSIZE 100
typedef struct CTNode /*孩子结点*/
{
    int child;
    struct CTNode *next;
}ChildPtr;

typedef struct    /*表头结构*/
{
    int data;
    ChildPtr firstchild;
}CTBox;

typedef struct    /*树结构*/
{
    CTBox nodes[MAXSIZE];
    int r,n;
}CTree;

这样的结构对于我们要查找某个结点的某个孩子，或者找某个节点的兄弟，只需要查找这个结点的孩子单链表即可。对于遍历整棵树也是很方便，对头结点的数组循环即可。但是这样对于我们查找某一个结点的双亲有点麻烦，这样可以把表头结构里面增加一个双亲域：
typedef struct    /*表头结构*/
{
    int data;
    int parent;
    ChildPtr firstchild;
}CTBox;

孩子兄弟表示法
任意一颗树，它的节点的的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该节点的第一个孩子和此节点的右兄弟：
typedef struct CSNode
{
int data;
struct CSNode *firstchild,*rightbro;
}CSNode;

这样的表示方法最大的好处是它把一颗复杂的树变成了一颗二叉树。

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】