7

So this is my first java program, but I've done c++ for a few years. I wrote what I think should work, but in fact it does not. So I had a stipulation of having to write a method for this call:

tree.insertNode(value);

where value is an int. I wanted to write it recursively, for obvious reasons, so I had to do a work around:

public void insertNode(int key) {
    Node temp = new Node(key);

    if(root == null) root = temp;

    else insertNode(temp);
}

public void insertNode(Node temp) {
    if(root == null)
        root = temp;

    else if(temp.getKey() <= root.getKey())
        insertNode(root.getLeft());

    else insertNode(root.getRight());
}

Thanks for any advice.

4

5 に答える 5

18 
// In java it is little trickier  as objects are passed by copy.
// PF my answer below.

// public calling method

public void insertNode(int key) {
    root = insertNode(root, new Node(key));
}

// private recursive call

private Node insertNode(Node currentParent, Node newNode) {

    if (currentParent == null) {
        return newNode;
    } else if (newNode.key > currentParent.key) {
        currentParent.right = insertNode(currentParent.right, newNode);
    } else if (newNode.key < currentParent.key) {
        currentParent.left = insertNode(currentParent.left, newNode);
    }

    return currentParent;
}

サミール・スクマラン

于 2013-11-13T09:05:35.357 に答える
2

この記事を見たほうがいいです。ツリー構造と検索、挿入メソッドを実装するのに役立ちます: http://quiz.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/

// This method mainly calls insertRec()
void insert(int key) {
   root = insertRec(root, key);
}

/* A recursive function to insert a new key in BST */
Node insertRec(Node root, int key) {

    /* If the tree is empty, return a new node */
    if (root == null) {
        root = new Node(key);
        return root;
    }

    /* Otherwise, recur down the tree */
    if (key < root.key)
        root.left = insertRec(root.left, key);
    else if (key > root.key)
        root.right = insertRec(root.right, key);

    /* return the (unchanged) node pointer */
    return root;
}
于 2016-06-14T15:33:30.740 に答える
0

Integer新しいオブジェクト型を作成する代わりに、標準 (プリミティブ int のラッパー) オブジェクトを使用できますNode。最新の Java では、整数/整数の自動ボクシングがサポートされています。したがって、メソッドinsertNode(int key)はInteger引数も受け取ることができます (null でないことを確認してください)。

編集：上記のコメントは無視してください。私はあなたの本当の質問を理解していませんでした。オーバーロードする必要がありますinsertNode()。私はあなたが正しいと思います。

于 2013-02-12T04:47:33.877 に答える
0

しかし、あなたがいるときの一時はどこinsertNodeですか?? root が null でない場合、現在の実装では一時が失われます。

あなたは次のようなものが欲しいと思います

root.getLeft().insertNode(temp);

と

root.getRight().insertNode(temp);

つまり、新しいノード (temp) を左または右のサブツリーに挿入します。

于 2013-02-12T04:52:32.753 に答える