python Как обходить двоичное дерево поиска, используя inorder/pre/post/without recursion?

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 учебник