двоичное дерево поиска tree.root возвращает ноль

Question

Я нашел двоичный код вставки дерева поиска на веб-сайте,

https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/

, а часть кода, как показано ниже,

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

, и яМы думали, что нам не нужны никакие операторы return, потому что сам root является ссылочным типом (Node), поэтому достаточно обновить root.

, поэтому я изменил код следующим образом.

class BinarySearchTree {

class Node {
    int key;
    Node left, right;

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

Node root;

BinarySearchTree() {
    root = null;
}

void insert(int key) {
    insertRec(root, key);
}

/* A recursive function to insert a new key in BST */
void insertRec(Node root, int key) {

    if (root == null) {
        root = new Node(key);
    }

    if (key < root.key)
        insertRec(root.left, key);
    else if (key > root.key)
        insertRec(root.right, key);
}

// Driver Program to test above functions 
public static void main(String[] args) {
    BinarySearchTree tree = new BinarySearchTree(); 

    tree.insert(50);
    tree.insert(20);

    System.out.println(tree.root);
    }
}

, но tree.root возвращает ноль.

почему это происходит?

Answer 1

/* A recursive function to insert a new key in BST */
void insertRec(Node root, int key) {

    if (root == null) {
        root = new Node(key);
    }    
}

Это называется "эффектом теней".

Это означает, что ваша корневая заметка из родительского класса затеняется корневым узлом в вашем методе.Чтобы исправить это, используйте this.root для ссылки на родительский класс и инициализируйте объект.

Дополнительная информация: читайте «Shadowing» в статье.Это объяснили очень хорошо.

http://ocpj8.javastudyguide.com/ch03.html

Answer 2

В вашем конструкторе вы не инициализируете rootNode.Ваш ключ также не преобразуется в узел, и вы не устанавливаете вставленный узел в левый или правый узел.Кроме того, вы ничего не делаете с узлом, равным текущему узлу, который вы проходите.

Answer 3

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

Просто return значение root и обновляйте глобальное root для дерева.

Node insertRec(Node root, int key) {

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

    if (key < root.key)
        root.left = insertRec(root.left, key);
    else
       root.right  = insertRec(root.right, key);

   return root;
}

Наконец, обновите ваш глобальный root.

tree.root = tree.insert(50);
    tree.root = tree.insert(20);

Полный код:

class BinarySearchTree {

class Node {
    int key;
    Node left, right;

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

Node root;

BinarySearchTree() {
    root = null;
}

 Node insert(int key) {
   return insertRec(root, key);
}

/* A recursive function to insert a new key in BST */
Node insertRec(Node root, int key) {

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

    if (key < root.key)
        root.left = insertRec(root.left, key);
    else
       root.right  = insertRec(root.right, key);

   return root;
}

// Driver Program to test above functions 
public static void main(String[] args) {
    BinarySearchTree tree = new BinarySearchTree(); 

    tree.root = tree.insert(50);
    tree.root = tree.insert(20);

    System.out.println(tree.root.key);
    }
}

Answer 4

root = new Node(key); обновляет локальную переменную, она не обновляет корень дерева (this.root), и не должна.Поэтому это назначение не обновляет дерево.

Когда вы возвращаете только что созданный Node (как в исходном коде, который вы изменили), вы можете назначить его либо корнем дерева (как исходный код делал с root = insertRec(root, key);) или левым или правым потомком существующего узла дерева (как исходный код делал с root.left = insertRec(root.left, key); или root.right = insertRec(root.right, key);).Вот как обновляется дерево.

РЕДАКТИРОВАТЬ: Java является языком передачи по значению, а не по ссылке.Когда вы передаете переменную методу, этот метод не может изменить значение переданной переменной.Если вы передадите в метод переменную, значение которой равно null, и этот метод присвоит ему значение, эта переменная все равно будет содержать null, как только метод вернется.