我試圖理解下面的代碼是如何工作的。代碼按其應有的方式執行，但我不理解其中的部分內容。這是一種二叉搜索樹的中序遍歷方法：def traverse(self): def io(node): print("restart") #added to code see whats happening if node is not None: print("b4 app", node.data) #added to code see whats happening if node.left: io(node.left) result.append(node.data) if node is not None: print("aft app",node.data,node.right is None) #added to code see whats happening if node.right: #[1] skipped bc node.right is None print("inside right") #added to code see whats happening io(node.right) if self.root is None: return None else: result=[] io(self.root) return resultNode以下是二叉搜索樹的類結構：class Node: def __init__(self, data, left=None, right=None): self.data = data self.left=left self.right=right這是遍歷 BST 的輸出：restartb4 app 9restartb4 app 4 #[3]restartb4 app 3 aft app 3 True # <--- I thought it would end here? [0]aft app 4 False #[2]inside rightrestartb4 app 6aft app 6 Trueaft app 9 Falseinside rightrestartb4 app 17aft app 17 True[3, 4, 6, 9, 17] #<-- ordered list of nodes (this output is correct)它正在遍歷的 BST：""" 9 / \ 4 17 / \ 3 6"""在函數到達我指向的點（請參閱[0]）之后，node.right是，因此將跳過代碼中的None下一條語句（請參閱）。這是代碼在結束之前最后一次調用自身（據我所知？）。if[1]if如果跳過該語句（上次io調用該函數時），遞歸將如何繼續？另外，從輸出中的下一行可以看出（請參閱[2]），它繼續node=4, node.left=3, node.right=6，它是node=3的父級并提前傳遞到函數中（請參閱[3]）。那么io函數又是如何被調用的，為什么是node=4輸入呢？
1 回答
交互式愛情
TA貢獻1712條經驗 獲得超3個贊
這段代碼是一種非常令人困惑的樹遍歷編寫方式，但它看起來基本上是正確的。此外，輸出打印在不尋常的位置，并帶有誤導性標簽，因此在繼續討論您的問題之前，讓我們干凈地重寫一下。
這是編寫中序二叉樹遍歷的簡單方法：
from collections import namedtuple
class Tree:
? ? def __init__(self, root):
? ? ? ? self.root = root
? ? def inorder(self):
? ? ? ? def traverse(node):
? ? ? ? ? ? if node:
? ? ? ? ? ? ? ? yield from traverse(node.left)
? ? ? ? ? ? ? ? yield node
? ? ? ? ? ? ? ? yield from traverse(node.right)
? ? ? ? return traverse(self.root)
if __name__ == "__main__":
? ? Node = namedtuple("Node", "data left right")
? ? """
? ? ? ? 9
? ? ? ?/ \
? ? ? 4? ?17
? ? ?/ \
? ? 3? ?6
? ? """
? ? tree = Tree(
? ? ? ? Node(
? ? ? ? ? ? 9,
? ? ? ? ? ? Node(
? ? ? ? ? ? ? ? 4,
? ? ? ? ? ? ? ? Node(3, None, None),??
? ? ? ? ? ? ? ? Node(6, None, None),?
? ? ? ? ? ? ),
? ? ? ? ? ? Node(17, None, None)
? ? ? ? )
? ? )
? ? for node in tree.inorder():
? ? ? ? print(node.data, end=" ") # => 3 4 6 9 17
我們唯一需要的分支是檢查根是否為 None——最好避免擔心子遞歸調用。如果它們為“無”，則該單個分支將在子堆棧幀中處理該情況。
上面的代碼返回一個生成器，它比創建列表更內存友好，并且語法更簡單。
我還會繼續在函數之外進行打印。傳遞回調是避免產生副作用的常見方法，但是使用上面的生成器方法可以通過循環完成相同的結果，讓我們將打印保留在調用者中。
如果您確實需要出于調試目的進行打印，我建議使用空格縮進，這使得輸出成為樹并且更容易理解：
from collections import namedtuple
class Tree:
? ? def __init__(self, root):
? ? ? ? self.root = root
? ? def inorder(self):
? ? ? ? def traverse(node, depth=0):
? ? ? ? ? ? if node:
? ? ? ? ? ? ? ? yield from traverse(node.left, depth + 1)
? ? ? ? ? ? ? ? yield node, depth
? ? ? ? ? ? ? ? yield from traverse(node.right, depth + 1)
? ? ? ? return traverse(self.root)
if __name__ == "__main__":
? ? Node = namedtuple("Node", "data left right")
? ? """
? ? ? ? 9
? ? ? ?/ \
? ? ? 4? ?17
? ? ?/ \
? ? 3? ?6
? ? """
? ? tree = Tree(
? ? ? ? Node(
? ? ? ? ? ? 9,
? ? ? ? ? ? Node(
? ? ? ? ? ? ? ? 4,
? ? ? ? ? ? ? ? Node(3, None, None),??
? ? ? ? ? ? ? ? Node(6, None, None),?
? ? ? ? ? ? ),
? ? ? ? ? ? Node(17, None, None)
? ? ? ? )
? ? )
? ? for node, depth in tree.inorder():
? ? ? ? print(" " * (depth * 2) + str(node.data))
這給出了樹的側視圖：
? ? 3
? 4
? ? 6
9
? 17
通過這種縮進技巧，可以更輕松地可視化樹，這是前/中/后順序打印的清理版本，它應該給出遍歷的清晰圖片：
from collections import namedtuple
class Tree:
? ? def __init__(self, root):
? ? ? ? self.root = root
? ? def print_traversals_pedagogical(self):
? ? ? ? preorder = []
? ? ? ? inorder = []
? ? ? ? postorder = []
? ? ? ? def traverse(node, depth=0):
? ? ? ? ? ? if node:
? ? ? ? ? ? ? ? preorder.append(node.data)
? ? ? ? ? ? ? ? print("? ? " * depth + f"entering {node.data}")
? ? ? ? ? ? ? ? traverse(node.left, depth + 1)
? ? ? ? ? ? ? ? inorder.append(node.data)
? ? ? ? ? ? ? ? print("? ? " * depth + f"visiting {node.data}")
? ? ? ? ? ? ? ? traverse(node.right, depth + 1)
? ? ? ? ? ? ? ? postorder.append(node.data)
? ? ? ? ? ? ? ? print("? ? " * depth + f"exiting {node.data}")
? ? ? ? traverse(self.root)
? ? ? ? print("\npreorder ", preorder)
? ? ? ? print("inorder? ", inorder)
? ? ? ? print("postorder", postorder)
if __name__ == "__main__":
? ? Node = namedtuple("Node", "data left right")
? ? """
? ? ? ? 9
? ? ? ?/ \
? ? ? 4? ?17
? ? ?/ \
? ? 3? ?6
? ? """
? ? tree = Tree(
? ? ? ? Node(
? ? ? ? ? ? 9,
? ? ? ? ? ? Node(
? ? ? ? ? ? ? ? 4,
? ? ? ? ? ? ? ? Node(3, None, None),??
? ? ? ? ? ? ? ? Node(6, None, None),?
? ? ? ? ? ? ),
? ? ? ? ? ? Node(17, None, None)
? ? ? ? )
? ? )
? ? tree.print_traversals_pedagogical()
輸出：
entering 9
? ? entering 4
? ? ? ? entering 3
? ? ? ? visiting 3
? ? ? ? exiting 3
? ? visiting 4
? ? ? ? entering 6
? ? ? ? visiting 6
? ? ? ? exiting 6
? ? exiting 4
visiting 9
? ? entering 17
? ? visiting 17
? ? exiting 17
exiting 9
preorder? [9, 4, 3, 6, 17]
inorder? ?[3, 4, 6, 9, 17]
postorder [3, 6, 4, 17, 9]
現在我們可以將上面的輸出與您的代碼連接起來并消除一些混亂。
首先，讓我們翻譯您的輸出標簽以匹配上面顯示的標簽：
restart做同樣的事情，b4 app所以你應該忽略它以避免混淆。這if node is not None: print("b4 app", node.data)始終是正確的——我們保證調用者node不會是 None。b4 app->?entering（或將新調用推入堆棧）。aft app->?visiting（按順序）。再次if node is not None:保證是真實的并且應該被刪除。父調用會檢查這一點，即使他們沒有這樣做，程序也會在上面使用 的行上崩潰node.data。inside right令人困惑——這是一個有序打印，但僅適用于具有右子節點的節點。我不確定這會增加什么價值，所以我會忽略它。
請注意，您沒有exiting（彈出調用堆棧幀/后序）打印語句。
結合這個背景，我們來回答一下你的問題：
這是代碼在結束之前最后一次調用自身（據我所知？）。
是的，這個節點即將退出。需要明確的是，該函數會調用自身，因為它是遞歸的，但樹中的每個節點只有一次調用。
if如果跳過該語句（上次io調用該函數時），遞歸將如何繼續？
調用堆棧彈出，并從父級中停止的地方繼續執行。這不是最后一次io被調用，因為父級可以（及其父級或其父級的子級）可以（并且確實）產生其他調用。
那么
io函數又是如何被調用的，為什么是node=4輸入呢？
它沒有被再次調用—— 的調用框架node=4被暫停，等待其子級解決，當控制權返回到它時，它從中斷處繼續。
讓我們將我的輸出與您的輸出聯系起來：
? ? visiting 3? # this is your `aft app 3 True [0]`
? ? exiting 3? ?# you don't have this print for leaving the node
visiting 4? ? ? # this is your `aft app 4 False #[2]`
您可以看到我們退出了 的調用框架node=3。此時，node=4已完成遍歷其所有左子孫（只有一個），然后按順序訪問其自己的值，然后繼續處理其右子孫。
嘗試在上面的代碼中使用不同的樹結構，并將打印的調試/教學遍歷與您的理解進行比較。
添加回答
舉報
0/150
提交
取消