Дерево бинарного поиска не будет добавлять новые узлы? - PullRequest
Новая
       25

Дерево бинарного поиска не будет добавлять новые узлы?

0 голосов
/ 21 ноября 2018

Я пытаюсь написать рекурсивный метод для добавления узла в двоичное дерево поиска (которое не допускает дублирование).По какой-то причине метод работает только тогда, когда дерево пустое, в противном случае он печатает «Дубликат» (даже если он не является дубликатом).Я новичок в программировании и был бы признателен за помощь и советы, чтобы исправить это.Спасибо. 

//add new node to the tree
public void add(int data) {
    Node<Integer> newNode = new Node<>(data); //create new node with the data

    //if the tree is empty, the newNode becomes the root
    if (size() == 0) {
        root = newNode;
        return;
    }
    //otherwise, check if node should be placed to right or left 
    add(data, root);
}
private void add(int data, Node<Integer> node) {
    //base case - found an empty position
    if (node == null) {
        node = new Node<Integer>(data);
    }
    if (data < node.data) {
        add(data, node.left);
    }
    else if (data > node.data) {
        add(data, node.right);
    }
    else if (data == node.data) {
        System.out.println("Duplicate. This value cannot be added to the tree.");
    }
}

Ответы [ 2 ]

0 голосов
/ 21 ноября 2018

В конце рекурсии вы не возвращаете фактический корень BST.«корневой» объект, который у вас есть, указывает на последний вставленный узел.Поэтому каждый раз, когда вы пытаетесь вставить одно и то же значение, оно будет вставлено после последнего вставленного узла, имеющего то же значение.Вот моя реализация: 

class BinarySearchTree { 


    class Node { 
        int key; 
        Node left, right; 

        public Node(int item) { 
            key = item; 
            left = right = null; 
        } 
    } 


    Node root; 

    BinarySearchTree() {  
        root = null;  
    } 


    void add(int data) { 
       root = add(root, data); 
    } 

    Node add(Node root, int data) { 


        if (root == null) { 
            root = new Node(data); 
            return root; 
        } 

        if (data < root.key) 
            root.left = add(root.left, data); 
        else if (data > root.key) 
            root.right = add(root.right, data); 
        else if( data==root.key) {
                System.out.println("Duplicate. This value cannot be added to the tree.");
        }
        return root; 
    } 


    void inorder()  { 
       inorderRec(root); 
    } 


    void inorderRec(Node root) { 
        if (root != null) { 
            inorderRec(root.left); 
            System.out.println(root.key); 
            inorderRec(root.right); 
        } 
    } 
    public static void main(String[] args) { 
        BinarySearchTree tree = new BinarySearchTree(); 


        tree.add(50); 
        tree.add(30); 
        tree.add(20); 
        tree.add(20);
     // print inorder traversal of the BST 
        System.out.println("Inorder traversal");
        tree.inorder(); 

        tree.add(40); 
        tree.add(40);
        tree.add(70); 
        tree.add(60); 
        tree.add(80); 
        System.out.println("Inorder traversal");
        // print inorder traversal of the BST 
        tree.inorder(); 
    } 
}
0 голосов
/ 21 ноября 2018

Когда ваше дерево пусто, узел добавляется к нему правильно.Первая функция add(int data) в порядке.

Проблема существует со второй функцией add(int data, Node<Integer> node).Если в дереве уже есть элемент, вызывается этот метод.Если переданный узел больше или меньше переданного значения, то функция вызывается снова с левым или правым потомком текущего узла.Это значение может быть (будет в конечном итоге) нулевым.Это приводит к созданию узла в базовом случае вашего метода, что приводит к удовлетворению этого условия data == node.data, поскольку узел действительно был создан со значением данных.Следовательно, вы получаете сообщение об ошибке.

Чтобы исправить это, вторая функция может быть изменена, как показано ниже: 

private void add(int data, Node<Integer> node) {
    if (data < node.data) {
        if (node.left != null) {
            add(data, node.left);
        } else {
            node.left = new Node<>(data);
        }
    }
    else if (data > node.data) {
        if (node.right != null) {
            add(data, node.right);
        } else {
            node.right = new Node<>(data);
        }
        add(data, node.right);
    }
    else if (data == node.data) {
        System.out.println("Duplicate. This value cannot be added to the tree.");
    }
}

Смотрите, что базовый случай был удален.Если когда-либо встречается базовый случай не дает нам ссылку на какой-либо узел дерева.Следовательно, добавление data к дереву невозможно (аргумент узла никогда не должен быть нулевым).

Кроме того, код добавляет data в качестве дочернего элемента к node, еслиребенок нольЭто гарантирует, что метод не является рекурсивным с нулевым аргументом node и добавляет data на его законное место, что более важно.

...