树的存储结构

树的存储结构  树的存贮结构有多种表示方法，比较典型的乃是顺序结构和链表结构两类。  　　顺序存贮结构即向量，一般将树结点按自上而下，自左至右的顺序一一存放。如前文所介绍的完全二叉树就可以采用顺序存贮结构。 1.双亲链表表示法     　顺序存储结构常用的有双亲表示法，这种方法在每个数组元素中存放某个结点信息和该结点的双亲下标值。 （1）双亲链表表示法的实现  方法① 用动态链表实现  方法② 用向量表示——更为方便 （2）双亲链表表示实例   【例】如图6.13（a）所示这棵一般树，它的双亲数组表示法，如图6.13（b）所示。                                   （a）              分析：     　E和F所在结点的双亲域是3，它们的双亲结点在向量中的位置是3，即c是它们的双亲。   注意：     　① 根无双亲，其parent域为-1。     　② 双亲链表表示法中指针parent向上链接，适合求指定结点的双亲或祖先(包括根)；求指定结点的孩子或其它后代时，可能要遍历整个数组。 2.多重链表的孩子表示法 （1） 结点结构 ① 定长结点      　即树中每个结点均按树的度k来设置指针。     　n个结点的树一共有n*k个指针域，而树中只有n-1条边，故树中的空指针数目为          kn-(n-1)=n(k-1)+1（k越大，浪费的空间越多）。 ②不定长结点     　即树中每个结点按本结点的度来设置指针数，并在结点中增设一个度数域degree指出该结点包含的指针数。     　各结点不等长，虽然节省了空间，但是给运算带来不便。 （2）孩子链表表示法     　孩子链表表示法是为树中每个结点设置一个孩子链表，并将这些结点及相应的孩子链表的头指针存放在一个向量中。 （3）孩子链表表示法实例  【例】图 6.13 所示的树是一个三叉树，可用三重链表来存贮，其结点结构为：有一个数据域和三个指针域，指针域用于指向该结点的各个孩子。该树的三重链表如图 6.14 （ a ）所示。如果面对一棵分叉很多的树，这种方法就会更加复杂。             注意：     　① 孩子结点的数据域仅存放了它们在向量空间的序号。     　② 与双亲链表表示法相反，孩子链表表示便于实现涉及孩子及其子孙的运算，但不便于实现与双亲有关的运算。     　③ 将双亲链表表示法和孩子链表表示法结合起来，可形成双亲孩子链表表示法。 3.孩子兄弟链表表示法  （1）表示方法     树最常用的是孩子 - 兄弟二叉链表表示法，这种方法表示规范，不仅适用于多叉树的存储，也适用于森林的存储。构成孩子 - 兄弟二叉链表的结点结构是：一个数据域和两个指针域，一个指针指向它的长子，另一指针指向它的一个兄弟。 （2）表示实例 　　【例】图 6.13 中树的孩子 - 兄弟二叉链表结构如图 6.14(b) 所示。假设把图 6.14(b) 中指向兄弟的水平方向指针改为下斜 45 ℃ ，不难发现它与一棵二叉树十分相似。二叉树结构规范、简单并具有一些重的要性质，因此常将一般树结构转换为二叉树结构进行处理。         注意：     　这种存储结构的最大优点是：它和二叉树的二叉链表表示完全一样。可利用二叉树的算法来实现对树的操作。