线索二叉树算法的实验与实现

郭小春，王 红

(1.泰山学院信息科学技术学院，山东泰安 271021;2.泰山职业技术学院财经系，山东泰安 271000)

在计算机科学中，数据结构是一个重要的基础理论.它在软件开发及程序设计中都有着不可替代的应用价值.二叉树是一种重要的数据结构，它的应用范围非常广泛.不仅在程序设计中，而且在图像处理和模式识别等诸多新学科中也有很重要的应用［1－2］，它是数据结构中目前很活跃的研究课题之一，而对二叉树加线索使其成为线索二叉树是简化二叉树各种操作的重要手段.

遍历二叉树是以一定规则将二叉树中结点排列成一个线性序列，得到二叉树中结点的先序序列、中序序列或后序序列.这实质上是对一个非线性结构进行线性化操作，使每个结点(除第一个和最后一个外)在这些线性序列中有且仅有一个直接前驱和直接后继.但是，当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直接得到结点在任一序列中的前驱和后继信息，这种信息只有在遍历的动态过程中才能得到.解决这个问题的方法是:当第一次遍历二叉树时，就在各结点的空余域中加线索，加线索的二叉树就称为线索二叉树.加线索之后，当再遍历时，就可在某些结点沿着线索走，从而简化操作［3－8］.

经过算法分析和实验发现现有绝大部分“数据结构”教科书中对二叉树的线索化实现算法存在错误，没有对线索树中非线索结点的LTag和RTag的指针赋值.为了解决这一问题提高数据结构课程在理论方面教学的严格性和实用性，对二叉树线索化的算法进行了修正和实现.

1 线索二叉树的基础知识

n个结点的二叉链表中含有n+1个空指针域.利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针(这种附加的指针称为“线索”).加上线索的二叉树称为线索二叉树，对二叉树以某种次序使其变为线索二叉树的过程叫做线索化.对二叉树的遍历过程可以有先序、中序和后序三种顺序，相应的二叉树的线索化也有三种顺序，分别称之为先序线索化、中序线索化和后序线索化.

线索二叉树的结点的存储结构及意义如下:若结点有左子树，则其lchild域指示其左孩子，否则令lchild指示其前驱;若结点有右子树，则其rchild域指示其右孩子，否则令rchild域指示其后继.

其中:

C语言表述的存储结构如下:

2 线索二叉树的实验研究

在对线索化的二叉树遍历过程中发现大部分“数据结构”教材中实现二叉树线索化的算法存在问题，容易引起死机.通过反复实验，发现原来教材中没有对线索树中非线索结点的LTag和RTag的指针赋值.以中序线索化为例［3］，原程序如下:

其中pre指向当前访问的结点p的前驱.在别的教科书也同样存在这个问题.

3 二叉树线索化算法的修正

对原算法做出了修正，以中序线索化为例，修改后的程序如下:

当当前结点p有左孩子的时候，让其左孩子的LTag标志域为Link.当当前结点p有右孩子的时候，让其右孩子的RTag标志域为Link.

4 修正后的二叉树算法线索化算法的实验证明

用VC++对修改后的算法进行了实验验证，以二叉树中序线索化算法为例.为了明确的输出图形，更好查看结果，论文对原数据结构做出了修改，加入了结点的位置信息.修改如下:

修正后的算法实现如下:

程序输入的原二叉树如图1所示:

图1 程序中输入的二叉树

运行程序后得到的遍历结果如图2所示:

图2 二叉树中序线索化结果

实验证明，该程序经改正后算法运行是正确的、可行的.

5 结束语

在实验过程中，论文针对“数据结构”课程中二叉树的线索化算法中出现的指针未定义指向的问题进行了研究，给出了解决方案，并通过实践证明改正的正确性、可行性.对提高“数据结构”课程在理论方面教学的严格性和实用性具有一定的意义.

［1］T.Pavlidis.Algorithms for Graphies and Image Processing，Computer Science Press，1982.

［2］傅京孙.模式识别及其应用［M］.北京:科学出版社，1985.

［3］严蔚敏，吴伟民.数据结构(C语言版)［M］.北京:清华大学出版社，1997.

［4］谭卓群，杨冬青，唐世渭，等.数据结构与算法［M］.北京:高等教育出版社，2005

［5］王国均.数据结构－C语言描述［M］.北京:科学出版社，2005.

［6］严蔚敏.数据结构与算法分析［M］.北京:清华大学出版社，2004.

［7］吉根林，林波.数据结构教程(C++版)［M］.北京:电工工业大学出版社，2009.

［8］耿国华.数据结构—C语言描述［M］.北京:高等教育出版社，2005.