如何通過二叉搜索樹遍歷在Python（沒有遞歸）

到目前爲止，我有如何通過二叉搜索樹遍歷在Python（沒有遞歸）

def tree_iterate(): 
parent, current = None, self.root 
lst = [] 
while current is not None: 
if current.left not None: 
    lst.append(current.item) 
    parent, current = current, current.left 
if current.right not None: 
    lst.append(current.item) 
    parent, current = current, current.right

（抱歉間距我非常新的這個）

我不太清楚當電流左右移動時，如何在樹的兩邊迭代，而不使用遞歸。我的主要目標是獲得此BST中所有節點的列表enter code here

來源

2014-03-31 user3452238

你爲什麼想避免遞歸？這是做樹遍歷的最簡潔清晰的方法。獲得樹中所有節點的簡單迭代方法是使用寬度優先搜索（BFS）。你可以使用一個隊列（一個簡單的python列表）。 – spinlok

要迭代地獲取BST中所有節點的列表，請使用廣度優先搜索（BFS）。請注意，這不會給你的排序順序的節點：

level = [root] 
nextLevel = [] 
queue = [] 
while not level: 
    queue.extend(level) 
    for l in level: 
     nextLevel.append(l.left if l.left != None) 
     nextLevel.append(l.right if l.right != None) 
    level = nextLevel 
    nextLevel = []

如果你想在有序的節點，則需要使用堆棧序遍歷模擬：

result = [] 
stack = [root] 
while stack: 
    stack[-1].visited = True 
    if stack[-1].left != None and not stack[-1].left.visited: 
     stack.append(stack[-1].left) 
    else: 
     node = stack.pop() 
     result.append(node) 
     if stack[-1].right != None: 
      stack.append(stack[-1].right)

來源

2014-03-31 02:17:03 spinlok

如何通過二叉搜索樹遍歷在Python（沒有遞歸）

回答

相關問題