Bezdepbonusu7Программирование: статьи и ответы
Меню

Вопрос

Итеративное уничтожение бинарного дерева в java

Автор вопроса: user21Ответов: 2

Эта задача обычно выполняется во время рекурсивного обхода почтового заказа, и в Интернете есть несколько примеров. Один из них находится здесь , но мне интересно, правильно ли это, потому что кажется, что метод _deleteTree() выполняет только BFS и не выполняет никаких операций с узлами, а удаление выполняется путем простого присвоения корню дерева значения null. Без сомнения, он вернет пустое дерево. Но правильно ли удалить ссылки на все узлы дерева?

Кроме того, для итеративного обхода почтового заказа, скажем, как показано ниже

public TreeNode postorderTraversal(TreeNode root) {
    if(root==null) return null;
    Stack<TreeNode> stack1=new Stack<>();
    Stack<TreeNode> stack2=new Stack<>();
    TreeNode cur=root;
    stack1.push(cur);
    while(!stack1.isEmpty()){
        cur=stack1.pop();

        if(cur!=null){
            stack2.push(cur);
        }

        if(cur.left!=null){
            stack1.push(cur.left);
        }
        if(cur.right!=null){
            stack1.push(cur.right);
        }
    }

    while(!stack2.isEmpty()){
        //elements poped will be in post order sequence
        }
    return root;
}

Как итеративно уничтожить бинарное дерево? Может ли кто-нибудь дать пример кода (java)? Спасибо!

  • Код, на который вы ссылаетесь, вводит в заблуждение. Похоже, кто-то взял пример с C++ и попытался дословно переписать его на Java. Концепция deleteTree просто не применима к Java. Java-версия метода, как вы указали, на самом деле ничего не делает. Sam 30.12.2016

javaalgorithmdestroybinary-tree

Ответы

Ответ 1 · David Eisenstat

Есть лучшее решение, которое использует сами узлы дерева для хранения очереди. Что-то вроде этого:

static void clear(Node root) {
    while (root != null) {
        Node left = root.left;
        if (left == null) {
            Node right = root.right;
            root.right = null;
            root = right;
        } else {
            // Rotate the left child up.
            root.left = left.right;
            left.right = root;
            root = left;
        }
    }
}

Ответ 2 · GreenSkies

Обычно, когда вы назначаете узлу значение null, вы технически избавляетесь от всех данных. Как и в случае со связанным списком, когда вы разрываете его соединение, устанавливая его "следующий" за слово равным нулю, вы удаляете список, а сборщик мусора Java позаботится обо всем остальном. Таким образом, в коде Java, который вы связали, они делают то же самое, как только корень определен как не имеющий дочерних элементов.

Перевод вопроса и ответов сообщества Stack Overflow, лицензия CC BY-SA. Оригинал на Stack Overflow.

Похожие материалы