数据结构与算法分析 8.9分
读书笔记 第4章 树 练习
knightley
4.45 由于具有N个节点的二叉查找树有N+1个NULL指针,因此在二叉查找树中指定给指针信息的空间的一半被浪费了。设若一个节点有一个NULL左儿子,我们使它的左儿子指向它的中缀前驱(inorder predecessor),若一个节点有一个NULL右儿子,我们让它的右儿子指向它的中缀后继(inorder successor)。这就叫做线索树(threaded tree),而附加的指针就叫做线索。
a.我们如何能够从实际的儿子指针中区分出线索?

答:需要在树节点的数据结构中添加额外的变量。

c.使用线索树的优点是什么?

答:遍历起来更容易,而且可以不使用递归。可以加快查找二叉树中某节点的前驱和后继的速度。关于线索树优点的更详细的介绍,参见wiki:https://zh.wikipedia.org/wiki/%E7%BA%BF%E7%B4%A2%E4%BA%8C%E5%8F%89%E6%A0%91

0
《数据结构与算法分析》的全部笔记 69篇
豆瓣
免费下载 iOS / Android 版客户端