线索二叉树 以你之姓@ 2022-06-09 01:13 232阅读 0赞 线索化二叉树相对于之前的树的遍历,在树的定义上增加了两个值,一个是ltag,另外一个是rtag。 ltag代表着这个节点的是否有右孩子,如果有,则ltag=1,p->lchild指向的是p的左孩子。 如果没有左孩子,那么ltag=0,p->lchild指向的是p的前驱节点。 rtag代表着这个节点的是否有右孩子,如果有,则rtag=1,p->rchild指向的是p的右孩子。 如果没有右孩子,那么rtag=0,p->rchild指向的是p的后继节点。 线索二叉树的定义如下: typedef struct ThreadTree(BiTree T) { ElemType data; struct ThreadTree *lchild,*rchild; int ltag,rtag; }ThreadTree; 首先声明: void CreateThreadTree(ThreadNode T) { ThreadNode pre=NULL,p=T; if(T!=NULL) { ThreadTree(T,pre); pre->rchild =NULL;//处理最后一个节点的右子树 pre->rtag = 0; } } 中序遍历线索化二叉树的递归代码,作用是生成线索化二叉树: void ThreadTree(BiTree &T,BiTree &pre) { if(T) { ThreadTree(T->lchild,pre); if(T->lchild==NULL) { T->lchild = pre; T->ltag = 1; } if(pre!=NULL && pre->lchild!=NULL) { pre->rchild = T; pre->rtag = 1; } pre = T; ThreadTree(T->rchild,pre); } } 线索化二叉树的遍历: 查找第一个节点: ThreadNode FirstNode(ThreadNode T) { while(T->ltag == 0) T=T->lchild; return T; } 一直向最左边进行遍历。直到查找到第一个不为0的,便是中序遍历的第一个字符。 查找节点p的下一个后继节点 ThreadNode NextNode(ThreadNode *p){ if(p->rtag==0) return FirstNode(p->rchild); else return p->rchild; } 整个的树的遍历: ThreadNode InOrder(ThreadNode T){ if(T!=NULL) { for(ThreadNode p = FirstNode(T); p!=NULL ;p = NextNode(p)) visit(p); } }
相关 树——二叉树——线索二叉树 一、线索二叉树 (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 赞/ 293 阅读
相关 线索二叉树 package com.tree; import java.util.concurrent.SynchronousQueue; / 红太狼/ 2021年10月15日 02:37/ 0 赞/ 341 阅读
相关 线索二叉树 Overview 将二叉树中没有子节点的节点称为空指针域,利用二叉树的空指针域,按照前中后某种遍历方式存放对应的前驱节点,后驱节点(这种附加指针称为“线索”)。二叉树的空 矫情吗;*/ 2021年10月01日 09:34/ 0 赞/ 393 阅读
还没有评论,来说两句吧...