|
|
知识路径： > 计算机科学基础 > 数据结构与算法基本概念 > 数据结构与算法 > 树和二叉树 >
|
|
相关知识点：8个
|
|
|
|
|
存储结构的选择不仅要考虑数据元素如何存储，更重要的是要考虑数据元素之间的关系如何体现。根据数据元素之间关系的不同表示方式，常用的树存储结构主要有三种：双亲表示法、孩子表示法和孩子兄弟表示法。本节主要讨论树的双亲表示法，如下图所示。
|
|
|
|
|
|
|
|
在树中，除根结点没有双亲外，其他每个结点的双亲是唯一确定的。因此，根据树的这种性质，存储树中结点时，应该包含两个信息：结点的值data和体现结点之间相互关系的属性——该结点的双亲parent。借助于每个结点的这两个信息便可唯一地表示任何一棵树。这种表示方法称为双亲表示法，为了查找方便，可以将树中所有结点存放在一个一维数组中，具体类型定义如下。
|
|
|
|
|
|
其中datatype应根据结点值的具体类型给出定义，在此假设为字符型。这里值得一提的是，根结点在树中有着与其他结点不同的地位，树根的位置是非常关键的，正如单链表中抓住了表头指针，就掌握了整个链表一样，树中只要知道树根在哪里，便可以访问到树中所有的结点，因此树的存储结构中要特别考虑根结点的存储。
|
|
|
|
其中parent的值为-1表示结点的双亲不存在。本树中root域的值为0,表示树的根结点存放在数组的第一个元素中。
|
|
|
