Проблемы с функцией редактирования Binary TreeNode - PullRequest
Новая
       31

Проблемы с функцией редактирования Binary TreeNode

0 голосов
/ 11 февраля 2019

У меня возникли проблемы с моим кодом.

Цель этой функции - пройти через двоичное дерево и отредактировать его так, чтобы ветви из определенной точки были заменены новыми, размещенными под "новым узлом".В настоящее время он возвращает то же значение для дерева, с которого он начал (поэтому current = newNode фактически не редактирует исходное дерево).

Кто-нибудь может объяснить, почему это так?Спасибо. 

 public static Node editTree(Node current, Node newNode, String value) {
        if (current == null) {
            return null;
        }

        if (current.value.equals(value)) {
            current = newNode;
            return current;
        }

        if (!current.isLeaf()) {
            editTree(current.getLeft(), newNode, value);
            editTree(current.getRight(), newNode, value);
            return current;
        }

        return current;
    }

Это должно быть выполнено таким образом, чтобы сначала проходить дерево (исходное дерево), пока не будет найдено определенное значение.Затем узел, в котором находится значение, полностью заменяется новым узлом, который содержит свое собственное значение и свои собственные левый и правый узлы.Затем глобальная переменная Node устанавливается равной значению вновь отредактированного дерева, которое затем используется для сброса исходного значения деревьев.Причина, по которой это не может быть сделано каким-либо другим способом, заключается в том, что я не могу установить значения левого и правого узлов в классе узлов, поскольку это не разрешено.

Ответы [ 2 ]

0 голосов
/ 11 февраля 2019

Назначение нового значения для current не окажет влияния вне метода.Я думаю, что вы должны использовать возвращаемое значение: 

public static Node editTree(Node current, Node newNode, String value) {
        if (current == null) {
            return null;
        }

        if (current.value.equals(value)) {
            return newNode;
        }

        if (!current.isLeaf()) {
            current.setLeft(editTree(current.getLeft(), newNode, value));
            current.setRight(editTree(current.getRight(), newNode, value));
        }

        return current;
    }

ОБНОВЛЕНИЕ: полный код и результаты теста 

public class Node {
    public final String value;
    private Node left;
    private Node right;

    Node(String value, Node left, Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    public boolean isLeaf() {
        return left == null && right == null;
    }

    @Override
    public String toString() {
        return "Node{" + "value=" + value + ", left=" + left + ", right=" + right + '}';
    }
}

Метод теста: 

public static void main(String[] args) {
    Node tree = new Node("b",
            new Node("a", null, null), new Node("c", null, null));
    System.out.println(tree);
    tree = editTree(tree, new Node("d", null, null), "c");
    System.out.println(tree);
}

Результаты: 

Node{value=b, left=Node{value=a, left=null, right=null}, right=Node{value=c, left=null, right=null}}
Node{value=b, left=Node{value=a, left=null, right=null}, right=Node{value=d, left=null, right=null}}
0 голосов
/ 11 февраля 2019

В строке current = newNode; вы просто меняете ссылку на переменную current в вашем методе.Это не повлияет на оригинальное дерево.Вам необходимо установить newNode как value для предыдущего узла.

Для получения дополнительной информации см. Является ли Java «передачей по ссылке» или «передачей по значению»?

...