插入二叉树问题的方法

Question

我在插入二叉树时遇到问题，以下代码似乎无法按我希望的方式工作。

  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

我正在考虑以一种它会出来的方式制作一棵树：

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

我找不到哪里出错了。任何帮助将不胜感激。

Answer 1

从对原始问题的评论来看，您尝试做的似乎是 Tree Sort，这通常更容易实现为递归算法，而不是迭代（while 循环）。我建议查看文献以了解有关该算法的更多信息。上面代码目前的写法（迭代式，即使用for循环），只会让你每次迭代遍历树的单个节点，使得得到的数据结构是线性的，即每个节点只会有一个child（换句话说，它将等同于一个列表）。

此外，我强烈建议正确缩进代码，因为这样可以更容易准确地理解代码分支到哪里。

Answer 2

当我检查代码时，我发现了错误，这段代码产生了预期的结果。

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

插入二叉树问题的方法

Method to insert into a binary tree problem

java

methods

binary-tree

inorder