显示二叉搜索树在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);