Блог

Почему я получаю false во время работы search(7) ? Я попробовал рекурсивное решение, оно работает нормально.. попытка реализации с помощью цикла не удалась

 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));
    }
}


 

Проблема кроется внутри insert метода — вы неправильно вставляете узлы внутри дерева.

1. Если дерево пустое, вы должны назначить this.root , нет currentNode . Назначение currentNode не влияет на this.root .

   В настоящее время ваш код не вставляет какой-либо узел внутри дерева; он просто присваивает новый узел локальной переменной insert метода, т. Е. currentNode .

2. Если условие data < currentNode.data истинно, то вам нужно проверить currentNode.left , так это null или нет. Если это так, то свяжите новый узел с текущим узлом, как показано ниже:

    currentNode.left = newNode; 
    

   Если currentNode.left нет null , то выполните следующие действия:

    currentNode = currentNode.left;
    

   В настоящее время ваш код перемещает значение currentNode to null , а затем присваивает значение newNode to currentNode без ссылки на его родительский узел в дереве.

3. Сделайте 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;
        }
    }
}