java - 编写一个方法来查找两个 BST 之间的公共(public)元素，并将它们插入到第 3 个 BST 中

Question

我有一个插入方法和一个搜索方法，我正在考虑一种方法来循环二叉搜索树并使用像获取节点这样的方法，然后在另一个二叉搜索树上搜索它，如果它成立，那么我将其插入该元素，但问题是我无法想出一种基于索引获取节点的方法，因为它与 linkedList 不同，并且无法想出一种方法来开始获取节点；总而言之，我实际上不知道开始解决这个问题的正确方法。

public class BinarySearchTree extends BinaryTree {
    //default constructor
    //Postcondition: root = null;

    public BinarySearchTree() {
        super();
    }

    //copy constructor
    public BinarySearchTree(BinarySearchTree otherTree) {
        super(otherTree);
    }
public class BinaryTree {

    //Definition of the node
    protected class BinaryTreeNode {

        DataElement info;
        BinaryTreeNode llink;

        public DataElement getInfo() {
            return info;
        }

        public BinaryTreeNode getLlink() {
            return llink;
        }

        public BinaryTreeNode getRlink() {
            return rlink;
        }
        BinaryTreeNode rlink;
    }
    protected BinaryTreeNode root;

    //default constructor
    //Postcondition: root = null;
    public BinaryTree() {
        root = null;
    }

    //copy constructor
    public BinaryTree(BinaryTree otherTree) {
        if (otherTree.root == null) //otherTree is empty
        {
            root = null;
        } else {
            root = copy(otherTree.root);
        }
    }

    public BinaryTreeNode getRoot() {
        return root;
    }
public boolean search(DataElement searchItem) {
        BinaryTreeNode current;
        boolean found = false;

        current = root;
        while (current != null && !found) {
            if (current.info.equals(searchItem)) {
                found = true;
            } else if (current.info.compareTo(searchItem) > 0) {
                current = current.llink;
            } else {
                current = current.rlink;
            }
        }

        return found;
    }

    public int countEven() {

            return countEven(root);

    }
public void insert(DataElement insertItem) {
        BinaryTreeNode current;
        BinaryTreeNode trailCurrent = null;
        BinaryTreeNode newNode;
        newNode = new BinaryTreeNode();
        newNode.info = insertItem.getCopy();
        newNode.llink = null;
        newNode.rlink = null;
        if (root == null) {
            root = newNode;
        } else {
            current = root;
            while (current != null) {
                trailCurrent = current;
                if (current.info.equals(insertItem)) {
                    System.out.println("The insert item is already in" + "the list -- duplicates are" + "not allowed.");
                    return;
                } else if (current.info.compareTo(insertItem) > 0) {
                    current = current.llink;
                } else {
                    current = current.rlink;
                }
            }

            if (trailCurrent.info.compareTo(insertItem) > 0) {
                trailCurrent.llink = newNode;
            } else {
                trailCurrent.rlink = newNode;
            }
        }
    }

Answer 1

向下遍历到一棵树的左端，将其与另一棵树的根节点进行比较。如果发现相等，则将其插入到第三棵树中。如果不相等，则检查它是否小于或大于第二棵树的根。如果小于，则遍历到第二棵树的左子树并再次调用您的搜索方法，否则，遍历到第二棵树的右子树并再次调用您的搜索方法。然后对您选择的第一棵树的相对起始节点的右侧节点重复整个过程，并再次调用搜索方法。重复该过程时，继续向上移动第一棵树。

这是一个示例代码(请记住，您没有提供有关树木的任何详细信息):

void search(Node node1, Node root2){
    if(root2 == null)
        return;
    if(node1.data == root2.data){
        //copy to your third tree
        return; 
    }
    else{
        if(node1.data < root2.data){
            root2 = root2.left;
            search(node1, root2);
        }
        else{
            root2 = root2.right;
            search(node1, root2);
        }
    }
}

void common(Node root1, Node root2){
    if(root1 != null){
        common(root1.left, root2);
        search(root1, root2);
        common(root1.right, root2);
    }
}