实现二叉树并使其平衡

Question

如何将 1 到 10000 之间的随机整数插入树？我只是在下面的代码中使用 scanner.in

 private BinaryTree insert(BinaryTree node, int value)
 {
     if (node == null)
         node = new BinaryTree(value);
     else
     {
         if (value <= node.getValue())
             node.left_child = insert(node.left_child, value);
         else
             node.right_child = insert(node.right_child, value);
     }
     return node;
 }

公共静态空隙主（字符串[] 参数）

    do    
    {
        //tree operations
        System.out.println("nTree Operationsn");
        System.out.println("1. insert ");

        int choice = scan.nextInt();            
        switch (choice)
        {
        case 1 : 
            System.out.println("get integer element to insert");
            bst.insert( scan.nextInt() );                     
            break;                                    
        default : 
            System.out.println("Wrong Entry n ");
            break;   
        }

Answer 1

我假设你的BinaryTree类如下：

public BinaryTree{
private int value = null;
private BinaryTree left_child=null;
private BinaryTree right_child=null;
//Also insert getters and setters here
BinaryTree(value){
this.value = value;
}
 private BinaryTree insert(BinaryTree node, int value)
 {
     if (node == null)
         node = new BinaryTree(value);
     else
     {
         if (value <= node.getValue())
             node.left_child = insert(node.left_child, value);
         else
             node.right_child = insert(node.right_child, value);
     }
     return node;
 }
}

在您的主要方法中，您应该具有：

BinaryTree node = new BinaryTree("RootValue");
do{
    //tree operations
    System.out.println("nTree Operationsn");
    System.out.println("1. insert ");

    int choice = scan.nextInt();            
    switch (choice)
    {
    case 1 : 
        System.out.println("get integer element to insert");
        node = bst.insert( node,scan.nextInt() );                     
        break;                                    
    default : 
        System.out.println("Wrong Entry n ");
        break;   
    }

我还没有对此进行测试，但我认为您的代码的主要问题是您的插入方法采用两个参数，但您只在代码中传递一个参数。莱姆知道这是否有效。

Answer 2

这只是为了插入，你需要另一个过程来使其平衡。我建议，取数组中的所有整数，对数组进行排序，然后一次性构造一个二叉树，

private BinaryTree constructBalanced(int a[], int low, int high) {
  if (low > high) return null;
  else {
    int mid = (low + high) / 2;
    BinaryTree root = new BinaryTree(a[mid]);
    root.left = constructBalanced(int a[], low, mid - 1);
    root.right = constructBalanced(int a[], int mid + 1, high);
    return root;
  }
}