вставка в двоичное дерево не работает с использованием Java

Question

В настоящее время я изучаю деревья, используя Java и у меня есть некоторые ошибки, происходящие здесь при вставке элементов в двоичное дерево Я не понимаю, почему это не работает

это код: узел дерева:

public class TNode {
    int data;
    TNode left;
    TNode right;

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

класс дерева:

public class Tree {
    TNode root;

    public Tree(){
        root = null;
    }

    public TNode insertNode(TNode item, int d) {
        if (item == null) {
            return new TNode(d);
        }

         if (d < item.data) {
            item.left = insertNode(item, d);
        }

        if (d > item.data) {
            item.right = insertNode(item, d);
        } else {
            return item;
        }

        return item;
    }

    public void add(int d) {
        insertNode(root, d);
    }
}

Всякий раз, когда я добавляю элемент, корень остается нулевым без правых или левых элементов. если кто-то может помочь, я буду очень благодарен

Answer 1

Прекрасный код, но повторение не идет дальше

item.left = insertNode(item.left, d);
item.right = insertNode(item.right, d);

И начальный рут не обновляется:

root = insertNode(root, d);

Остальная часть или окончательный возврат излишни.

---

Нечто в стиле кода

insertNode имеет узел в качестве входных данных и возвращает обновленное значение узла, поэтому вызов "pattern" должен выглядеть как

X = insertNode(X, d); // X is some expression

Это потому, что java никогда не может присваивать переданному выражению аргумента: у него нет передачи по ссылке, но передача по значению; f(x) никогда не присваивается x.

Answer 2

root всегда равно нулю, поскольку вы никогда не назначаете ему значение.

Вы можете добавить в начало проверки вашего метода и назначить его

public TNode insertNode(TNode item, int d){
    if(item == null){
        TNode node = new TNode(d);
        if (root == null) { 
            root = node;
        }
        return node
    }
    ... rest of method isn't changed...

Также, когда вы рекурсивны, вы должны сделать вызов с подходящим дочерним узлом вместо того, чтобы всегда вызывать с item, поэтому, например, первый случай будет:

    item.left = insertNode(item.left, d);

Для второго случая вы бы просто использовали item.right.