多叉树线索化算法的改进
- 格式：pdf
- 大小：1.42 MB
- 文档页数：3
TECHNOLOGY AND INFORMATION科学与信息化2022年5月下 67多叉树线索化算法的改进
马乐 李晨志 马尧四川大学/公共管理学院 四川 成都 610000摘 要 多叉树作为二叉树的延伸，在管道、网络等规划方面具有重要作用。而线索多叉树充分利用了空置链域，大大提高了空间利用率。本文借鉴重新定义Ltag域和Rtag域的方法，简化树的线索化过程，将其推广至多叉树的线索化并以三叉树为例给出具体代码。关键词 多叉树；线索多叉树；遍历；数据结构Improvement on Threaded Multi-branch Tree AlgorithmMa Le, Li Chen-zhi, Ma YaoSchool of Public Administration, Sichuan University, Chengdu 610000, Sichuan Province, ChinaAbstract As the extension of binary tree, multi-branch tree plays an important role in pipeline and network planning. The threaded multi-branch tree makes full use of the empty chain domain, which greatly improves the spatial utilization. In this article, the method of redefining Ltag domain and Rtag domain is used to simplify the process of tree threading, which is extended to the threading of multi-branch tree and the specific code is given by taking the ternary tree as an example.Key words multi-branch tree; threaded multi-branch tree; traversal; data structure引言在经典的二叉树线索化算法改进方面，费洪晓、杨彦等人在改进二叉树线索化方面取得了相应成果，简化了二叉树遍历流程，但是并没有将该改进方法推广至多叉树。1 传统树的线索化相比于与一般的树的节点，树的线索化需要构建的节点结构新增加了标识域，数据节点包含5个域，如图1所示：
图1其中data域存储节点相应数据，ptr是指针域，tag是标识符，其具体含义如下面公式所示。
以这种方式线索化的树会带有因自身局限性而导致的非连续性，即会存在线索在某一结点中断的情况。具体以前序线索二叉树为例，如图2所示，其中Lc指向节点的左孩子或直接后继，Rc指向节点的右孩子或直接前驱，Lt是Lc的标识符，Rt是Rc的标识符。 TECHNOLOGY AND INFORMATION68
科学与信息化2022年5月下图2 先序线索化二叉树这种二叉树存在不连贯性，导致在遍历整棵树的时候仍需要前序遍历才能找到下一个节点。2 改进树的线索化通过观察传统的二叉树线索化方法会发现，之所以会出现线索中断的情况是因为有些节点因为存在左（右）孩子，指针域被占用，导致其不能进行线索化。如果使得一个指针域可以同时满足指向其孩子和指向线索两种功能，这样的不连续性就能得到解决[1-3]。具体的改进思路是将Ltag和Rtag的功能进行颠倒，即如下
面公式所示：因为对于二叉树的前序遍历而言，一个节点（非叶子节点）的左孩子就是它的直接后继。因此对于有左孩子的节点，左指针域不仅指向其左孩子，还指向直接后继，而对于叶子节点而言，其左指针域自然也是指向其直接后继。所以在这种改进的方法下，节点的左孩子和直接后继就统一了。Ltag无论是1还是0，节点的Lc始终指向其直接后继。运用改进的算法线索化二叉树如图3所示。
图3 改进的算法线索化二叉树图 TECHNOLOGY AND INFORMATION科学与信息化2022年5月下 69改进后的线索化方法与原先相比空间需求没有增加，时间复杂度相同，但是在遍历过程中，旧线索二叉树在遍历某些节点时需要使用遍历非线索二叉树的方法，但新的线索二叉树只需以遍历一个线性链表的方式进行遍历即可。3 推广到多叉树和代码实现下面将该方法推广到多叉树，以三叉树为例并附上相应c语言代码。三叉树的线索化需要的节点结构如图4。其中Lc指向左孩子节点，Mc、Rc同理指向中间和右孩子，Lt为该指针域标识符，Mt、Rt依此类推，da为数据域。
图4c语言代码如下：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语言代码。这种改进后的线索化的意义在于：时间和空间复杂度不增加的情况下，线索多叉树的线索不会中断，每个节点都有其后继节点（先序遍历）， 使得对它进行遍历和对线性链表一样方便快捷。参考文献[1] 尹叶青.三叉树存储结构分析比较[J].广西民族学院学报(自然科学版),2003(2):50-53.[2] 胡树杰,喻红婕.线索二叉树算法的改进[J].沈阳理工大学学报, 2008,27(6):18-20.[3] 严蔚敏,李冬梅,吴伟民.数据结构[M].北京:人民邮电出版社, 2015:281.
