java如何创建包含从1到n的所有数字的二叉搜索树

Question

我正在尝试创建一个包含从1到n的所有数字的二元搜索树。例如，从1到5可能是这样的

根：3

根。左：2

根。左边左=1

根。右=4

根。正当右=5

这棵树碰巧不是很平衡，但我更喜欢一种尽可能产生平衡树的方法

我正试图为此创建自己的数据结构，所以我基本上只编写了一个节点类：

    private class BinaryNode{
        int data;
        BinaryNode left;
        BinaryNode right;
        BinaryNode parent;
    }

我计划把它放在另一个类中，代表树本身。我一直在寻找一种合适的方法来确定左/右值以构建树，非常感谢您的帮助

Answer 1

public void insert(int id){
    Node newNode = new Node(id);
    if(root==null){
        root = newNode;
        return;
    }
    Node current = root;
    Node parent = null;
    while(true){
        parent = current;
        if(id<current.data){                
            current = current.left;
            if(current==null){
                parent.left = newNode;
                newNode.parent = parent;
                return;
            }
        }else{
            current = current.right;
            if(current==null){
                parent.right = newNode;
                newNode.parent = parent;
                return;
            }
        }
    }
}

无需递归插入1到n个数字

public static void main(String arg[]){
    Solution2 s = new Solution2();
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    for(int i = 1;i <= n;i++){
        s.insert(i);
    }

}