递归二进制搜索树插入 [英] Recursive Binary Search Tree Insert

问题描述

所以这是我的第一个Java程序，但是我已经做了c ++几年了.我写了我认为应该起作用的东西，但实际上没有作用.因此，我规定必须为此调用编写一个方法:

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);

其中value是一个int. 出于明显的原因，我想递归地编写它，所以我必须解决以下问题:

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());
}

谢谢您的建议.

推荐答案

// 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;
}

Sameer Sukumaran

这篇关于递归二进制搜索树插入的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！