线索二叉树6----口----

来源：蜘蛛抓取(WebSpider) 时间：2016-09-07 18:13 标签： 线索

发布时间： 来源：网络 上传者：鼡户

上一章介绍了二叉树的二叉链表的实现,并给出了相关遍历算法,但是,当以二叉链表作为二叉树的存储结构时,无法直接得到结点在任一序列中的前驱与后继信息为了规避这个弊端,本章将引入线索二叉树二叉树的概念 ,并给出相关Java实现。

为了得到前驱与后继的信息,最直观的想法是在每个结点上添加两个指针域,分别指向结点在遍历时的前驱及后继然而,这样会使存储密度大大降低,而在有n个结点的二叉树中有n+1个空鏈域,故可利用这些空链域来存放结点的前驱及后继信息,并作如下规定:若结点有左子树,则其leftChild域指向其左孩子,否则,令leftChild指向其前驱;若结点有右子樹,则其rightChild域指向其右孩子,否则,令rightChild指向其后继。

为了避免混淆,现对上章中的结点结构作适当改动,改动后如下:

并规定:leftTag取值为false时,指示结点的左孩子,取值为true时,指示结点的前驱;rightTag取值为false时,指示结点的右孩子,取值为true时,指示结点的后继

线索二叉树链表:以上述结点结构构成的二叉链表作为二叉樹的存储结构,其中指示结点前驱及后继信息的指针称作线索二叉树,加上线索二叉树的二叉树称为线索二叉树二叉树。
线索二叉树化:对二叉樹以某种次序遍历使其变为线索二叉树二叉树的过程
线索二叉树化的实质:修改空指针(将二叉链表中的空指针改为指向前驱或后继的线索②叉树)。

下面给出相关java代码实现:

进行举报并提供相关证据，工作人员会在5个工作日内联系你一经查实，本站将立刻删除涉嫌侵权内容

二叉树按某种顺序线索二叉树化後任一结点均有指向其前驱和后续的线索二叉树，这种说法____ A. 正确 B. 错误 5. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前媔这种说法____。 A. 正确 B. 错误 6. 由于二叉树中每个结点的度最大为2所以二叉树是一种特殊的树，这种说法____ A. 正确 B. 错误 7. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里我们把由树转化得到的二叉树叫做这棵数对應的二叉树。结论____是正确的 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 树的后根遍历序列与其对应的二叉树的后序遍历序列相同 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 以上都不对 17. 深度为5的二叉树至多有____个结点。 A. 16 B. 32 C. 31 D. 10 18. 在一非空二叉树的中序遍历序列中根结点的右边____。 A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点 19. 树最适合用来表示____ A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 20. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序____。 A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对 21. 实现任意二叉树的后序遍历的非递归算法而不使用栈结构最佳方案是②叉树采用____存储结构。 A. 二叉链表 B. 广义表存储结构 C. 三叉链表 D. 顺序存储结构 22.

内容提示：数据结构第6章 树和二叉树3

文档格式：PPT| 浏览次数：7| 上传日期： 20:45:41| 文档星级：?????

全文阅读已结束如果下载本文需要使用

该用户还上传了这些文档

我要回帖

更多关于 线索 的文章

 

随机推荐