这个 BST 实现有什么问题？

Question

为什么我在做 search(7) 时得到 false？我尝试了递归解决方案，它工作正常.. 尝试用循环实现失败

public class BST {

    class Node {
        int data;
        Node left , right;

        public Node(int data) {
            this.data = data;
            this.left = this.right = null;
        }
    }

    Node root;

    public BST() {
        this.root = null;
    }

    public void insert(int data) {
        // create a new node and start iteration from root node
        Node newNode = new Node(data);
        Node currentNode = this.root;

        while (true) {
            if (currentNode == null) {
                currentNode = newNode;
                break;
            }

            if (data < currentNode.data) { // if data is less go left
                currentNode = currentNode.left;
            } else if (data > currentNode.data) {   // if data is greater go right
                currentNode = currentNode.right;
            } else {    // do nothing for duplicates
                break;
            }
        }
    }

    public boolean search(int data) {
        Node currentNode = this.root;

        while (true) {
            if (currentNode == null) {
                return false;
            }

            if (data == currentNode.data) {
                return true;
            } else if (data < currentNode.data) {
                currentNode = currentNode.left;
            } else {
                currentNode = currentNode.right;
            }
        }
    }

    public static void main(String... args) {
        BST tree = new BST();

        tree.insert(15);
        tree.insert(7);

        System.out.println(tree.search(7));
    }
}

Answer 1

问题出在 insert 方法中 - 您没有在树中正确插入节点。

如果树是空的，你应该分配给this.root，而不是currentNode。分配给 currentNode 对 this.root 没有影响。

目前，您的代码没有插入树中的任何节点；它只是将新节点分配给 insert 方法的局部变量，即 currentNode.
如果条件data < currentNode.data为真，则需要检查currentNode.left是否为null。如果是，则link新节点与当前节点如下图：
```
currentNode.left = newNode; 
```
如果 currentNode.left 不是 null，则执行以下操作：
```
currentNode = currentNode.left;
```
目前，您的代码将 currentNode 移动到 null，然后将 newNode 分配给 currentNode ，而不引用其父节点在树中.
也为 data > currentNode.data 执行第 2 步。

改变insert方法的实现，如下所示：

public void insert(int data) {

    Node newNode = new Node(data);
    
    if (this.root == null) {
        this.root = newNode;
        return;
    }
    
    Node currentNode = this.root;

    while (true) {
        if (data < currentNode.data) {
            if (currentNode.left == null) {
                currentNode.left = newNode;
            } else {
                currentNode = currentNode.left;
            }
        } else if (data > currentNode.data) {
            if (currentNode.right == null) {
                currentNode.right = newNode;
            } else {
                currentNode = currentNode.right;
            }
        } else {
            break;
        }
    }
}

这个 BST 实现有什么问题？

Whats wrong in this BST implementation?

java

data-structures

binary-search-tree