线程二进制搜索树的优势

Question

关于线程二进制搜索树的解释（如果你知道它们，请跳过）：

我们知道，在一个有n个节点的二叉搜索树中，有n1个左右指针包含null。为了使用包含null的内存，我们对二叉树进行如下更改-

对于树中的每个节点z：

如果左[z]=NULL，我们在左[z]中输入树前身（z）的值（即，指向包含前身键的节点的指针），

如果right[z]=NULL，我们将树后继者（z）的值放在right[z]中（同样，这是一个指向包含后继者键的节点的指针）。

这样的树称为线程二叉搜索树，新链接称为线程。

我的问题是：线程二叉搜索树的主要优点是什么（与“常规”二叉搜索树相比）。在网络上的快速搜索告诉我，它有助于迭代而不是递归地实现顺序遍历。

这是唯一的区别吗？有没有其他方法可以使用这些线程？

这是有意义的优势吗？如果是，为什么？递归遍历也花费O（n）时间，所以...

非常感谢你。

Answer 1

与常规二叉搜索树相比，线程二叉搜索树的主要优势在于遍历自然，与其他搜索树相比，前者更高效。

递归遍历意味着您不需要使用堆栈或队列来实现它。每个节点都将有一个指针，它将以更有效的方式给出顺序的后继和前置，而在正常的BST中实现遍历需要堆栈，这是内存耗尽的（因为这里的编程语言必须考虑堆栈的实现）。

Answer 2

非递归有序扫描是一个巨大的优势。想象一下，有人让你找到值“5”及其后的四个值。使用递归很难。但是如果你有一个线程树，那就很容易了：执行递归有序搜索以找到值“5”，然后按照线程链接获取接下来的四个值。

同样，如果您想要特定值之前的四个值怎么办？递归遍历很难做到这一点，但如果您找到项目然后向后遍历线程链接，这就微不足道了。