algorithm - 非递归 n 射线树遍历

Question

给定的类定义为:

class Node {
    public Double value;
    public List<Node> children;
}

将下面的程序翻译成非递归的:

public static void process(Node node) { 
    for (int i = 0; i < node.children.size(); i++) {
        Node child = node.children.get(i);
        if (child.value < node.value) {
            process(child);
        }
    }
    System.out.println(node.value);
    for (int i = 0; i < node.children.size(); i++) {
        Node child = node.children.get(i);
        if (child.value >= node.value) {
            process(child);
        }
    }
}

普通的树遍历算法似乎适合这里，因为出栈需要检查条件。

实在想不出办法。

使用代码中所示的示例树时，我得到以下输出:

5.76.01.012.013.05.08.07.010.09.05.515.011.014.0

public class Node {
public Double value;
public List<Node> children;
public Node(Double value) {
    this.value = value;
    this.children = new ArrayList<Node>();
}
public void addChild(Node node) {
    children.add(node);
}
public static Node createSample() {
    Node node = new Node(10.0);
    Node node1 = new Node(15.0);
    Node node2 = new Node(6.0);
    Node node3 = new Node(11.0);
    Node node4 = new Node(14.0);
    Node node5 = new Node(5.0);
    node.addChild(node1);
    node.addChild(node2);
    node.addChild(node3);
    node.addChild(node4);
    Node node51 = new Node(8.0);
    Node node52 = new Node(7.0);
    node5.addChild(node51);
    node5.addChild(node52);
    node.addChild(node5);
    Node node11 = new Node(9.0);
    Node node12 = new Node(5.5);
    node1.addChild(node11);
    node1.addChild(node12);
    Node node21 = new Node(5.7);
    Node node22 = new Node(12.0);
    node2.addChild(node21);
    node2.addChild(node22);
    Node node31 = new Node(13.0);
    Node node32 = new Node(1.0);
    node22.addChild(node31);
    node22.addChild(node32);
    return node;
}

Answer 1

一种方法是手动实现递归过程的功能，在进行递归调用时利用内存使用的相同机制。即利用内存的栈结构进行递归调用。非递归树遍历也可以通过使用类似于内存使用的堆栈来模拟。然后，遍历将包含一个循环，在该循环中，您不断将 child 插入堆栈，并访问(弹出)第一个 child 。当堆栈中没有更多节点时，循环将终止。这与您正在进行的递归遍历相同，也称为后序树遍历。如果您处理的不是树而不是树，甚至可以将这种方法视为深度优先搜索。

但是，您在问题中没有口头提及的一件事是需要按照 child 值(value)观的数量级来处理他们。为此，您只需要调整将元素放入堆栈的顺序即可。请记住，由于堆栈是一种 LIFO(后进先出)数据结构，因此您需要将值高于父节点的元素放在值较小的元素之前。

下面是一个示例，它不是我上面描述的解决方案的高效实现。您可能会在工作中观察到此解决方案 here ，产生与您在问题中提供的相同的输出。

class StackNode {
    public Node node;
    public boolean largerChildrenPushed;
    public StackNode(Node n) {
        this.node = n;
        this.largerChildrenPushed = false;
    }
}
public static void process(Node node) {
    Stack st = new Stack();
    st.push(new StackNode(node));
    while(!st.empty()) {
        StackNode stParent = (StackNode)st.pop();
        Node parent = stParent.node;
        if(!stParent.largerChildrenPushed) {
            for (int i = parent.children.size() - 1; i >= 0; i--) {
                Node child = parent.children.get(i);
                if (child.value >= parent.value) {
                    st.push(new StackNode(child));
                }
            }
            st.push(stParent);
            stParent.largerChildrenPushed = true;
            for (int i = parent.children.size() - 1; i >= 0; i--) {
                Node child = parent.children.get(i);
                if (child.value < parent.value) {
                    st.push(new StackNode(child));
                }
            }
        }
        else {
            System.out.println(parent.value);
        }
    }
}