线索二叉树 女爷i 2022-01-23 08:15 293阅读 0赞 ### 什么是线索二叉树? ### **遍历二叉树**是以一定的规则将二叉树中的结点排列成一个线性序列,从而等到二叉树的各种遍历序列,其实质是对一个非线性操作进行线性化操作,使这个访问序列中的每一个结点(去除第一个和最后一个)都有一个之直接前驱和直接后继。 **我们发现在二叉链表表示的二叉树中存在大量的空指针,若利用这些空指针存放指向其直接前驱和直接后继的节点,那么可以更方便的运用某些二叉树操作算法。** ### 为什么要引入线索二叉树? ### 为了加快查找结点前驱和后继的访问速度。 ### 怎么进行线索化? ### 规定:若无左子树,令lchild指向其前驱结点;若无右子树,令rchild指向其后继结点。这样的话,需要增加两个标志域表明当前指针域所指对象是指向左(右)孩子结点还是指向直接前驱(后继)。 ### 线索二叉树的结点结构 ### 从怎么进行线索化中估计大家能看出来。 <table> <thead> <tr> <th><span><span><span> l t a g ltag </span><span><span><span style="height: 0.88888em; vertical-align: -0.19444em;"></span><span style="margin-right: 0.01968em;">l</span><span>t</span><span>a</span><span style="margin-right: 0.03588em;">g</span></span></span></span></span></th> <th><span><span><span> l c h i l d lchild </span><span><span><span style="height: 0.69444em; vertical-align: 0em;"></span><span style="margin-right: 0.01968em;">l</span><span>c</span><span>h</span><span>i</span><span style="margin-right: 0.01968em;">l</span><span>d</span></span></span></span></span></th> <th><span><span><span> d a t a data </span><span><span><span style="height: 0.69444em; vertical-align: 0em;"></span><span>d</span><span>a</span><span>t</span><span>a</span></span></span></span></span></th> <th><span><span><span> r c h i l d rchild </span><span><span><span style="height: 0.69444em; vertical-align: 0em;"></span><span style="margin-right: 0.02778em;">r</span><span>c</span><span>h</span><span>i</span><span style="margin-right: 0.01968em;">l</span><span>d</span></span></span></span></span></th> <th><span><span><span> r t a g rtag </span><span><span><span style="height: 0.80952em; vertical-align: -0.19444em;"></span><span style="margin-right: 0.02778em;">r</span><span>t</span><span>a</span><span style="margin-right: 0.03588em;">g</span></span></span></span></span></th> </tr> </thead> <tbody></tbody> </table> 其中,标志域的含义如下: l t a g \{ 0 , lchild域指向结点的左孩子 1 , lchild域指向结点的前驱 r t a g \{ 0 , rchild域指向结点的左孩子 1 , rchild域指向结点的后继 ltag \\begin\{cases\} 0, & \\text\{lchild域指向结点的左孩子\} \\\\ 1, & \\text\{lchild域指向结点的前驱\} \\end\{cases\} rtag \\begin\{cases\} 0, &\\text\{rchild域指向结点的左孩子\}\\\\ 1, &\\text\{rchild域指向结点的后继\} \\end\{cases\} ltag\{ 0,1,lchild域指向结点的左孩子lchild域指向结点的前驱rtag\{ 0,1,rchild域指向结点的左孩子rchild域指向结点的后继 ### 相关代码 ### #### 1. 先序线索二叉树 #### #include <iostream> #include <string> using namespace std; typedef char ElemType; typedef struct ThreadNode { ElemType data; struct ThreadNode *lchild, *rchild; int ltag, rtag; ThreadNode(){ ltag = 0, rtag = 0; }; }ThreadNode, *ThreadTree; // 根据先序遍历序列和中序遍历序列建树 ThreadTree createTree(string s1, string s2) { if (s1 == "" || s2 == "") return NULL; ThreadTree tree = new ThreadNode(); tree->data = s1[0]; int m = 0; while (m < s2.size() && s2[m] != s1[0]) m++; tree->lchild = createTree(string(s1.begin() + 1, s1.begin() + 1 + m), string(s2.begin(), s2.begin() + m)); tree->rchild = createTree(string(s1.begin() + 1 + m, s1.end()), string(s2.begin() + m + 1, s2.end())); return tree; } // 遍历结点 void visit(ThreadTree p) { cout << p->data << " "; return; } // 递归创建先序线索二叉树 void FirstThread(ThreadTree &tree, ThreadTree &pre) { if (tree) { if (!tree->lchild){ tree->lchild = pre; tree->ltag = 1; } if (pre && !pre->rchild) { pre->rchild = tree; pre->rtag = 1; } pre = tree; if(!tree->ltag) FirstThread(tree->lchild, pre); if(!tree->rtag) FirstThread(tree->rchild, pre); } return; } // 创建先序线索二叉树主程序 void createFristOrder(ThreadTree &tree) { if (!tree) return; ThreadTree pre = NULL; FirstThread(tree, pre); pre->rchild = NULL; pre->rtag = 1; return; } // 查找先序线索二叉树指定结点的下一个结点 ThreadTree nextNode(ThreadTree p) { if (p->ltag) return p->rchild; return p->lchild; } // 先序遍历 先序线索二叉树 void firstThreadOrder(ThreadTree tree) { if (!tree) return; for (ThreadTree it = tree; it; it = nextNode(it)) { visit(it); } cout << endl; return; } int main() { ThreadTree tree = createTree("abdce", "bdaec"); createFristOrder(tree); firstThreadOrder(tree); return 0; } #### 2. 中序线索二叉树 #### #include <iostream> #include <string> using namespace std; typedef char ElemType; typedef struct ThreadNode { ElemType data; struct ThreadNode *lchild, *rchild; int ltag, rtag; ThreadNode(){ ltag = 0, rtag = 0; }; }ThreadNode, *ThreadTree; // 根据先序遍历序列和中序遍历序列建树 ThreadTree createTree(string s1, string s2) { if (s1 == "" || s2 == "") return NULL; ThreadTree tree = new ThreadNode(); tree->data = s1[0]; int m = 0; while (m < s2.size() && s2[m] != s1[0]) m++; tree->lchild = createTree(string(s1.begin() + 1, s1.begin() + 1 + m), string(s2.begin(), s2.begin() + m)); tree->rchild = createTree(string(s1.begin() + 1 + m, s1.end()), string(s2.begin() + m + 1, s2.end())); return tree; } // 遍历结点 void visit(ThreadTree p) { cout << p->data << " "; return; } // 递归创建中序线索化二叉树 void InThread(ThreadTree &tree, ThreadTree &pre) { if (tree) { InThread(tree->lchild, pre); if (!tree->lchild){ tree->lchild = pre; tree->ltag = 1; } if (pre && !pre->rchild){ pre->rchild = tree; pre->rtag = 1; } pre = tree; InThread(tree->rchild, pre); } return; } // 中序线索化二叉树 void createInThread(ThreadTree &tree) { if (!tree) return; ThreadTree pre = NULL; InThread(tree, pre); pre->rchild = NULL; pre->rtag = 1; } // 求中序线索二叉树中中序序列的第一个结点 ThreadTree firstNode(ThreadTree tree) { while (tree->ltag == 0) tree = tree->lchild; return tree; } // 求中序线索二叉树在中序序列下的后继结点 ThreadTree nextNode(ThreadTree p) { if (p->rtag) return p->rchild; return firstNode(p->rchild); } // 遍历中序线索二叉树 void inThreadOrder(ThreadTree tree) { if (!tree) return; for (ThreadTree it = firstNode(tree); it; it = nextNode(it)){ visit(it); } cout << endl; return; } int main() { ThreadTree tree = createTree("abdce", "bdaec"); createInThread(tree); inThreadOrder(tree); return 0; } #### 3. 后序线索二叉树 #### 参考:[https://blog.csdn.net/My\_heart\_/article/details/52087948][https_blog.csdn.net_My_heart_article_details_52087948] 后序线索化二叉树有一个比较关键的问题,就是使用后序线索二叉树进行遍历的时候需要知道结点的父节点,因此需要给结构体加上一个父节点域,才能发挥后序线索二叉树的作用,而后序线索二叉树的线索化和先序、中序是一样的。 ### 关于2020王道课后习题 ### ##### 题目描述 ##### 查找在中序线索二叉树中的一个结点在后序遍历序列下的前驱结点。 ##### 思路分析 ##### 分为四种情况: 1. 当前结点有右孩子。则右孩子即为当前结点在后序遍历序列下的前驱结点。 2. 当前结点无右孩子,有左孩子。则左孩子即为当前结点在后序遍历序列下的前驱结点。 3. 当前结点没有孩子,并且是中序遍历的第一个结点。那么他也是后序遍历序列下的第一个结点。 4. 当前结点没有孩子,不是中序遍历序列的第一个结点。那么当前一直在当前结点在中序序列中的祖先中找到一个有左孩子的结点,那个左孩子就是当前结点在后序遍历序列下的前驱结点。 ##### 代码 ##### // 查找指定结点在后序序列中的前驱结点 ThreadTree findPreInLastOrder(ThreadTree tree, ThreadTree p) { if (!p->rtag) return p->rchild; if (!p->ltag) return p->lchild; if (p->lchild == NULL) return NULL; while (p->ltag == 1 && p->lchild != NULL) p = p->lchild; if (!p->ltag) return p->lchild; return NULL; } [https_blog.csdn.net_My_heart_article_details_52087948]: https://blog.csdn.net/My_heart_/article/details/52087948
相关 树——二叉树——线索二叉树 一、线索二叉树 (1)什么是线索化 将二叉树以某种次序将其遍历, 得到线性序列, 就是将非线性结构进行线索化。 线索化的优点就是可以很快地得到前驱或后继。 如 梦里梦外;/ 2023年06月13日 09:35/ 0 赞/ 40 阅读
相关 线索二叉树 一 概述 遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列,从而得到几种遍历序列,使得该序列中的每个结点(第一个和最后一个结点除外)都有一个直接前驱和直接后继。 ﹏ヽ暗。殇╰゛Y/ 2022年12月09日 02:46/ 0 赞/ 30 阅读
相关 线索二叉树 1.基本概念 对于某些二叉树而言,其指针域的空间不能被充分利用。因此我们可以考虑利用那些空的指针域来存放指向结点在某种遍历次序下的前驱和后继结点的地址。我们把这种指向前 怼烎@/ 2022年06月14日 03:48/ 0 赞/ 202 阅读
相关 线索二叉树 线索化二叉树相对于之前的树的遍历,在树的定义上增加了两个值,一个是ltag,另外一个是rtag。 ltag代表着这个节点的是否有右孩子,如果有,则ltag=1,p->lchi 以你之姓@/ 2022年06月09日 01:13/ 0 赞/ 233 阅读
相关 线索二叉树 二叉树的链式存储如下图, ![Image 1][] 不难发现,图中所示的左—右指针表示中,有一半以上的指针是空的。事实上,所有包括n个结点的二叉树的这种表示中,每个结 秒速五厘米/ 2022年05月29日 00:18/ 0 赞/ 193 阅读
相关 线索二叉树 线索二叉树提出的原因: 在普通二叉树中,每个结点都有左右两个指针域,这些指针域都指向结点类型的数据对象,当二叉树稀疏时,很多结点的左右两个指针域就显得浪费存储空间了。因此,提 待我称王封你为后i/ 2022年03月15日 13:24/ 0 赞/ 292 阅读
相关 线索二叉树 本文主要介绍线索二叉树和树、二叉树、森林三者之间的相互转换。 对于线索二叉树,这里只做简单介绍,着重还是要理解上篇博文中二叉树的各种遍历算法。 线索二叉树 基本概念 旧城等待,/ 2022年02月23日 08:36/ 0 赞/ 263 阅读
相关 线索二叉树 什么是线索二叉树? 遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列,从而等到二叉树的各种遍历序列,其实质是对一个非线性操作进行线性化操作,使这个访问序列中的每 女爷i/ 2022年01月23日 08:15/ 0 赞/ 294 阅读
相关 线索二叉树 package com.tree; import java.util.concurrent.SynchronousQueue; / 红太狼/ 2021年10月15日 02:37/ 0 赞/ 341 阅读
相关 线索二叉树 Overview 将二叉树中没有子节点的节点称为空指针域,利用二叉树的空指针域,按照前中后某种遍历方式存放对应的前驱节点,后驱节点(这种附加指针称为“线索”)。二叉树的空 矫情吗;*/ 2021年10月01日 09:34/ 0 赞/ 393 阅读
还没有评论,来说两句吧...