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

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调用正确地将元素添加到树中，但后续调用失败，因为当您递归插入到左侧或右侧时，您覆盖了要null的数据成员temp。因此，第一个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.Insert(x)一样称呼它。