递归插入节点

Question

我正在尝试使用递归方法在二叉树中插入节点。但是一旦它脱离了方法，根就变成了新节点，左 child 和右 child 为空。有了这个，我试图学习递归是如何工作的。此外，递归方法是否总是必须 return 一些东西。下面是代码。

public class BinaryNode {
     int key;
     BinaryNode left;
     BinaryNode right;

    public BinaryNode( int key){
        this.key = key;
       // this.left = left;
        //this.right = right;

    }
}

public class BinaryTree {

    BinaryNode root;


    public  void insert(int key){

        BinaryNode newNode = new BinaryNode(key);

            if(root == null){
                root = newNode;

            }else{
                  BinaryNode focusNode = root;
                  BinaryNode parent;

                while(true){
                    parent = focusNode;
                    if(key<focusNode.key){

                        focusNode = focusNode.left;
                        if(focusNode==null){
                            parent.left= newNode;
                            return;
                        }

                    }else{
                        focusNode = focusNode.right;
                        if(focusNode==null){
                            parent.right= newNode;
                            return;
                        }
                    }

                }

            }





    }

    public BinaryNode recursiveInsert(int key, BinaryNode node){
        BinaryNode newNode = new BinaryNode(key);
        if (node == null){
            root = newNode;

        }

        else{

            if(key < node.key){


                 root.left = recursiveInsert(key, node.left);


            }
            else{

                 root.right = recursiveInsert(key, node.right);


            }
        }

      return root;
    }




     public String toString(){
         String toTree = null;



        return toTree;
     }

    public static void main(String[]args){
        BinaryTree tree = new BinaryTree();

        tree.recursiveInsert(7, tree.root);
        tree.recursiveInsert(6, tree.root);
        tree.recursiveInsert(4, tree.root);
        tree.recursiveInsert(8, tree.root);
        tree.recursiveInsert(9, tree.root);
        tree.recursiveInsert(5, tree.root);



    }

}

我尝试的方法是recursiveInsert。谢谢！！

Answer 1

你的递归代码应该是这样的：

public BinaryNode recursiveInsert(int key, BinaryNode node) {
    if (node == null) {
        return root = new BinaryNode<>(key);
    } else {
        if (key < node.key) {
            if (node.left == null) {
                return node.left = newNode;
            } else {
                return recursiveInsert(key, node.left);
            }
        } else {
            if (node.right == null) {
                return node.right = newNode;
            } else {
                return recursiveInsert(key, node.right);
            }
        }
    }
}

您正在对递归函数中的 root 节点进行操作，您应该对传递给递归函数的 node 节点进行操作。

Answer 2

我想问题出在

if (node == null){
        root = newNode;
}

您正在遍历树，并且在最后一步中您要询问叶节点的 left/right child。这没有一个，所以它 child 是空的。这是递归调用返回的值，最后，它被分配给 root。

要解决此问题，在下降到节点之前，请确保 child 节点存在。

还有这个有点奇怪

root.left = recursiveInsert(key, node.left);

应该是node而不是root。

Answer 3

你的代码有几个问题我不一定要讨论，因为我认为它们会分散你对核心问题的注意力。

首先回答您的第二个问题：不，没有规则规定递归方法必须 return 任何东西。更重要的是他们知道什么时候终止。

至于你的错误，我认为这可能是因为你的 insert 方法总是 returns 并且在 root 上运行。您可能是想修改 return newNode.

Answer 4

这是因为您的 recursiveInsert 方法总是在 root 上运行。试试这个 -

public Node recursiveInsert(Node currentParent, Node newNode) {

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

        return currentParent;
    }

递归插入节点

Insert node recursively

java

recursion

binary-tree

nodes