Способ вставки в двоичное дерево задачи - PullRequest
Новая
       37

Способ вставки в двоичное дерево задачи

0 голосов
/ 28 сентября 2018

У меня проблема со вставкой в ​​двоичное дерево, следующий код, кажется, не работает так, как я хочу.

  public static <E extends Comparable<? super E>>
                                   boolean inorderInsert(BTree<E> T, E x) {

   BTreeNode<E> n = T.getRoot();
    if(T.getRoot() == null) {
        T.setRoot(new BTreeNode<E>(x));
    }


 while (n != null) {
         if (x.compareTo(n.getElement()) == 0)
             return false;
         else if (x.compareTo(n.getElement()) < 0)
         if(n.getLeftChild()==null) {
             n.setLeftChild(new BTreeNode<E> (x));
         }
         if(n.getLeftChild()!=null) {
             n=n.getLeftChild();
         }
         else
         if(x.compareTo(n.getElement()) > 0) {
         if(n.getRightChild()==null) {
             n.setRightChild(new BTreeNode<E> (x));
         }
         if(n.getRightChild()!=null ) {
             n=n.getRightChild();
         }
         }
     } // while
    return true;

}

со следующими входами: 

             10 3 8 4 10 5 5 18 19 13

код производит следующий вывод: 

             3 4 5 13 18 19 8 10

вместо: 

             3 4 5 8 10 13 18 19 10

iдумал о том, чтобы сделать дерево таким образом, чтобы оно выглядело так: 

                         10
                      __/  \__
                     3         18                                                             
                      \       /  \
                       8     13  19                                               
                      /  
                     4
                      \ 
                       5

Я не могу найти, где я ошибся.Любая помощь будет принята с благодарностью.

Ответы [ 2 ]

0 голосов
/ 28 сентября 2018

Когда я просмотрел код и обнаружил, что это не так, этот код дал желаемые результаты. 

    boolean inorderInsert(BTree<E> T, E x) {
    BTreeNode<E> n = T.getRoot();
    if(T.getRoot() == null) {
        T.setRoot(new BTreeNode<E>(x));
    }


    while (n != null) {
        if (x.equals(n.getElement()))                            
        return false;                                                             
else if (x.compareTo(n.getElement()) < 0)                  
        if (n.getLeftChild() == null) {                            
        n.setLeftChild(new BTreeNode<E>(x));                      
        return true;                                              
        }           
        else         
        n = n.getLeftChild();                                                                                                    
else  if (n.getRightChild() == null){                            
        n.setRightChild(new BTreeNode<E>(x));                   
        return true;                                               
        }
        else   
        n = n.getRightChild();                                  
        }
        return false;                                              
        }
0 голосов
/ 28 сентября 2018

Из комментариев к исходному вопросу видно, что вы пытаетесь сделать сортировку по дереву , которую обычно проще реализовать как рекурсивный алгоритм, а не итеративный (цикл while),Я рекомендую взглянуть на литературу, чтобы узнать больше об алгоритме.Способ написания приведенного выше кода в настоящее время (итеративно, то есть с использованием цикла for) позволит вам пройти только один узел дерева за одну итерацию, делая результирующую структуру данных линейной, то есть каждый узел будет толькоиметь одного ребенка (другими словами, он будет эквивалентен списку).

Кроме того, я настоятельно рекомендую правильно делать отступы в коде, поскольку это намного упрощает понимание того, куда именно ветвится код.

...