线索二叉树,画图教你秒懂线索二叉树(线索二叉树的建立和简单操作)逻辑代码分析 |
您所在的位置:网站首页 › 什么是树的结点 › 线索二叉树,画图教你秒懂线索二叉树(线索二叉树的建立和简单操作)逻辑代码分析 |
数据结构专升本学习,线索二叉树
前言
前面我们学习树和二叉树的一些基本操作,今天我们学习一个新的知识,学习一下线索二叉树,线索二叉树是由二叉链存储结构变化而来的(我们先得有个二叉链树,再做处理),就是将原来的空域链改为莫种遍历次序下该结点的前驱结点和后继结点的指针,就相当于把我们的空域也利用起来指向下一个要输出的结点,对于下一个结点提高了访问速度,emmm,有点难,博主也有点云里雾里,看博主的解释能不能让你理解。嘿嘿 每日一遍,快乐学习你们第一次炒菜是不是也是这个样纸!!!!哈哈哈哈 1.什么是线索二叉树对于n个结点的二叉树,在二叉链存储结构中有n+1个空链域,利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针,这些指针称为线索,加上线索的二叉树称为线索二叉树。这种加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同,线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。注意:线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题,解决了二叉链表找左、右孩子困难的问题。讲人话就是:(假设一个链式二叉树采用先序遍历,遍历到了叶子结点的时候发现有两个空指针域,我们前驱指向上一个遍历过的结点,后继指向先序遍历时这个结点需要遍历的下一个结点,形成线索) 2.线索二叉树的存储结构线索二叉树主要是针对三种遍历去实现的,分别是先序中序后序遍历,线索二叉树的结点是由五个变量来表示的,为了区分左子树和右子树,我们有两个指针指向,一个前驱一个后继,为了区别这个指针是否是空指针域,我们还需要两个标记值,我们采用ltag和rltag来标记,结点结构如图: 博主用的是中序遍历来对二叉树进行的线索化 3.1初始化线索二叉树的类型先销毁原来的二叉链,最后释放头结点。 void DestroyBTree1(BthNode *&b) { if (b->ltag==0) //b有左孩子,释放左子树 DestroyBTree1(b->lchild); if (b->rtag==0) //b有右孩子,释放右子树 DestroyBTree1(b->rchild); free(b); } void DestroyBTree(BthNode *&tb) { DestroyBTree1(tb->lchild); //释放以tb->lchild为根结点的树 free(tb); //释放头结点 } 3.4 简单操作 BthNode *FirstNode(BthNode *tb)//在中序线索树中查找中序序列的第1个结点 { BthNode *p=tb->lchild; //p指向根结点 while (p->ltag==0) //找根结点的最左下结点 p=p->lchild; //继续找左子树 return(p); } BthNode *LastNode(BthNode *tb) //在中序线索树中查找中序序列的最后1个结点 { return(tb->rchild);//因为我们的最后一个结点后继指向头,头的后继指向最后一个结点 } BthNode *PreNode(BthNode *p)//在中序线索二叉树上,查找p结点的前驱结点 { BthNode *pre; pre=p->lchild;//找到它的左子树 if (p->ltag!=1)//如果左子树就指向p的前驱,ltag=1,因为它中序前一个为莫个树的中根 while (pre->rtag==0)//往后遍历,直到为1,就它的后继就是p的前驱 pre=pre->rchild; return(pre); } BthNode *PostNode(BthNode *p)//在中序线索二叉树上,查找p结点的后继结点 { BthNode *post; post=p->rchild; if (p->rtag!=1) while (post->ltag==0)//和上面同理 post=post->lchild; return(post); } void ThInOrder(BthNode *tb)//中序遍历线索二叉树,输出中序遍历序列 { BthNode *p; p=FirstNode(tb); while (p!=tb) { printf("%c ",p->data); p=PostNode(p); } printf("\n"); } 总结线索二叉树是基于二叉链之上的,博主的代码是用二叉链再做逻辑连接,我们也可以直接用那个类型建立线索二叉树,只要记住线索二叉树的连接规则是根据二叉树的三种遍历方法得来的,我们根据遍历来判断空域的连接,前驱指向这个遍历的结点的上一个结点,后继指向这个结点的下一个需要遍历的结点,差不多就是这样,不是很难,好了创作不易,点赞关注评论收藏哦!!!感谢大佬 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |