Дисплей Двоичное дерево в Java

Question

У меня возникли проблемы с отображением бинарное дерево поиска

Я хочу, чтобы быть в состоянии видеть каждое значение, которое было вставлено в дерево, и я не знаю, где находится ошибка. Также есть ли что-нибудь, что я должен изменить, чтобы сделать этот код более функциональным или более легким для чтения?

class BSTNode { 
    public int value; // data item (key) 
    public BSTNode leftChild; // this node's left child 
    public BSTNode rightChild; // this node's right child 

    public void displayNode() // display this node 
    { 
     StringBuilder node = new StringBuilder(); 
     node.append("{"); 
     node.append(value); 
     node.append("}"); 
     System.out.println(node); 
    } 
} 

class BSTree { 
    private BSTNode root; // first node of tree 

    public BSTree() { 
     root = null; 
    } 

    public BSTNode find(int searchValue) // looks for node with certain key 
    { 
     BSTNode current = root; 

     while (current.value != searchValue) { 

      if (searchValue < current.value) 
       current = current.leftChild; 
      else 
       current = current.rightChild; 

      if (current == null) 
       return null; 
     } 
     return current; 
    } 

public void insert(int value) // insert a new Node 
{ 
    BSTNode newNode = new BSTNode(); 
    BSTNode current, parent; 

    newNode.value = value; 

    if (root == null) 
     root = newNode; 
    else { 
     current = root; 
     while (true) { 
      parent = current; 
      if (value < current.value) // go left 
      { 
       current = current.leftChild; 
       if (current == null) // if end of line 
       { 
        parent.leftChild = newNode; 
        return; 
       } 
      } // end left 
      else // go right 
      { 
       current = current.rightChild; 
       if (current == null) // if end of the line 
       { 
        parent.leftChild = newNode; 
        return; 
       } 
      } 
     } 
    } 
} 

Вот метод отображения:

public void displayBSTree() // display search tree 
{ 
    Stack<BSTNode> treeStack = new Stack<BSTNode>(); 
    treeStack.push(root); 
    int numOfBlanks = 32; 
    boolean isRowEmpty = false; 
    System.out.println("\n"); 

    while (isRowEmpty == false) { 
     Stack<BSTNode> localStack = new Stack<BSTNode>(); 
     isRowEmpty = true; 

     for (int x = 0; x < numOfBlanks; x++) 
      System.out.print(" "); 

     while (treeStack.isEmpty() == false) { 
      BSTNode temp = (BSTNode)treeStack.pop(); 
      if (temp != null) 
      { 
       System.out.print(temp.value); 
       localStack.push(temp.leftChild); 
       localStack.push(temp.rightChild); 

       if (temp.leftChild != null || temp.rightChild != null) 
        isRowEmpty = false; 
      } 
       else { 
        System.out.print("--"); 
        localStack.push(null); 
        localStack.push(null); 
       } 

       for (int y = 0; y < numOfBlanks*2-2; y++) 
        System.out.print(" "); 
      } 
     System.out.println(); 
     numOfBlanks /= 2; 
     while (localStack.isEmpty() == false) 
      treeStack.push(localStack.pop()); 

    } 
    System.out.println(); 
} 

и основной метод

public class ShowBST { 

    public static void main(String[] args) { 
     int[] values = new int[] {23, 17, 5, 90, 12, 44, 38, 84, 77, 3, 66, 55, 1, 19, 37, 88, 8, 97, 25, 50, 75, 61, 49}; 

     BSTree tree = new BSTree(); 

     for (int value : values) { 
      tree.insert(value); 
     } 
     tree.displayBSTree(); 

    } 

} 

В настоящее время выход

      23                
      49        --        

Answer 1

Условие еще в вставке добавляет узел к LeftChild вместо RightChild.

 else // go right 
     { 
      current = current.rightChild; 
      if (current == null) // if end of the line 
      { 
       parent.leftChild = newNode; 
       return; 
      } 
     } 

После устранения, что вам нужно настроить интервал, вы бежите из заготовок на все нули так номера начинают получать слиты вместе.

Answer 2

Я предполагаю, что это копия & паста Ошибка:

  else // go right 
      { 
       current = current.rightChild; 
       if (current == null) // if end of the line 
       { 
        parent.leftChild = newNode; 
        return; 
       } 
      } 

Должно быть:

  else // go right 
      { 
       current = current.rightChild; 
       if (current == null) // if end of the line 
       { 
        parent.rightChild = newNode; 
        return; 
       } 
      } 

Вы перекрывая левый узел каждый раз, когда вы найдете что-то подходящее в качестве правого узла, поэтому вы можете видеть только добавил узел кулака (23) и последний (49), который должен идти вправо, но, по-видимому, он находится слева.

Answer 3

В вашем обходе дерева в методе insert, вы случайно пойти налево, вместо того, чтобы идти направо:

else // go right 
     { 
      current = current.rightChild; 
      if (current == null) // if end of the line 
      { 
       parent.leftChild = newNode; 
       return; 
      } 
     } 

исправить, изменить ссылку на parent.leftChild в parent.rightChild.

Кроме того, есть усовершенствования вашего кода, которые могут быть сделаны. Например, создайте конструктор с параметром для класса BSTNode, чтобы вам не приходилось устанавливать .value каждый раз. Как так:

class BSTNode { 
    //constructor 
    public BSTNode(int value){ 
    this.value = value; 
    } 
} 

Затем переключитесь BSTNode newNode = new BSTNode(value);