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

Эта задача обычно выполняется во время рекурсивного обхода почтового заказа, и в Интернете есть несколько примеров. Один из них находится здесь , но мне интересно, правильно ли это, потому что кажется, что метод _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)? Спасибо!


java algorithm destroy binary-tree
person user21    schedule 30.12.2016    source источник
comment
Код, на который вы ссылаетесь, вводит в заблуждение. Похоже, кто-то взял пример с C++ и попытался дословно переписать его на Java. Концепция deleteTree просто не применима к Java. Java-версия метода, как вы указали, на самом деле ничего не делает.   -  person Sam    schedule 30.12.2016

Ответы (2)


arrow_upward
0
arrow_downward

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

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;
        }
    }
}
person David Eisenstat    schedule 30.12.2016

arrow_upward
0
arrow_downward

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

person GreenSkies    schedule 30.12.2016