在 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

我猜是复制粘贴错误:

            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 2

在您的 insert 方法中遍历树时，您不小心向左走而不是向右走：

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

要修复，请将 parent.leftChild 的引用更改为 parent.rightChild。

此外，还可以对您的代码进行改进。例如，创建一个带有参数 BSTNode class 的构造函数，这样您就不必每次都设置 .value。像这样：

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

然后改为 BSTNode newNode = new BSTNode(value);

Answer 3

insert 中的 else 条件将节点添加到 leftChild 而不是 rightChild。

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

修复后需要调整间距，运行将所有空值都填空，因此数字开始合并在一起。

在 Java 中显示二叉搜索树

Display Binary Search Tree in Java

java

binary-search-tree