Вывод двоичного дерева дерева поиска

Я хочу вывести двоичное дерево поиска, задав массив значений. Он следует принципу двоичного дерева поиска. Диаграмма повернута влево.
Это желаемый результат:

Вывод двоичного дерева дерева поиска

Но он выводит как этот

Как я могу это исправить?

//class Node 
class Node { 
    int value; 
    Node left; 
    Node right; 

    Node(int x) { 
     value = x; 
    } 
} 

//class BST 
public class BST { 
    static int value[] = {3,4,5,6,1,2}; 
    public static Node root; 

    public static Node insert(int num[], int start, int end) { 
     if (start > end) 
      return null; 

     int mid = (start + end)/2; 
     Node roots = new Node(value[mid]); 
     roots.left = insert(value, start, mid - 1); 
     roots.right = insert(value, mid + 1, end); 

     display(roots, 0); 
     return roots; 
    } 

    public static void display(Node node, int level){ 
     if(node!=null){ 
      display(node.right, level+1); 
      System.out.println(""); 
      if(node==root) 
       System.out.print("Root-> "); 
      for(int i=0;i<level&&node!=root;i++) 
       System.out.print("    "); 
      System.out.print(node.value+"< "); 
      display(node.left, level+1); 
     } 
    } 

    public static void main(String args[]){ 
     insert(value, 0, 5); 
    } 
}

источник

2016-04-14 Meryel

Вы не вставить значение правильно, ваше последнее дерево не BST (1 имеет большее число в левом узле, но 3 имеет больший узел справа). Если вы хотите, чтобы ваша вставка работала, ваш массив должен быть уже отсортирован. Если вы хотите, чтобы ваш массив значений был несортирован, вам нужно сделать поворот во время вставки, вы должны посмотреть на код википедии или розетты для получения дополнительной информации. – Guillaume

Я отредактировал свой код, и вы правы, мне нужно его сортировать! Я найду алгоритм, как его сортировать. Благодаря! – Meryel

Самая интересная часть использования BST - это знать, как вставлять случайные значения, а не отсортированные значения. В вашем случае было тривиально вставлять значения, используя отсортированный массив, но вы действительно должны попытаться вставить значения случайным образом. – Guillaume

Рабочий код с отсортированного массива:

public class BST { 
    static int value[] = {1,2,3,4,5,6}; 
    public static Node root; 

    public static Node insert(int[] num) { 
     if (num.length == 0) 
       return null; 

     return insert(num, 0, num.length - 1); 
    } 

    public static Node insert(int num[], int start, int end) { 
     if (start > end) 
      return null; 

     int mid = (start + end)/2; 
     Node roots = new Node(value[mid]); 
     roots.left = insert(value, start, mid - 1); 
     roots.right = insert(value, mid + 1, end); 

     return roots; 
    } 

    public static void display(Node node, int level){ 
     if(node!=null){ 
      display(node.right, level+1); 
      System.out.println(""); 
      if(node==root) 
       System.out.print("Root-> "); 
      for(int i=0;i<level&&node!=root;i++) 
       System.out.print("    "); 
      System.out.print(node.value+"< "); 
      display(node.left, level+1); 
     } 
    } 

    public static void main(String args[]){ 
     display(insert(value), 0); 
    } 
}

источник

2016-04-14 14:53:39 Meryel

Вывод двоичного дерева дерева поиска

ответ

Смежные вопросы