【6.3】树的顺序存储结构

树的顺序存储结构:

• 带右链的先根次序表示
• 带双标记的先根次序表示
• 带双标记的层次次序表示
• 带度数的后根次序表示

一、带右链的先根次序表示

结点按先根次序顺序连续存储

• info:结点的数据
• rlink:右指针
• 指向结点的下一个兄弟、即对应的二叉树中结点的右子结点
• ltag:标记
• 树结点没有子结点，即二叉树结点没有左子结点，ltag为 1
• 否则为0

二、带双标记的先根次序表示

带右链的先根次序表示”中rlink也有冗余，可以把 rlink指针替换为一个标志位rtag，成为“带双标记的 先根次序表示”。其中，每个结点包括结点本身数据， 以及两个标志位ltag和rtag，其结点的形式为:

由结点的先根次序以及ltag、rtag两个标志位，就可以 确定树“左孩子/右兄弟”链表中结点的llink和rlink值 。其中llink的确定与带右链的先根次序表示法相同。

从双标记的先根次序恢复树

三、带双标记的层次次序表示法

结点按 层次次序顺序 存储在连续存储单元

• info是结点的数据
• ltag是一个一位的左标记，当结点没有子节点，即对应的二叉树 中结点没有左子结点时， ltag为1，否则为0
• rtag是一个一位的右标记，当结点没有下一个兄弟，即对应的二 叉树中结点没有右子结点时， rtag为1，否则为0

带双标记的层次次序转换为树：

带双标记位的层次次序构造：

四、带度数的后根次序表示

在带度数的后根次序表示中，结点按后根次序顺 序存储在一片连续的存储单元中，结点的形式为

其中info是结点的数据，degree是结点的度数

带度数的后根次序表示法：

带度数的后根次序变成树：

五、思考:森林的顺序存储

• 信息冗余问题
• 树的其他顺序存储
• 带度数的先根次序?
• 带度数的层次次序?
• 二叉树的顺序存储?
• 二叉树与森林对应，但语义不同 。 带右链的二叉树前序；带左链的二叉树层次次序

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾