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

数据结构目录

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时，表示找到了树结点的根
缺点：
如果我们要知道某结点的孩子是什么，只能遍历整个树结构

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

双亲表示法-孩子

如果我们又比较关心它们兄弟之间的关系呢？那么结构可以改为这样

双亲表示法-兄弟

孩子表示法

由于树中每个结点可能有多棵子树，可以考虑用多重链表来实现，这就有了如下的表示法：

树
孩子表示法

如图所示，每个结点除了存储自身的值与索引外，还增加了一个指针，指向子树的左子树，左子树依次指向右子树，这样，不管是孩子还是兄弟的查找都变得很容易了

双亲孩子表示法

在孩子表示法中，只找到孩子还不够完善，我们合并之前的双亲表示法，就得到了双亲孩子表示法：

双亲孩子表示法