3

如标题中所述，我有一个二叉搜索树。我想使用递归将其转换为排序的双重链接列表。

我的代码

 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 sollution获得了一个链接。我在SO中搜索了相同的解决方案，并且对我有用。我不明白解决方案的append function内容，因为它包含代码

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

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

谁能解释一下如何加入（最后，b）加入（爆炸，a）

在每个递归调用中链接节点。

4

3 回答 3

1

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

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

于 2012-09-06T09:08:12.150 回答
1

我认为您过度考虑了这实际上非常简单的任务-按顺序从二叉树中提取数据就像进行深度优先遍历一样简单-这是二叉树的要点，它非常有效地为您提供了排序中的元素命令。

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

这个顺序深度优先递归是相当简单的伪代码：

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

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

于 2012-09-06T09:15:23.453 回答
1

扩展元素的答案

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。

于 2012-09-06T11:48:00.213 回答