六、树(二)、树的存储结构

2020-06-02 本文已影响0人默默_David

数据结构目录

1.树三种不同的表示法：

双亲表示法
孩子表示法
孩子兄弟表示法

双亲表示法

双亲表示法，就是以双亲作为索引的关键词的一种存储方式
我们假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示其双亲结点在数组中位置的元素
也就是说，每个结点除了知道自己是谁之外，还知道它的双亲在哪里

双亲表示法

定义:

// 树的双亲表示法结点结构定义
#define MAX_TREE_SIZE 100

typedef int ElemType;

typedef struct PTNode
{
    ElemType data;  // 结点数据
    int parent;     // 双亲位置(下标)
}PTNode;

typedef struct
{
    PTNode nodes[MAX_TREE_SIZE];
    int r;          // 根的位置(下标)
    int n;          // 结点数目
}PTree;

双亲表示法这样的存储结构，我们可以根据某结点的parent指针找到它的双亲结点，所用的时间复杂度为O(1),索引到parent位-1时，表示找到了树结点的根
缺点：
如果我们要知道某结点的孩子是什么，只能遍历整个树结构

那我们对这个结构做如下改进，每个结点添加孩子的下标：