python如何遍歷二叉搜索樹使用inorder/pre/post /沒有遞歸？

Question

在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 

我知道如何遞歸遍歷這個二叉樹，但我想知道如何做到這一點不遞歸

Answer 1

您可以使用堆棧的方法做樹遍歷沒有遞歸。 我給例如爲序

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教程