二叉搜索树BST节点DFS深度优先搜索遍历，基于栈，非递归，binarytree，python

秒速五厘米 2023-10-02 15:13 16阅读 0赞

binarytree二叉树节点DFS深度优先搜索遍历，基于栈，非递归，python

注意对已经访问过的节点的处理，在while循环中，如果在栈回退时候，遇到之前访问过的节点，则直接弹出。弹出的情况还有一种就是该节点没有左右子节点了，表明到了尽头。

from binarytree import bst
    
    
    def app():
        t = bst(height=3, is_perfect=True)
        print(t)
    
        print('-----')
        dfs(t)
    
    
    def dfs(node):
        if node.left is None and node.right is None:
            return node
    
        stack = [node]
        visited = []
    
        while True:
            if len(stack) == 0:
                break
    
            visit_node = stack.pop()
            visited.append(visit_node)
    
            right_child = visit_node.right
            left_child = visit_node.left
    
            if right_child is not None:
                stack.append(right_child)
            if left_child is not None:
                stack.append(left_child)
    
        print('dfs', visited)
    
    
    if __name__ == '__main__':
        app()

输出：

______7_______
           /              \
        __3__           ___11___
       /     \         /        \
      1       5       9         _13
     / \     / \     / \       /   \
    0   2   4   6   8   10    12    14
    
    -----
    dfs [Node(7), Node(3), Node(1), Node(0), Node(2), Node(5), Node(4), Node(6), Node(11), Node(9), Node(8), Node(10), Node(13), Node(12), Node(14)]