深度第一次迭代加深算法首先打印二叉樹的寬度

我不是程序員，但作爲我的個人項目的一部分我很想了解是否有遞歸解決方案能夠打印二叉樹廣度第一，水平順序？我知道可以使用迭代深度優先算法？深度第一次迭代加深算法首先打印二叉樹的寬度

#Helper method 
def getChildren(node): 
    children=[] 
    hasLeft = node.left is not None 
    hasRight = node.right is not None 
    if not hasLeft and not hasRight: 
     return [] 
    if hasLeft: 
     children.append(node.left) 
    if hasRight: 
     children.append(node.right) 
    return children 

def DLS(node, depth): 
    """Depth Limited Search""" 
    if (depth == 0): 
     return node 
    elif (depth > 0): 
     print node.value, 
     children = getChildren(node) 
     for child in children: 
      DLS(child, depth-1) 
    else: 
     return False

對於下列二叉樹：
(1)3 (2)2 (3)1 (4)1 (5)1 (6)1 (7)0 (8)1 (9)0

我得到這個遍歷輸出： (1)3 (2)2 (4)1 (8)1 (9)0 (5)1 (3)1 (6)1 (7)0 None

這不是水平順序，但預購深度優先。

我是否必須迭代DLS函數的深度？我將如何實現二叉樹的級別打印輸出？

非常感謝亞歷

來源

2012-03-16 Alex2134

嗨@andrewcooke我確實認爲我在問我三個問題的同一個問題;但我一直在思考一些想法和反饋意見，所以熱衷於繼續詢問這個問題。我並不想刪除我的問題，因爲我想回顧一下我在學習時給出的回覆。有什麼方法可以將我的舊問題歸檔，所以我可以回顧一下嗎？謝謝 – Alex2134 2012-03-16 23:15:41

在數據結構方面，深度優先和廣度優先之間的區別是，深度優先使用堆棧和廣度優先使用的隊列。

深入優先，這個想法是「處理你處理的最後一件事的後果」。所以對於一個堆棧，你總是彈出被推送的最後一個節點，並且你得到正確的行爲。

在廣度優先，這個想法是「首先處理所選節點的所有後果，然後繼續前進」。所以你首先找出後果（並存儲它們），然後纔開始按照你找到的順序處理它們。最簡單的數據結構就是一個隊列。

問題是遞歸使用堆棧（調用堆棧）。所以你沒有看到數據結構，但它確實存在。由於沒有（簡單的）排隊調用方式，因此不能使用顯式隊列將廣度優先搜索轉換爲代碼。

如果您需要有關隊列的廣度優先實現的信息，我建議您查看Wikipedia。

來源

2012-03-16 23:07:45

Hi @OmriBarel我已經使用隊列實現了廣度優先搜索。我認爲，我應該堅持這個功能。感謝Alex – Alex2134 2012-03-16 23:18:55

深度第一次迭代加深算法首先打印二叉樹的寬度

回答

相關問題