-2

我是 python 编程的新手，最近我在编程递归方面遇到了一些问题。考虑我有一个图：a）顶点列表 b）和邻接列表（作为二维列表），我正在尝试获得列表将给我这些顶点的后序遍历顺序（Post_Order_List_of_Node），与此相反，它将告诉任何节点的顺序（Order_of_Node）和所有节点的父亲列表。我编写了以下代码：

我的“订单”变量是全局的，但根据输出，它不会增加。

我不知道为什么，但变量“订单”没有得到更新。

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)
4

1 回答 1

1

order没有得到更新，因为与您声称的不同，它不是全局变量。通过像这样定义你的recursive函数，

def recursive(node,order,father):

在该函数范围内的任何引用order只会修改参数，而不是全局变量。在该函数中，您仅在分支中进行修改order，if但在分支中使用它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. 但是，它确实要求您确保您确实有一棵树（没有循环），或者在开始处理任何子节点之前将节点标记为已访问。

于 2014-05-06T21:57:48.670 回答