有序地遍历两个 BST

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

objective 是按顺序打印它们，所以，在这种情况下，它会打印：

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

现在，挑战来了：是否真的可以在不使用任何其他辅助动态数据结构（如队列、堆栈、列表等）的情况下做到这一点...？

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

Answer 1

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

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

更详细一点：您初始化了两个 DFS。这为您提供了每棵树中分别指向第一个元素的路径。现在你比较元素，select 树与较低的元素。打印元素（如果需要，使用减号）并在您 selected 的树中推进 DFS。这为您提供了这棵树中的下一个元素。同样，您比较两棵树中的下一个元素，select 较小的那个，等等。

这里是一些Javascript/C-like伪代码：

// 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());
}

Answer 2

我假设 negBST 和 posBST 各自包含唯一的键。

与其尝试在 parallel/simultaneously 中处理两个单独的 BST:s，不如创建一个 BST，比如 commonBST，它允许非唯一条目.通常，这很棘手并且会破坏 BST 的基本属性，但在这种特殊情况下，它会起作用，因为：

对于我们的数字数组（例如：-2 2 5 8 -4 -5 -3 -6），为了构造单 BST commonBST，只看每个数字的绝对值;说 KEY = abs(number)，然后将数字的符号关联到 KEY 的附加属性，说 KEY.sign。每个可能的KEY只能存在于以下状态：
- 无（树中不存在）
- (KEY, KEY.keySign=-1 为 -)
- (KEY, KEY.keySign=+1 对于 +)
- (KEY, 两个符号, KEY.keySign=0)
如果我们已经有两棵树（而不是创建这两棵树的初始数组），我们只需将 negBST 添加到 posBST 即可实现上述的 commonBST。

由于 negBST 和 posBST 仅包含唯一键，因此 commonBST 键的唯一退化是特定 KEY 可能同时出现 + 和 -。

使用此架构，我们可以创建 commonBST（以您的数字数组为例）：

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)。

有序地遍历两个 BST

Traversing two BSTs inorder in an orderly fashion

algorithm

binary-search-tree