Python inorder/pre/post/recursionを使用しないバイナリ検索ツリーの走査方法

Question

Pythonで

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

なしでそれを行う方法を思ったんだけど。 私はあなたが考えることができ、より説明はINORDER

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チュートリアル