1

我有一个插入方法和一个搜索方法，我正在考虑一种方法来遍历二叉搜索树并使用像获取节点这样的方法然后在另一个二叉搜索树上搜索它，如果它实现了，那么我插入它那个元素，但问题是我无法想出一种基于索引获取节点的方法，因为它不同于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;
            }
        }
    }
4

2 回答 2

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);
    }
}
于 2012-05-25T18:37:21.227 回答
0

我假设您需要修改BinarySearchTree该类，因此以下内容是根据该假设编写的。

您可以通过首先调用getRoot()将返回树的根 (a ) 来遍历树，然后分别通过调用和BinaryTreeNode访问节点的左右子节点。从每个节点，您可以通过在另一棵树中搜索（通过调用第二棵树上的方法）来获取其值。getLLink()getRLink()getInfosearch()

注意：实际上，您只能从方法中调用节点上的方法，BinarySearchTree因为访问权限BinaryTreeNode仅限于BinaryTree和派生自它的类（BinarySearchTree符合条件）

于 2012-05-26T04:03:44.060 回答