我試圖理解下面的代碼是如何工作的。代碼按其應(yīng)有的方式執(zhí)行，但我不理解其中的部分內(nèi)容。這是一種二叉搜索樹的中序遍歷方法：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以下是二叉搜索樹的類結(jié)構(gòu)：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"""在函數(shù)到達我指向的點（請參閱[0]）之后，node.right是，因此將跳過代碼中的None下一條語句（請參閱）。這是代碼在結(jié)束之前最后一次調(diào)用自身（據(jù)我所知？）。if[1]if如果跳過該語句（上次io調(diào)用該函數(shù)時），遞歸將如何繼續(xù)？另外，從輸出中的下一行可以看出（請參閱[2]），它繼續(xù)node=4, node.left=3, node.right=6，它是node=3的父級并提前傳遞到函數(shù)中（請參閱[3]）。那么io函數(shù)又是如何被調(diào)用的，為什么是node=4輸入呢？
1 回答
交互式愛情
TA貢獻1712條經(jīng)驗 獲得超3個贊
這段代碼是一種非常令人困惑的樹遍歷編寫方式，但它看起來基本上是正確的。此外，輸出打印在不尋常的位置，并帶有誤導(dǎo)性標(biāo)簽，因此在繼續(xù)討論您的問題之前，讓我們干凈地重寫一下。
這是編寫中序二叉樹遍歷的簡單方法：
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——最好避免擔(dān)心子遞歸調(diào)用。如果它們?yōu)椤盁o”，則該單個分支將在子堆棧幀中處理該情況。
上面的代碼返回一個生成器，它比創(chuàng)建列表更內(nèi)存友好，并且語法更簡單。
我還會繼續(xù)在函數(shù)之外進行打印。傳遞回調(diào)是避免產(chǎn)生副作用的常見方法，但是使用上面的生成器方法可以通過循環(huán)完成相同的結(jié)果，讓我們將打印保留在調(diào)用者中。
如果您確實需要出于調(diào)試目的進行打印，我建議使用空格縮進，這使得輸出成為樹并且更容易理解：
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))
這給出了樹的側(cè)視圖：
? ? 3
? 4
? ? 6
9
? 17
通過這種縮進技巧，可以更輕松地可視化樹，這是前/中/后順序打印的清理版本，它應(yīng)該給出遍歷的清晰圖片：
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]
現(xiàn)在我們可以將上面的輸出與您的代碼連接起來并消除一些混亂。
首先，讓我們翻譯您的輸出標(biāo)簽以匹配上面顯示的標(biāo)簽：
restart做同樣的事情，b4 app所以你應(yīng)該忽略它以避免混淆。這if node is not None: print("b4 app", node.data)始終是正確的——我們保證調(diào)用者node不會是 None。b4 app->?entering（或?qū)⑿抡{(diào)用推入堆棧）。aft app->?visiting（按順序）。再次if node is not None:保證是真實的并且應(yīng)該被刪除。父調(diào)用會檢查這一點，即使他們沒有這樣做，程序也會在上面使用 的行上崩潰node.data。inside right令人困惑——這是一個有序打印，但僅適用于具有右子節(jié)點的節(jié)點。我不確定這會增加什么價值，所以我會忽略它。
請注意，您沒有exiting（彈出調(diào)用堆棧幀/后序）打印語句。
結(jié)合這個背景，我們來回答一下你的問題：
這是代碼在結(jié)束之前最后一次調(diào)用自身（據(jù)我所知？）。
是的，這個節(jié)點即將退出。需要明確的是，該函數(shù)會調(diào)用自身，因為它是遞歸的，但樹中的每個節(jié)點只有一次調(diào)用。
if如果跳過該語句（上次io調(diào)用該函數(shù)時），遞歸將如何繼續(xù)？
調(diào)用堆棧彈出，并從父級中停止的地方繼續(xù)執(zhí)行。這不是最后一次io被調(diào)用，因為父級可以（及其父級或其父級的子級）可以（并且確實）產(chǎn)生其他調(diào)用。
那么
io函數(shù)又是如何被調(diào)用的，為什么是node=4輸入呢？
它沒有被再次調(diào)用—— 的調(diào)用框架node=4被暫停，等待其子級解決，當(dāng)控制權(quán)返回到它時，它從中斷處繼續(xù)。
讓我們將我的輸出與您的輸出聯(lián)系起來：
? ? 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]`
您可以看到我們退出了 的調(diào)用框架node=3。此時，node=4已完成遍歷其所有左子孫（只有一個），然后按順序訪問其自己的值，然后繼續(xù)處理其右子孫。
嘗試在上面的代碼中使用不同的樹結(jié)構(gòu)，并將打印的調(diào)試/教學(xué)遍歷與您的理解進行比較。
添加回答
舉報
0/150
提交
取消