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

1 つのツリーの左端までたどり、他のツリーのルート ノードと比較します。等しい場合は、3 番目のツリーに挿入します。等しくない場合は、2 番目のツリーのルートより小さいか大きいかを確認します。より小さい場合は、2 番目のツリーの左側の子に移動して検索メソッドを再度呼び出します。それ以外の場合は、2 番目のツリーの右側の子に移動して検索メソッドを再度呼び出します。次に、選択した最初のツリーの反対側の開始ノードの右側のノードでプロセス全体を繰り返し、検索メソッドを再度呼び出します。プロセスを繰り返しながら、最初の木を上に移動し続けます。

サンプルコードは次のとおりです（ツリーに関する詳細をまったく提供していないことに注意してください）：

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呼び出してノードの左右の子にアクセスします。各ノードから、他のツリーで検索できる値を介してその値を取得できます ( 2 番目のツリーでメソッドを呼び出すことにより)。getLLink()getRLink()getInfosearch()

注BinarySearchTree：そのままでは、アクセスBinaryTreeNodeが制限されているため、ノードのメソッド内からのみ呼び出すことができ、BinaryTreeそれから派生するクラス（BinarySearchTree修飾するもの）

于 2012-05-26T04:03:44.060 に答える