有序遍历两个二叉搜索树

Question

这些天我一直在尝试实现我的教授提出的一个函数，作为一个挑战，但我无法想出任何可能做到它的方法，所以我来这里看看是否有人能够帮助我。

这个问题只涉及算法，但我实际上是使用C++编程的，使用了基本规格（插入、删除、成员操作）编写的BSTree。

问题如下：

假设树的每个节点都包含一个绝对数值，并且我们有两个不同的BST：一个用于存储负数，另一个用于存储正数。我们可以称之为negBST和posBST。例如，如果我们输入数字-2 2 5 8 -4 -5 -3 -6，这将是我们的两棵树：

2                        2
 \                        \
  4                        5
 / \                        \
3   5                        8
     \
      6
Negative BST               Positive BST

目标是将它们按顺序打印出来，因此，在这种情况下，它会输出：

2 -2 -3 -4 5 -5 -6 8 

现在，挑战来了：是否可以在不使用任何其他辅助动态数据结构（如队列、栈、列表等）的情况下完成这个任务呢？

编辑： 所提供的示例可能有点令人困惑，因为树的深度可能会有所不同。

- Sergio Sánchez

---

如果你的树有固定的最大深度，你可以使用固定大小的数组来存储同时遍历两棵树时当前的“路径”（在每个值处比较你正在查看的两个值中哪个更小，记录它，并增加该树的位置）。 - Dave

@Dave 这确实可以解决问题，但很遗憾只有在两棵树都有固定的最大深度的情况下才能使用，正如你所说的 :( - Sergio Sánchez

@SergioSánchez 也可以考虑查看一下我的答案是否能够帮到你，或者对它提出一些反馈（这样我也可以学到一些东西）。 - dfrib

Answer 1

一个简单但效率低下的解决方案是从零到MAX_NUMBER迭代一个变量n，并检查每个迭代和树，如果数字n在树中保存。如果是，则打印它（当然对于负数树则为负）。

您还可以并行进行两次深度优先搜索。在每次迭代中，比较下一步搜索将产生较低数字的树。从相应的树中打印数字并推进相应的搜索。

稍微详细一些：您初始化了两个DFSs。这为您提供了每个树中指向第一个元素的一个路径。现在，您比较元素，选择具有较低元素的树。打印元素（如有必要，则带负号）并推进所选树中的DFS。这为您提供了此树中的下一个元素。再次比较两个树中的下一个元素，选择较小的一个，以此类推。

以下是一些JavaScript /类似C的伪代码：

// let's assume a DFS and its status is represented by an object
// dfs.next() returns the next number and advances the search
// dfs.peekNext() only returns the next number

var dfsPos = initDFS(posBST);
var dfsNeg = initDFS(negBST);

while (!dfsPos.hasFinished() || !dfsNeg.hasFinished()) {
    if (dfsPos.hasFinished())
        print('-' +dfsNeg.next());
    else if (dfsNeg.hasFinisehd())
        print(dfsPos.next());
    else if (dfsPos.peekNext() < dfsNeg.peekNext()) 
        print(dfsPos.next());
    else
        print('-' +dfsNeg.next());
}

- lex82

---

这确实可能有效，但效率低下，不过应该可以工作。在我成功将其翻译成C++之前，我会继续关注这个问题，或者如果有人分享了更有效的方法，谢谢！ - Sergio Sánchez

我刚刚更新了答案。第二种方法不应该是低效的。实际上，它是最快的方式。 - lex82

我在答案中添加了更多的细节和伪代码。 - lex82

这不就是合并两个已排序数组的相同问题吗？ - newbie_old

@newbie_old 嗯，这与程序有关。在我的回答中，我只是将树看作可以按顺序从中提取元素的序列，所以你也可以用数组来做同样的事情。 - lex82

Answer 2

我将假设negBST和posBST各自都包含独特的键。

不需要同时处理两个单独的BST，你可以创建一个单一的BST，比如commonBST，允许非唯一条目。通常情况下这很棘手，并可能破坏基本的BST属性，但在这种特殊情况下，它能够解决问题。

• 对于我们的数字数组（例如：-2 2 5 8 -4 -5 -3 -6），为了构建单个 BST commonBST，只考虑每个数字的绝对值；假设 KEY = abs(number)，并将数字的符号关联到一个附加属性 KEY.sign 上。每个可能的 KEY 只能存在以下状态之一：

  • nil（不在树中）
  • (KEY, KEY.keySign=-1 表示 - )
  • (KEY, KEY.keySign=+1 表示 + )
  • (KEY, 两种符号都有, KEY.keySign=0)

• 如果我们已经有了两棵树（而不是创建这两棵树的初始数组），我们只需将 negBST 添加到 posBST 中即可得到上述 commonBST。

由于 negBST 和 posBST 只包含唯一的键，因此 commonBST 的键中唯一的退化情况是特定 KEY 的 + 和 - 出现可能都存在。

使用这个模式，我们可以创建一个通用的二叉搜索树（以您的数字数组为例）：

For key C:
    C*: C contains both +C and -C (keySign = 0)
    C : C contains only one of +C and -C (get sign from keySign)

Example binary tree for numbers [-2, 2, 5, 8, -4, -5, -3, -6]:

    2*
     \
     5*
   /    \
  4      8
 /      /
3      6

以下 Swift 代码构造了这样一棵树。

// adapted from "regular" BST in Swift from: 
// http://waynewbishop.com/swift/binary-search-trees/

//generic binary search tree
public class AVLTree {
    var key: Int?
    var keySign: Int? // -1 or 1 for unique entries, 0 if both
    var left: AVLTree?
    var right: AVLTree?

    init() { }

    //add item based on its value
    func addNode(key: Int) {

        //check for the head node
        if (self.key == nil) {
            self.key = abs(key)
            self.keySign = abs(key)/key
            return
        }

        // check for duplicate key
        if (abs(key) == self.key) {
            self.keySign = 0
        }

        //check the left side of the tree
        else if (abs(key) < self.key) {
            if (self.left != nil) {
                left!.addNode(key)
            }
            else {
                //create a new left node
                let leftChild : AVLTree = AVLTree()
                leftChild.key = abs(key)
                leftChild.keySign = abs(key)/key
                self.left = leftChild
            }
        }

        //check the right side of the tree
        else if (abs(key) > self.key) {
            if (self.right != nil) {
                right!.addNode(key)
            }
            else {
                //create a new right node
                let rightChild : AVLTree = AVLTree()
                rightChild.key = abs(key)
                rightChild.keySign = abs(key)/key
                self.right = rightChild
            }
        }
    }
}

let numberList : Array<Int> = [-2, 2, 5, 8, -4, -5, -3, -6]

//create a new BST instance
var root = AVLTree()

//sort each item in the list
for number in numberList {
    root.addNode(number)
}

这里使用了纯命令式方法，因此您应该能够将其作为所选语言的详细伪代码使用。

commonBST可以像常规BST一样扩展，但在扩展每个键时只需检查属性keySign即可。

- 如果keySign = 1，则print(key)。 - 如果keySign = -1，则print(-key)。 - 如果keySign = 0，则print(-key)和print(key)（或您选择的顺序）。

这应该具有与任何常规BST相同的复杂度，在平均插入和查找时为O(log n)。

- dfrib

---

这是一个简单而有效的方法。问题在于我的教授给了我一些限制，不允许我创建任何辅助数据结构来执行操作，但我会点赞这个方法，因为它可能对其他人有帮助。谢谢！ - Sergio Sánchez

@SergioSánchez 啊，我有点错过了那个，我的错！ - dfrib