多叉树线索化算法的改进

马乐 李晨志 马尧

四川大学/公共管理学院 四川 成都 610000

引言

在经典的二叉树线索化算法改进方面，费洪晓、杨彦等人在改进二叉树线索化方面取得了相应成果，简化了二叉树遍历流程，但是并没有将该改进方法推广至多叉树。

1 传统树的线索化

相比于与一般的树的节点，树的线索化需要构建的节点结构新增加了标识域，数据节点包含5个域，如图1所示：

图1

其中data域存储节点相应数据，ptr是指针域，tag是标识 符，其具体含义如下面公式所示。

以这种方式线索化的树会带有因自身局限性而导致的非连续性，即会存在线索在某一结点中断的情况。具体以前序线索二叉树为例，如图2所示，其中Lc指向节点的左孩子或直接后继，Rc指向节点的右孩子或直接前驱，Lt是Lc的标识符，Rt是Rc的标识符。

图2 先序线索化二叉树

这种二叉树存在不连贯性，导致在遍历整棵树的时候仍需要前序遍历才能找到下一个节点。

2 改进树的线索化

通过观察传统的二叉树线索化方法会发现，之所以会出现线索中断的情况是因为有些节点因为存在左（右）孩子，指针域被占用，导致其不能进行线索化。如果使得一个指针域可以同时满足指向其孩子和指向线索两种功能，这样的不连续性就能得到解决[1-3]。

因为对于二叉树的前序遍历而言，一个节点（非叶子节点）的左孩子就是它的直接后继。因此对于有左孩子的节点，左指针域不仅指向其左孩子，还指向直接后继，而对于叶子节点而言，其左指针域自然也是指向其直接后继。所以在这种改进的方法下，节点的左孩子和直接后继就统一了。Ltag无论是1还是0，节点的Lc始终指向其直接后继。运用改进的算法线索化二叉树如图3所示。

图3 改进的算法线索化二叉树图

改进后的线索化方法与原先相比空间需求没有增加，时间复杂度相同，但是在遍历过程中，旧线索二叉树在遍历某些节点时需要使用遍历非线索二叉树的方法，但新的线索二叉树只需以遍历一个线性链表的方式进行遍历即可。

3 推广到多叉树和代码实现

下面将该方法推广到多叉树，以三叉树为例并附上相应c语言代码。三叉树的线索化需要的节点结构如图4。其中Lc指向左孩子节点，Mc、Rc同理指向中间和右孩子，Lt为该指针域标识符，Mt、Rt依此类推，da为数据域。

图4

c语言代码如下：

typedefstructTNode //定义三叉树节点

{

intda，Lt ， Mt ， Rt ;

《二次函数》是一节概念课，重点内容只有一个，就是二次函数的概念。如何去引入，如何把一个概念表述清楚，让学生真正地理解、弄懂这个概念的来龙去脉，从而加深对它的认识，这是件很不容易的事情，这也是值得我们在进行教学设计时深入思考的地方。在这节课中，笔者主要运用启发式教学法，提出问题进行分析讨论，不严密之处再和学生一起思考和补充，即使对于一些较为困难的问题，也是鼓励和引导学生大胆思考，积极尝试。这样上课气氛非常活跃，学生之间常会因为某个观点的不同而争论，在争论之中也逐步加深了对概念的理解和认识，概念课教学的主要目的也就达到了。

structTNode* Lc ，* Mc;

}TNode;

voidpreThread(TNode* p， TNode*&pre) //前序线索化，其中p是一个已创建好的三叉树

{

if (p != NULL)

{

if (p-＞Lc == NULL)

{

p-＞Lt = 1;

p-＞Lc = p-＞Lc;

}

if (p-＞Mc == NULL) p-＞Mc =NULL;

if (pre != NULL&&pre-＞Rc == NULL)

{

pre-＞Rc = p;

pre-＞Rt = 1;

}

pre = p;

if (p-＞Lc!=NULL)preThread(p-＞Lc， pre);

if(p-＞Mc!=NULL)preThread(p-＞Mc， pre);

if(p-＞Rc!=NULL)preThread(p-＞Rc， pre);

}

}

4 结束语

本文借鉴线索二叉树改进算法，将其推广至多叉树，并给出相应C语言代码。这种改进后的线索化的意义在于：时间和空间复杂度不增加的情况下，线索多叉树的线索不会中断，每个节点都有其后继节点（先序遍历）， 使得对它进行遍历和对线性链表一样方便快捷。