Реализовать двоичное дерево и сделать его сбалансированным

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;
 }

public static void main(аргументы String[])

    do    
    {
        //tree operations
        System.out.println("\nTree Operations\n");
        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 Operations\n");
    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;
  }
}