线索二叉树 – 数据结构和算法48

线索二叉树

让编程改变世界

Change the world by program

线索二叉树

为什么需要线索二叉树呢？

我想正如程序猿发觉单链表并不总能满足他们设计的程序某些要求的时候，发明了双向链表来弥补一样，线索二叉树也是在需求中被创造的！

那普通的二叉树到底有什么缺陷让我们发指呢？

一，浪费空间

二，浪费时间

三，浪费青春

来，我们具体分析下如何个浪费法：

数序题：请问以下有多少个“^”？总共浪费了多少字节的空间？(32bit的机器)

脑筋急转弯：我们知道通过对二叉树的约定遍历方式，可以得到一个固定的遍历顺序，那么请问哪种遍历方式可以节省“^”所浪费的空间？（利用“^”记录该结点的前驱后继）

没错，中序遍历可以拯救地球！

上图经过中序遍历后结果是：HDIBEAFCG

我们发现红色的结点都是刚才“^”造成浪费的结点，利用中序遍历刚好它们均处于字符中间，可以很好地利用“^”来存放前驱和后继的指针。

不过好事总是多磨的，我们是有主观意识所以可以很容易出来哪些结点可以利用存放前驱后继。

有鱼油不同意了：这所谓的主观意识还不简单，不就是从第一个开始每隔一个结点都可以？

上图经过中序遍历后结果是：FDGBACE

黄色说明只有一个空闲的指针位置，如果是这样的话我们就面临一个问题：机器怎么识别到底是存放指针还是线索？

没错，她需要一丁点儿提示，为此我们将已经定义好的结构进行“扩容”：

ltag为0时指向该结点的左孩子，为1时指向该结点的前驱。

rtag为0时指向该结点的右孩子，为1时指向该结点的后继。

视频下载
技术, IT技术, 数据结构和算法, 结点

                                                    风险提示及免责条款

市场有风险，投资需谨慎。本文不构成个人投资建议，也未考虑到个别用户特殊的投资目标、财务状况或需要。用户应考虑本文中的任何意见、观点或结论是否符合其特定状况。据此投资，责任自负。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！