Skip to main content
 首页 » 编程设计

python 如何使用中序/前/后/无递归遍历二叉搜索树

2025年04月02日8telwanggs

在 python 3

class BinaryTree: 
""" 
=== Private Attributes === 
@type _root: object | None 
@type _left: BinaryTree | None 
@type _right: BinaryTree | None 
 
""" 
def __init__(self, root, left, right): 
 
    if root is None: 
        # store an empty BinaryTree 
        self._root = None 
        self._left = None 
        self._right = None 
    else: 
        self._root = root 
        self._left = left 
        self._right = right 
 
def is_empty(self): 
    return self._root is None 

我知道如何递归地遍历这棵二叉树,但我想知道如何不递归地做到这一点

请您参考如下方法:

不用递归就可以用栈的方式遍历树。 我举的例子是有序的

def inOrder(root): 
 
    # Set current to root of binary tree 
    current = root  
    s = [] # initialze stack 
    done = 0 
 
    while(not done): 
 
        # Reach the left most Node of the current Node 
        if current is not None: 
 
            # Place pointer to a tree node on the stack  
            # before traversing the node's left subtree 
            s.append(current) 
 
            current = current.left  
 
 
        # BackTrack from the empty subtree and visit the Node 
        # at the top of the stack; however, if the stack is  
        # empty you are done 
        else: 
            if(len(s) >0 ): 
                current = s.pop() 
                print current.data, 
 
                # We have visited the node and its left  
                # subtree. Now, it's right subtree's turn 
                current = current.right  
 
            else: 
                done = 1 

更多解释你可以考虑https://www.youtube.com/watch?v=xLQKdq0Ffjg&t=755s教程