帶有下一節點和上一節點鏈接的排序樹

Question

想象一下具有有序鍵的普通二叉搜索樹，其中每個節點還具有用於下一個（右側子節點中最左側節點）和前一個（左側子節點中最右側節點）節點的鏈接。如何調用這樣的數據結構（如果有名稱的話）？

Answer 1

您所描述的內容聽起來像threaded binary tree的特例，二叉樹本身就是二叉搜索樹。

一種類型的線程化二叉樹被稱爲「雙線程二叉樹」：每個節點都朝向順序前驅和後繼（左側和右側）。

在你使用二叉搜索樹的情況下，左子節點中最右邊的節點實際上是有序前導符，右子節點中最左邊的節點實際上是有序後繼節點。