通过使用这个BST插入方法，我只有根作为输出，为什么？

Question

我试图插入二叉查找树使用递归，然后打印它预先使用这个特定的代码，但我只有根作为输出，为什么？这是因为每个时间栈（每次调用后）弹出从而删除新节点？这是一个java代码）

class node{
    int data;
    node left;
    node right;
    node(int key){
        data = key;
        left = right = null;
    }
}

class bst{
    node  root;
    node  temp;
    node  last;
    bst(){
        root =  null;
    }
    bst(int key){
        root = new node(key);
    }
    void Insert(node r,int value){
        temp = r;
        if(temp == null){
            if(root == null){
                root = new node(value);
                root.data = value;
                return;
            }
            temp = new node(value);
            temp.data = value;
            return;
        }
        else{
            if(value > temp.data){
                Insert(temp.right,value);
                return;
            }
            else{
                Insert(temp.left,value);
                return;
            }
        }
    }
}

class test{
        static void in_order(node root){
            if(root == null){
                return;
            }
            in_order(root.left);
            System.out.println(root.data+" ");
            in_order(root.right);
        }
    public static void main(String[] args){
        bst tree = new bst();
        tree.Insert(tree.root,45);
        tree.Insert(tree.root,39);
        tree.Insert(tree.root,12);
        tree.Insert(tree.root,59);
        test.in_order(tree.root);
    }
}

Answer 1

您仅为输出获取单个整数的原因是，第一个Insert调用正确地将元素添加到树中，但后续调用失败，因为当您递归地向左或向右插入时，您将数据成员temp覆盖为null。因此，第一个if语句的第二个分支永远不会执行。

这里实际上不需要变量temp。一种常见的约定是使用私有递归成员函数，该函数将树的根作为参数返回修改后的树，并在公共成员函数中将返回值分配给root。

public void Insert(int value) {
  root = Insert(root, value);
}

private node Insert(node r, int value) {
  if (r == null) {
    r = new node(value);
  }
  else if (value > r.data) {
    r.right = Insert(r.right, value);
  }
  else {
    r.left = Insert(r.left, value);
  }
  return r;
}

这意味着您只需像tree那样调用它。插入（x）。