使用递归将二叉搜索树转换为双向链表

Question

如标题所述，我有一棵二叉搜索树。我想使用递归将其转换为排序的双向链表。 我的代码：

 for each node in tree
   find max of left sub-tree and assign its right to present node ,present node left to max 
   find min of right sub-tree and assign its left to present node ,present node right to max 
   and now recursively do same thing to other nodes in BST .

但这种解决方案效率不高，因为它会多次到达每个节点。在我的优化代码探索中，我从谷歌获得了一个链接 greatTreeList 解决方案。我在 SO 中搜索了相同的内容，两种解决方法都适用于我。我没有理解解决方案中的 append function，因为它包含代码。

join(alast,b)
join(blast,a)

对于按照以下顺序插入节点的树10,5,9,6,8,7,12,11,13,14

请问有人能解释一下如何在每次递归调用中链接节点的join（alast，b）和join（blast，a）吗？

- Imposter

---

你不想获取外部列表，而是要更新bst节点，对吗？我猜节点是一个记录，包含BST部分的指针（left_child、right_child）和列表部分的指针（previous_node、next_node）。 - Kwariz

@Kwariz：我不想使用任何外部列表。我想了解greatTreeList解决方案中append函数的逻辑。 - Imposter

Answer 1

为了将二叉搜索树转换为排序的双向链表，通常执行中序深度优先遍历，在遍历过程中构建链表。

尝试编写执行中序深度优先遍历并按排序顺序打印二叉树项的代码。从那里开始，完成你的任务应该很容易。

- Philip

Answer 2

我认为你在过度思考这个实际上非常简单的任务——从二叉树中按顺序提取数据就像进行深度优先遍历一样简单——这是二叉树的优点，它可以非常高效地按排序顺序给出元素。

所以你需要做的就是对树进行标准的深度优先遍历，并每次找到一个节点时将其添加到你的链表中。

这种按顺序的深度优先递归在伪代码中相当简单：

Traverse(Node N)
  Traverse(N.left);
  Add N to the linked list
  Traverse(N.right);

我建议您在您的示例上手动尝试一下，以便了解它是如何工作的。

- Elemental

---

当你说将列表添加到n时，涉及哪些步骤？返回值是什么，请解释。我总是困惑于递归中该返回什么，如果你能举个例子，尤其是我在这个问题中提到的例子，那就太好了。 - Imposter

@Elemental 这个算法需要有全局变量，它应该指向当前节点。在Java中，我们需要静态变量。谢谢。 - Trying

@Trying - 实际上不需要。这个程序可以（而且应该）完全不使用静态或全局引用来运行。 - Elemental

Answer 3

在Elemental的回答基础上进行扩展

Traverse(Node N)
  Traverse(N.left);
  Add N to the linked list
  Traverse(N.right);

如果要将N添加到链表中，

你的链表类或数据结构应该有一个append()方法或类似的方法。

可以发挥想象力，但是可以像这样：

def append(N):
    new_tail = node(val=N, prev=self.tail, next=None)
    self.tail.next = new_tail
    self.tail = new_tail

当然，在第一次添加时，您还需要添加self.head = self.tail。

- Rusty Rob