java 递归二叉搜索树

Question

我编写了一个 boolean 插入方法，它将值插入到二叉搜索树中，如果值不存在则插入该值，如果存在则返回 true，如果值已经存在则返回 false，因此不插入任何内容。我正在尝试将这种迭代方法转换为完全没有循环的所有递归方法，但我无法弄清楚如何实现。如有任何帮助，我们将不胜感激!

public boolean insert(int value) {
    Node travel= root, prev= null, newNode;
    boolean result= true;

    while (travel != null && travel.data != value) {
      prev= travel;
      if (value < travel.data)
        travel= travel.left;
      else travel= travel.right;
    }

    if (travel != null)
      result= false;
    else
      if (root == null)  
        root= new Node(value);
      else
        if (value < prev.data)
          prev.left= new Node(value);
        else prev.right= new Node(value);

    return result;
  }

Answer 1

http://www.java2s.com/Code/Java/Collections-Data-Structure/BinaryTree.htm

public class BinarySearchTree {

    private Node root;

    public boolean insert(int value) {
        if (root == null) {
            root = new Node(value);
            return true;
        } else {
            return insert(root, value);
        }
    }

    private boolean insert(Node node, int value) {
        if (value < node.value) {
            if (node.left != null) {
                return insert(node.left, value);
            } else {
                node.left = new Node(value);
                return true;
            }

        } else if (value > node.value) {
            if (node.right != null) {
                return insert(node.right, value);
            } else {
                node.right = new Node(value);
                return true;
            }

        } else {
            return false;
        }
    }

    public void printInOrder(Node node) {
        if (node != null) {
            printInOrder(node.left);
            System.out.println("Traversed " + node.value);
            printInOrder(node.right);
        }
    }

    public static void main(String[] args) {
        BinarySearchTree t = new BinarySearchTree();
        System.out.println("insert 5: " + t.insert(5));
        System.out.println("insert 4: " + t.insert(4));
        System.out.println("insert 7: " + t.insert(7));
        System.out.println("insert 4: " + t.insert(4));
        t.printInOrder(t.root);
    }
}

class Node {

    Node left;
    Node right;
    int value;

    public Node(int value) {
        this.value = value;
    }
}