在Python中使用递归进行后序遍历

Question

我刚开始学习Python编程，最近在编写递归程序时遇到了一些问题。假设我有一个图，包含：a) 顶点的列表 b) 邻接表（用二维列表表示）。我想得到一个列表，这个列表能告诉我这些顶点的后序遍历顺序（Post_Order_List_of_Node），还有一个反向的列表，能告诉我任何一个节点的顺序（Order_of_Node），以及一个包含所有节点父节点的列表。我写了以下这段代码：

我的“order”变量是全局的，但根据输出结果，它并没有增加。

我不知道为什么，“order”变量没有被更新。

def Post_Order(node,order,father):
    Order_of_Node = [No_of_Nodes]*No_of_Nodes   #Initialization
    Post_Order_List_of_Node = [No_of_Nodes]*No_of_Nodes     #Initialization
    def recursive(node,order,father):
        if len(Spanning_Tree[node]) == 0:
            Order_of_Node[node] = order
            Post_Order_List_of_Node[order] = node
            order = order + 1
            Father_List[node] = father
            del(Spanning_Tree[father][0])
            return
        else:
            while(len(Spanning_Tree[node])!=0): 
            recurse(Spanning_Tree[node][0],order,node)
    recurse(node,order,father)
    return Post_Order_List_of_Node,Order_of_Node
Father_List = [0]*No_of_Nodes
root = 0
father = 0
order = 1
Order = []
Order = Post_Order(root,order,father)

Answer 1

order没有被更新，因为它并不是你所说的全局变量。你这样定义你的recursive函数：

def recursive(node,order,father):

在这个函数的范围内，任何对order的引用只会修改参数，而不会修改全局变量。在这个函数里，你只在if分支中修改了order，而在else分支中使用了它。所以参数的更新并没有传递出去。

要想把order当作全局变量使用，你需要这样声明它：

def recursive(node, father):
    global order
    if ...

---

你代码中的另一个问题是，当你为Post_Order_List_of_Node设置值时，你使用了

Post_Order_List_of_Node[order] = node

但是，order是从1开始的，而不是从0开始，所以在处理最后一个节点时会出错。你需要使用

Post_Order_List_of_Node[order-1] = node

来代替。

---

你可能注意到了一个效率问题，就是你处理节点的方式：

def recursive(node,father):
    if len(Spanning_Tree[node]) == 0:
        # Process node
    else:
        while(len(Spanning_Tree[node])!=0): 
            # Process child

在一次recursive调用中，你只处理子节点或当前节点。你的代码之所以能工作，是因为有while循环——你对每个有子节点的子节点调用recursive两次。与其这样做，不如改成这样：

def recursive(node,father):
    for child in Spanning_Tree[node]:
        # process child
    # process node

这样做的好处是，不需要修改Spanning_Tree。不过，这要求你确保树是有效的（没有循环），或者在开始处理任何子节点之前，先标记节点为已访问。