2014-05-06 29 views
-2

我是一個新的python編程,最近我在編程遞歸時遇到了一些問題。考慮我有一個Graph作爲:a)頂點列表b)和一個鄰接列表(作爲2維列表),我試圖得到一個列表,這將給我這些頂點的Postorder遍歷順序(Post_Order_List_of_Node),這將反映任何節點的順序(Order_of_Node)和所有節點的父親列表。我寫了下面這段代碼:在Python中使用遞歸進行後序遍歷

我的「訂單」變量是全局的,但根據輸出,它沒有增加。

我不知道爲什麼,但變量「訂單」沒有得到更新。

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) 
+0

好了,所以我無法發佈測試輸入和輸出,因爲Stackoverflow認爲它也是代碼的一部分,不讓我發佈問題。所以這裏是: 例如我的樹是:「[[1,2],[3],[],[4],[5,6],[],[]]」 但我的Order_of_Node是: 「[7,1,1,1,1,1,1]」 和Post_Order_List_of_Node =「[7,2,7,7,7,7]」 – user2435273

+0

您的代碼不一致且非常規(變量名,間距)等等,因此會更難以閱讀。 –

+0

此代碼不起作用,因爲'Post_Order()'在使用後定義。也許還有其他的錯誤。 – user3159253

回答

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。但是,它確實要求您在開始處理任何子項之前確保您確實有一棵樹(沒有循環)或者將節點標記爲已訪問節點。