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

Question

我正在尝试使用递归插入二叉搜索树，然后使用此特定代码预先打印它，但我只有 root 作为输出，为什么？这是因为每次堆栈(每次调用后)都会弹出删除新节点？(这是一个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。一个常见的约定是有一个私有(private)的递归成员函数，它以树的根作为参数返回修改后的树，并将返回值分配给公共(public)成员函数中的 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) 那样调用它。