java - 如何在java中合并两个BST？

Question

我需要合并两个 BST。如果给定的符号表包含已在此符号表中的键，则合并将使用给定符号表中的值覆盖这些键的值。但我完全不知道如何开始。我现在所拥有的只是基本情况。

public class BST<Key extends Comparable<Key>, Value> {
private Node root;             // root of BST

private class Node {
    private Key key;           // sorted by key
    private Value val;         // associated data
    private Node left, right;  // left and right subtrees

    public Node(Key key, Value val) {
        this.key = key;
        this.val = val;
    }


public void merge(BST bst) {
    if(bst == null) return;
    // TODO
}

Answer 1

好吧，我不会为这个问题编写代码。我可以帮助你解决这个问题所需的逻辑

现在逻辑地思考一下，如果您执行 BST 的中序遍历并将每个 Node 对象存储在数组中，则结果数组将始终是排序的。

步骤1:

所以这里需要做的是对第一棵树进行中序遍历并将每个元素存储在 ar1(array1) 中。对第二棵树执行相同的操作并将其元素存储在 ar2(array2) 中。

步骤2:

将两个排序数组 ar1 和 ar2 合并到 ar3 中。

第三步:现在将这个排序数组转换为 BST，就完成了。但问题是你要怎么做？嗯，这很简单。中序遍历在这里再次发挥作用。

1.假设mid是数组中的中间元素。

2.从start到mid-1递归构造左子树

3.将中间元素作为根，并为其分配左子树。

4.从mid+1到end递归构造右子树。

5.将右子树分配给根。

看看这个链接，您的问题只是此处给出的问题的修改版本。 sortedlistToBst