如何通過Python中非二叉樹的遞回深度優先搜索列出每個父節點的子節點系數？-有解無憂

我有一個具有以下結構的非二叉樹：注意：系數僅指在 1 個父節點中存在多少子節點變數。因此，父節點的系數與此定義/分配無關。注意：確切的組成是隨機的。父母可以有任意數量的孩子，不同的父母可以有同一個孩子（即 F 和 B 都由 E 組成，盡管分別為 1E 和 4E）。如何通過Python中非二叉樹的遞回深度優先搜索列出每個父節點的子節點系數？

我已經通過字典復制了這個結構：

dicts = {str:{str:int}}
dicts["A"] = {"B":2,"C":2,"D":1}
dicts["B"] = {"E":4}
dicts["C"] = {"F":4, "G":1}
dicts["F"] = {"E":1}
dicts["G"] = {"D":1,"E":1,"H":1}

我最終想僅根據基礎層子變數來描述每個父節點。也就是說，就“E”、“D”和“H”而言，因為它們沒有其他子級，因此被視為基礎層。從數學上講，這涉及到到達根/基層節點，并將系數乘以父節點。即，對于A 的左分支，它由8E 組成。然后，另外 8 個 E（通過 2C -> 4F -> E） 2 個 E（2C -> G -> E）。“D”和“H”將采用類似的方法。

由于樹是非二進制的，并且可以有任意數量的具有任意深度的孩子，我知道我必須利用遞回來完成定義。

我已經設法構建了一個正確遍歷前幾條腿的腳本，但是當我移動到其他腿時（或者甚至只是先發制人地想到更復雜、可能的結構），我發現我需要增加復雜性來處理不斷變化的路徑。這讓我覺得我錯誤地處理了這個問題。我真的需要在遞回中嵌套更多條件嗎？還是我應該以不同的方式處理這個問題？

注意：在正確遍歷 A->2B->4E & A->2C->4F->E（導致 {A:{E:16}}）后，此回圈無限回圈。

dicts = {str:{str:int}}
dicts["A"] = {"B":2,"C":2,"D":1}
dicts["B"] = {"E":4}
dicts["C"] = {"F":4, "G":1}
dicts["F"] = {"E":1}
dicts["G"] = {"D":1,"E":1,"H":1}

nullvalues = ["E","D","H"]

tempIntArray = []
tempCheckedArray = {str:[str]}
tempAnsweredArray = {str:{str:int}}
persistentN = ""

def recursive_traversal(n):
    global persistentN
    if persistentN == "":
         persistentN = n
    for x in dicts[n]:
        if n not in tempCheckedArray.keys() or x not in tempCheckedArray[n]:
            if x in nullvalues:
                product = 1
                tempIntArray.append(dicts[n][x])
                for a in tempIntArray:
                    product = a * product
                if persistentN in tempAnsweredArray.keys():
                    if x in tempAnsweredArray[persistentN].keys():
                        tempValue = tempAnsweredArray[persistentN][x]   product
                        tempAnsweredArray[persistentN][x] = tempValue
                    else:
                        tempAnsweredArray.update({persistentN:{x:product}})
                else:
                    tempAnsweredArray.update({persistentN:{x:product}})

                product = 1
                if persistentN not in tempCheckedArray.keys():
                    tempCheckedArray[persistentN] = [n]
                else:
                    tempCheckedArray[persistentN].append(n)
                tempIntArray.clear()
                return recursive_traversal(persistentN)
            else:
                tempIntArray.append(dicts[n][x])
                return recursive_traversal(x)
           

recursive_traversal("A")
print(tempAnsweredArray)

我在當前代碼塊中看到的唯一前進路徑是添加一個檢查，該檢查在可決議字串中搜索已經經過的節點路徑并避免它們。類似 {"A": ["ABBC", "ACCFFE"]} 并運行一個條件來檢查路徑是否已被遍歷。但同樣，這在某種程度上感覺像是錯誤的方法。

uj5u.com熱心網友回復：

您描述的不是樹，而是有向無環圖（DAG）。

您確實需要深度優先遍歷，并檢測已訪問的節點。但：

您需要在遞回函式之外的所有節點上單獨回圈，因為僅從節點“A”開始遞回時，不能保證所有節點都可以訪問。
您需要為節點提供三種可能的狀態：
- 尚未訪問
- 訪問已開始（正在遍歷后代節點）
- 訪問已結束（所有后代節點都已訪問）
如果遇到處于中間狀態的節點，則圖有一個回圈，應該放棄該程序，因為這意味著一個節點可以分解為無限數量的基本專案。

您也有型別表示法的問題。這不是你想的那樣：

dicts = {str:{str:int}}

這會創建一個不為空的字典，但它會獲取一個恰好是str物件的鍵。這不是故意的。你想要的是宣告一個空字典的型別：

dicts: {str:{str:int}} = {}

這是我將如何實作它：

def resolve_graph(graph):
    visited = { node: 0 for node in graph }
    
    def dfs(node):
        if node not in graph or not graph[node]:  # It's a leaf
            return { node: 1 }
        if visited[node]:
            if visited[node] != "end":
                raise ValueError("graph has cycles!")
            return graph[node]

        visited[node] = "start" 
        leaves = {}
        for child, childcount in graph[node].items():
            for leaf, leafcount in dfs(child).items():
                if leaf not in leaves:
                    leaves[leaf] = 0
                leaves[leaf]  = childcount * leafcount
        graph[node] = leaves
        visited[node] = "end"
        return leaves

    for node in graph:
        if not visited[node]:
            dfs(node)

dicts: {str:{str:int}} = {}
dicts["A"] = {"B":2,"C":2,"D":1}
dicts["B"] = {"E":4}
dicts["C"] = {"F":4, "G":1}
dicts["F"] = {"E":1}
dicts["G"] = {"D":1,"E":1,"H":1}

resolve_graph(dicts)

print(dicts)

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/513474.html

標籤：Python递归树深度优先搜索

上一篇：從物件轉換物件組合

下一篇：如何將制表符縮進串列轉換為層次結構