带有下一个和上一个节点链接的排序树

Question

想象一个带有有序键的普通二叉搜索树，其中每个节点还有一个 link 用于下一个（右子节点中最左边的节点）和上一个（左子节点中最右边的节点）节点。如何调用这样的数据结构（如果有名称）？

Answer 1

你描述的听起来像是threaded binary tree的特例，二叉树本身就是二叉搜索树。

一种线程二叉树称为 "Double threaded binary tree"：每个节点都线程化到 in-order 前导和后继（左和右）。

对于二叉搜索树，左边 child 最右边的节点实际上是 in-order 的前身，右边 child 最左边的节点实际上是 in-order 继任者。