Блог

У меня проблема с моим кодом, я создаю структуру данных двоичного дерева поиска, и когда я вызываю функцию с дочерним элементом узла, а затем присваиваю значение этому дочернему элементу внутри функции, это не обновляет дочерний элемент узла.

 //*** Pseudo-ish Code ***

class BSTNode {

    private BSTNode lChild;
    private BSTNode rChild;
    private int key;

    public BSTNode(int key) {
        this.lChild = null;
        this.rChild = null;
        this.key = key;
    }

    //getters and setters for each field ^
}

class BST {

    private BSTNode root;

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

    public void insert(BSTNode currentNode, int value) {

        BSTNode newNode = new BSTNode(value);

        if (currentNode == null) {

            currentNode = newNode;
            if (this.root == null) {
                this.root = currentNode;
            }

        } else {

            //ignore the newNode == currentNode value statement right now

            if (newNode.getValue() < currentNode.getValue()) {
                insert(currentNode.getlChild(), value);
            } else if (newNode.getValue() > curNode.getValue()) {
                insert(curNode.getrChild(), value);
            }
        }
    }

    //getters and setters
}
  

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

 BST testBST = new BST();

testBST.insert(testBST.getRoot(), 10);
testBST.insert(testBST.getRoot(), 7);

System.out.print(testBST.getRoot()); 
System.out.print(" ");
System.out.print(testBST.getRoot().getlChild());
  

Это приведет 10 к исключению NullPointerException. Я понимаю, это потому, что каким-то образом 7 не был выделен как дочерний элемент 10, но я не знаю почему? У меня проблема с областью видимости, или это потому, что я вызываю рекурсивно с помощью getlChild() в моей функции insert, что у меня нет доступа к фактическому закрытому полю lChild?

ПРИМЕЧАНИЕ: Я использовал sysout для отладки своего кода, и я заметил, что рекурсия действительно работает, и она правильно присваивает currentNode 7, но затем, как только функция выполняется, это похоже на то, что currentNode больше не ссылается на дочерний элемент начального корневого узла.

Проблема здесь:

 BSTNode newNode = new BSTNode(value);
  

Каждый раз, когда компьютер вызывает рекурсивный метод insert() , он создает new BSTNode() . Вы просто хотите добавлять один new BSTNode() каждый раз, но это создает узлы снова и снова. Например, вы хотите добавить 3, и для этого она должна быть вызвана insert() 4 раза. Вместо создания только 1 узла будет создано 4 узла.

Что я сделал, помимо удаления некоторых ошибок, я создал рекурсивный insertValue() метод в BSTNode class . Таким образом, вам не нужно отслеживать currentNode каждый раз, когда вы вызываете этот метод. Поскольку каждый узел будет вызывать свой собственный insertValue() метод.

 //*** Pseudo-ish Code ***
class BSTNode 
{
    public BSTNode lChild;
    public BSTNode rChild;
    public int key;

    public BSTNode(int key) 
    {
        this.lChild = null;
        this.rChild = null;
        this.key = key;
    }

    /* Create INSERT function in BSTNode class so that you dont have to give the "CurrentNode" everytime
       you call this method, Now you just have to pass the "Key"*/
    public void insertValue(int insertValue)
    {
        if(insertValue < key)
        {
            if(lChild == null)
                lChild = new BSTNode(insertValue);
            else
                lChild.insertValue(insertValue);
        }
        else if(insertValue > key)
        {
            if(rChild == null)
                rChild = new BSTNode(insertValue);
            else
                rChild.insertValue(insertValue);
        }
        else;
    }
}

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

    // just create the root if not present else it'll call the recursive method of BSTNode class
    public void insert(int value)
    {
        if(root == null)
            root = new BSTNode(value);
        else
            root.insertValue(value);
    }

    // you didn't provide these methods so i wrote my own just to get your code runing 
    public BSTNode getRoot()
    {
        return root;
    }

    public int getRootValue()
    {
        return root.key;
    }
}

public class BSTMain
{
    public static void main(String[] args)
    {   
        BST testBST = new BST();
        testBST.insert(10);
        testBST.insert(7);

        System.out.print(testBST.getRootValue()); 
        System.out.print(" ");
        System.out.print(testBST.getRoot().lChild.key);
    }
}
  

ПРИМЕЧАНИЕ: Я добавил некоторые методы, подобные getRoot() просто для того, чтобы заставить ваш код работать, поскольку вы их не предоставили.