顯示二叉搜索樹在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

在INSERT else條件將該節點添加到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.rightChild的parent.leftChild參考。

此外，還可以對您的代碼進行改進。例如，爲BSTNode類創建一個帶有參數的構造函數，以便您不必每次都設置.value。像這樣：

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

然後換 BSTNode newNode = new BSTNode(value);