二叉树的结点度表示法
二叉树的顺序存储结构可看作是二叉树的一种无边表示，即树中边信息是隐含的。二叉树的另一种无边表示称为二叉树的结点度表示。这种表示法将二叉树中所有结点依其后序列表排列，并在每个结点中附加一个0到3之间的整数，以表示结点的状态。该整数为0时，表示相应的结点为一叶结点；为1时，表示相应结点只有一个左儿子；为2时，表示相应结点只有一个右儿子；为3时，表示相应结点有两个儿子。例如，图9(a)中的二叉树的结点度表示如图9(b)所示。
图9 二叉树的结点度表示
在二叉树的结点度表示下，结点土的右儿子很容易找到，因为依后序列表法则，如果结点i有右儿子，它一定排在结点i的前一个，即i-1为其右儿子。找结点i的左儿子和父亲不像找右儿子那样直接。因为我们所知道的只是左儿子在i之前，而父亲在i之后，所以，结点i的左儿子和父亲必须对结点i之前和之后的结点进行搜索才能找到。
说明：这种表示法我不太熟悉，所以运算的实现暂缺。
|
函数 Parent(v,T); 功能
实现 说明 复杂性 |
|
函数 Left_Child(v,T); 功能
实现 说明 复杂性
|
|
函数 Right_Child(v,T); 功能
实现 说明 复杂性
|
|
函数 Create(x,Left,Right,T); 功能
实现 说明 复杂性
|
二叉树的链式存储结构
由于二叉树的每个结点最多有两个儿子，因此存储二叉树的最自然的方法是链接的方法。在用链接方式存储二叉树时，对于每个结点，除了存储结点标号等信息外，还应设置指向结点左右儿子的指针LeftChild和RightChild。结点的类型说明为:
|
Type TPosition=^NodeType; NodeType=record
TreeType=TPosition; |
若用游标来模拟指针，可用一数组来存储二叉树的所有结点，并对此数组作如下说明:
|
Type TPosition=integer; NodeType=record
TreeType=TPosition; var Sellsapce:array [1..MaxNodeCount] of NodeType; {cellspace用来存储结点单元} |
例如，中二叉树，用指针实现的二叉链表和用游标实现的二叉链表分别如图10(a)和(b)所示。
(a)
(b)
图10 二叉树的链式存储结构
若经常要在二叉树中进行Parent操作，可在每个结点上再加一个指向其父结点的指针Parent，形成一个带父亲指针的二叉链表，或称其为一个三叉链表。
三叉链表的类型定义如下：
|
Type TPosition=^NodeType; NodeType=record
TreeType=TPosition; |
若用游标来模拟指针，可用一数组来存储二叉树的所有结点，并对此数组作如下说明:
|
Type TPosition=integer; NodeType=record
TreeType=TPosition; var Cellspace:array [1..MaxNodeCount] of NodeType;{cellspace用来存储结点} |
下面我们就针对三叉链表讨论ADT二叉树基本操作的实现。请注意，下面的三叉链是用指针实现的，用游标实现的三叉链与此类似。
三叉链表实现ADT二叉树基本操作
|
函数 Parent(v,T); 功能
实现
说明
复杂性
|
|
函数 Left_Child(v,T); 功能
实现
说明
复杂性
|
|
函数 Right_Child(v,T); 功能
实现
说明
复杂性
|
|
函数 Create(x,Left,Right,T); 功能
实现
说明
复杂性
|
我们看到，使用这种三叉链表示树，可以在O(1)时间内完成树的大部分操作，所以我们推荐使用这种方法表示树。
果园或森林的二叉树表示
从和可知，一般树和二叉树都可以用二叉链表作为其存储结构。因此，以二叉链表为媒介可以将一棵一般树转换为一棵二叉树。例如，图11(a)中的树可转化为图11(b)中的二叉树，它们具有相同的二叉链表表示。
(a)
(b)
图11 将一棵树转化为二叉树
由可知，与其对应的二叉树根结点的右子树必为空树。因此，如果我们将一个果园中的所有树转换为二叉树，并将第i+1棵树当作第i棵树的根结点的右子树，i=1,2,..，则可将一个果园转换为一棵二叉树。如图12(a)中的果园，经上述转换，变成为图12(c)中的二叉树。
(点击可以放大图形)
图12 果园的二叉树的表示
对于一个森林，可先确定森林中各树的一个排列顺序，将其变成一个果园，然后再用相应的二叉树来表示。
用树的前序和中序遍历可定义果园的前序和中序遍历如下：
若果园非空，则对果园的前序遍历是依序对果园中第i棵树，i=1,2,..，进行前序遍历的结果。
若果园非空，则对果园的中序遍历是依序对果园中第i棵树，i=1,2,..，进行中序遍历的结果。
在前序和中序遍历的意义下，果园和与之相应的二叉树是等价的。
线索二叉树
当时，因为每个结点中只有指向其左、右儿子结点的指针，所以从任一结点出发只能直接找到该结点的左、右儿子。在一般情况下靠它无法直接找到该结点在某种遍历序下的前驱和后继结点。如果在每个结点中增加指向其前驱和后继结点的指针，将降低存储空间的效率。
我们可以证明：在n个结点的二叉链表中含有n+1个空指针。因为含n个结点的二叉链表中含有个指针，除了根结点，每个结点都有一个从父结点指向该结点的指针，因此一共使用了n-1个指针，所以在n个结点的二叉链表中含有n+1个空指针。
因此可以利用这些空指针，存放指向结点在某种遍历次序下的前驱和后继结点的指针。这种附加的指针称为线索，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。为了区分一个结点的指针是指向其儿子的指针，还是指向其前驱或后继结点的线索，可在每个结点中增加两个线索标志。这样，线索二叉树结点类型定义为：
|
type
|
其中ltag为左线索标志，rtag为右线索标志。它们的含义是:
- ltag=0，LeftChild是指向结点左儿子的指针；
- ltag=1，LeftChild是指向结点前驱的左线索。
- rtag=0，RightChild是指向结点右儿子的指针；
- rtag=1，RihgtChild是指向结点后继的右线索。
例如图13(a)是一棵中序线索二叉树，它的线索链表如图13(b)所示。
(a)
(b)
图13 线索二叉树及其线索链表
图13(b)中，在二叉树的线索链表上增加了一个头结点，其LeftChild指针指向二叉树的根结点，其RightChild指针指向中序遍历时的{zh1}一个结点。另外，二叉树中依中序列表的{dy}个结点的LeftChild指针，和{zh1}一个结点的RightChild指针都指向头结点。这就像为二叉树建立了一个双向线索链表，既可从{dy}个结点起，顺着后继进行遍历，也可从{zh1}一个结点起顺着前驱进行遍历。
如何在线索二叉树中找结点的前驱和后继结点？以图13的中序线索二叉树为例。树中所有叶结点的右链是线索，因此叶结点的RightChild指向该结点的后继结点，如图13中结点"b"的后继为结点"*"。当一个内部结点右线索标志为0时，其RightChild指针指向其右儿子，因此无法由RightChild得到其后继结点。然而，由中序遍历的定义可知，该结点的后继应是遍历其右子树时访问的{dy}个结点，即右子树中最左下的结点。例如在找结点"*"的后继时，首先沿右指针找到其右子树的根结点"-"，然后沿其LeftChild指针往下直至其左线索标志为1的结点，即为其后继结点(在图中是结点"c")。类似地，在中序线索树中找结点的前驱结点的规律是：若该结点的左线索标志为1，则LeftChild为线索，直接指向其前驱结点，否则遍历左子树时{zh1}访问的那个结点，即左子树中最右下的结点为其前驱结点。由此可知，若线索二叉树的高度为h，则在最坏情况下，可在O(h)时间内找到一个结点的前驱或后继结点。在对中序线索二叉树进行遍历时，无须像非线索树的遍历那样，利用递归引入栈来保存待访问的子树信息。
对一棵非线索二叉树以某种次序遍历使其变为一棵线索二叉树的过程称为二叉树的线索化。由于线索化的实质是将二叉链表中的空指针改为指向结点前驱或后继的线索，而一个结点的前驱或后继结点的信息只有在遍历时才能得到，因此线索化的过程即为在遍历过程中修改空指针的过程。为了记下遍历过程中访问结点的先后次序，可附设一个指针pre始终指向刚刚访问过的结点。当指针p指向当前访问的结点时，pre指向它的前驱。由此也可推知pre所指结点的后继为p所指的当前结点。这样就可在遍历过程中将二叉树线索化。对于找前驱和后继结点这二种运算而言，线索树优于非线索树。但线索树也有其缺点。在进行插人和删除操作时，线索树比非线索树的时间开销大。原因在于在线索树中进行插人和删除时，除了修改相应的指针外，还要修改相应的线索。
| 已投稿到： |
|
|---|
