相关疑难解决方法(0)

我能够理解preorder遍历而不使用递归,但我很难进行inorder遍历.我也许似乎没有得到它,因为我还没有理解递归的内在工作.

这是我到目前为止所尝试的:

def traverseInorder(node):
    lifo = Lifo()
    lifo.push(node)
    while True:
        if node is None:
            break
        if node.left is not None:
            lifo.push(node.left)
            node = node.left
            continue
        prev = node
        while True:
            if node is None:
                break
            print node.value
            prev = node
            node = lifo.pop()
        node = prev
        if node.right is not None:
            lifo.push(node.right)
            node = node.right
        else:
            break

内部的while循环感觉不对劲.此外,一些元素被打印两次; 也许我可以通过检查之前是否打印过该节点来解决这个问题,但这需要另一个变量,这也是感觉不对.我哪里错了？

我没有尝试过postorder遍历,但我猜它类似,我也将面临同样的概念障碍.

谢谢你的时间!

PS:Lifo和的定义Node:

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right …

我正在寻找一些伪代码、算法或指南，以帮助我为广义图数据结构找到合适的迭代后序遍历算法。

我发现了大量的资源（例如两栈或一栈算法）非常适合树，但对于图来说却很糟糕，因为它们无法处理循环/后边缘、交叉边缘等。

我已经成功编写了一个递归后序图遍历算法，如下所示：

template<typename V, typename E>\nvoid tGraph<V, E>::RecursivePostOrderSearch(const tGraph& g, const VertexType& u, std::set<VertexType>& visited, std::vector<VertexType>& result)\n{\n    if (visited.find(u) == visited.end())\n    {\n        visited.insert(u);\n\n        EdgeSet edgesOut = g.outgoingEdgesOf(u);\n\n        for(typename EdgeSet::const_iterator iter = edgesOut.begin(); iter != edgesOut.end(); iter++)\n        {\n            RecursivePostOrderSearch(g, iter->second.second, visited, result);\n        }\n\n        result.push_back(u);\n    }\n}\n\ntemplate<typename V, typename E> std::vector<V> tGraph<V, E>::postOrderList(const VertexType& v) const\n{\n    std::set<V> visited;\n    std::vector<V> result;\n\n    RecursivePostOrderSearch(*this, v, visited, result);\n\n    return result;\n}\n

其中V是节点类型，E是边类型——“权重”对和传入/传出节点对。

如果我在下图上运行::postOrderList（带有根节点A）：