バイナリツリートラバース関数はステップで応答しますので、複数回実行することはできません。

Question

私はバイナリツリーインオーダートラバース機能を実装しました。本質的に3つの再帰的なステップがあります：左の子に行く、貨物のデータを取得する、右の子に行く。そこで、トラバース中に特定のノード上のステップが実行されたかどうかを記録するインクリメンタルフラグ（Nodeクラスに属するプロパティ）を設計しました。私はそれを一度実行するとフラグがうまく動作します。 2回目に実行すると、フラグは目的に反して動作します。

解決方法：ノードオブジェクトを生成してフラグをリセットするのと同じ機能を持つことができます。しかし、それは非常に冗長で、私の自己を繰り返すようです。トラバース目的のフラグや、ステップをまったく使用しない別の解決方法のフラグをリセットするための優れたソリューションを提供できますか？

ありがとうございました！ 以下はPythonで実装したものです：

"""implementation of Binary Tree""" 


class BinaryTreeNode(object): 

    def __init__(self, data, left=None, right=None, parent=None): 
     self.data = data 
     self.left = left 
     self.right = right 
     self.parent = parent 
     self.traversal_step = int(0) 

    def __str__(self): 
     return str(self.data) 

    def get_data(self): 
     return self.data 

    def get_left(self): 
     return self.left 

    def get_right(self): 
     return self.right 

    def get_parent(self): 
     return self.parent 

    def set_left(self, left): 
     self.left = left 

    def set_right(self, right): 
     self.right = right 

    def set_parent(self, parent): 
     self.parent = parent 

    def set_traversal_step(self, reset=False): 
     if reset == False: 
      self.traversal_step += 1 

     else: 
      self.traversal_step = 0 

    def get_traversal_step(self): 
     return self.traversal_step 


class BinaryTree(object): 
    """implement a binary tree 
    Protocol: 
    any data has value less than value of its parent node 
    will be placed on the left child node. While the ones 
    greater, will be placed to the right child node 
    """ 
    def __init__(self): 
     self.root = None 
     self.tree_depth = int(0) 
     self.node_sum = int(0) 

    def insert(self, data): 
     new_node = BinaryTreeNode(data) 
     current_node = self.root 
     # print('begin inserting : ' + str(data)) 
     if self.root: 
      # Determine left/right side should be chosen for the new node 
      fulfill_status = False 
      while not fulfill_status: 
       if data >= current_node.get_data(): 

        if current_node.get_right(): 
          # print('move to RIGHT, and dive to next level') 
         current_node = current_node.get_right() 
        else: 
         current_node.right = new_node 
         new_node.set_parent(current_node) 
         fulfill_status = True 
       else: 
        if current_node.get_left(): 
          # print('move to LEFT, and dive to next level') 
         current_node = current_node.get_left() 
        else: # empty node slot found 
         current_node.left = new_node 
         new_node.set_parent(current_node) 
         fulfill_status = True 
       # 3. verify status on the current node 
        # print('Current parent node = ' + str(current_node.get_data())) 
        # print('Child status: ' 
        #  + 'left=' + str(current_node.get_left()) 
        #  + ' right=' + str(current_node.get_right())) 
        # print('new child\'s parent node is:' + str(new_node.get_parent())) 

     else: 
      # print('Building a new tree now, root = ' + str(data)) 
      self.root = new_node 

     # print('Finishing inserting...' + '#' * 30) 

    def query(self, data): 
     """check if the data presents in the Tree already""" 
     current_node = self.root 
     print('begin querying data : {} '.format(data) + '#' * 50) 
     if self.root: 
      # Determine left/right side should be chosen for the new node 
      found_status = False 
      while not found_status: 
       if data == current_node.get_data(): 
        found_status = True 
        break 
       elif data > current_node.get_data(): 
        if current_node.get_right(): 
         # print('move to RIGHT, and dive to next level') 
         current_node = current_node.get_right() 
        else: 
         break # no existing node larger than the current node. 
       else: 
        if current_node.get_left(): 
         # print('move to LEFT, and dive to next level') 
         current_node = current_node.get_left() 
        else: 
         break 

      if found_status: 
       print("The data entry: {} found ".format(str(data)) + '#' * 30) 
       # print('my parent node is '+ str(current_node.get_parent())) 
      else: 
       print("Attention! The data entry: {} is not found ".format(str(data)) + '#' * 30 + '\n') 
      return found_status 
     else: 
      print("Attention! The data entry: {} is not found because the tree doesn't exist ".format(str(data)) 
        + '#' * 30 + '\n') 
      return False 

    def delete(self, data): 
     """there are 3 possible scenarios: 
     1. the node has no child 
      delete the node and mark its parent node that 'node.next = None' 
     2. the node has 1 child. 
      delete the node and re-connect its parent node with its child node 
     3. the node has 2 children 
      find the Smallest key in the node's Right sub-tree 
      replace the node with the Smallest key 
     """ 
     current_node = self.root 
     print('begin deleting data : {} '.format(data) + '#' * 50) 
     if self.root: 
      # Determine left/right side should be chosen for the new node 
      found_status = False 
      while not found_status: 
       if data == current_node.get_data(): 
        parent_node_data = current_node.get_parent().get_data() 
        print('Parent Node is ' + str(parent_node_data)) 
        current_node = current_node.get_parent() 
        if data >= parent_node_data: 
         current_node.set_right(None) 
         print ('removing RIGHT') 
        else: 
         current_node.set_left(None) 
         print('removing LEFT') 
        found_status = True 
        break 
       elif data > current_node.get_data(): 
        if current_node.get_right(): 
         # print('move to RIGHT, and dive to next level') 
         current_node = current_node.get_right() 
        else: 
         break # no existing node larger than the current node. 
       else: 
        if current_node.get_left(): 
         # print('move to LEFT, and dive to next level') 
         current_node = current_node.get_left() 
        else: 
         break 

      if found_status: 
       print("The data entry: {} found and deleted ".format(str(data)) + '#' * 30) 
       # print('my parent node is ' + str(current_node.get_parent())) 
      else: 
       print("Attention! The data entry: {} is not found ".format(str(data)) + '#' * 30 + '\n') 
      return found_status 
     else: 
      print("Attention! The data entry: {} is not found because the tree doesn't exist ".format(str(data)) 
        + '#' * 30 + '\n') 
      return False 

    def traverse_inOrder(self): 
     """Steps: 
     1 Go Left 
     2 Process current node 
     3 Go right 
     """ 
     print('traversing tree(in-order)') 
     tree_node = self.root 
     result = [] 
     while not (tree_node == self.root and self.root.get_traversal_step() > 1) : 
      if tree_node.get_traversal_step() < 3: 
       print('\ncurrent node is {}'.format(tree_node.get_data())) 
       print('steps: ' + str(tree_node.get_traversal_step())) 
       print('Left child is: ' + str(tree_node.get_left())) # for debugging 
       # step1 
       if tree_node.get_left(): 
        tree_node.set_traversal_step() 
        while tree_node.get_left() and tree_node.get_left().get_traversal_step() < 3: 
         print('traversing to LEFT child') 
         tree_node = tree_node.get_left() 
         tree_node.set_traversal_step() 
       else: 
         print('attempted to go LEFT but failed') 
         tree_node.set_traversal_step() 

       # step2 
       print('getting node data:' + str(tree_node.get_data())) 
       result.append(tree_node.get_data()) 
       tree_node.set_traversal_step() 

       #step3 
       if tree_node.get_right(): 
        print('traversing to RIGHT child') 
        tree_node.set_traversal_step() 
        tree_node = tree_node.get_right() 
       else: 
        print('attempted to go RIGHT but failed') 
        tree_node.set_traversal_step() 
      # step4 fall back to parent node 
      else: 
       if tree_node != self.root: 
        print('reversing to parent node {}'.format(tree_node.get_parent().get_data())) 
        tree_node = tree_node.get_parent() 
     # step-final: reset all the step markers for the next traverse run. 
     print(result) 
     return result 


    def traverse_preorder(self): 
     level_result = [] 
     result = {} 
     node = self.root 
     if node: 
      pass 
     else: 
      print('tree does not exist') 
     return result 

if __name__ == '__main__': 
    INPUT_LIST = [50, 76, 21, 4, 32, 64, 15, 52, 14, 100, 83, 80, 2, 3, 70, 87] 
    b = BinaryTree() 
    for i in INPUT_LIST: 
     b.insert(i) 
    # print('Query match result : ' + str(b.query(87))) 
    b.traverse_inOrder() 
    b.query(3) 
    b.delete(3) 
    b.query(3) 
    b.query(80) 
    b.traverse_inOrder() 
    b.traverse_inOrder() 

Answer 1

私はあなたが必要以上にはるかに複雑なものを作っていると思いますが。あなたは再帰を使用しない場合は、あなたが使用することにより、反復バージョンに同じアルゴリズムを変えることができます

def in_order_traversal(node): 
    if node is None: 
     return 
    in_order_traversal(node.left) 
    # do whatever you want to do on the current node here e.g.: 
    print(node.data) 
    in_order_traversal(node.right) 

：あなたは、ノードが何をしているのを追跡するために再帰関数の実行フレームを使用することができますスタック。ここでは、訪問している子供たちを残しています親ノードを追跡するためにスタックとしてlistを使用したバージョンだが、自分自身を処理するまだ持っている人：

def in_order_traversal_iterative(node): 
    stack = [] 
    while node is not None or stack: 
     while node is not None: 
      stack.append(node) 
      node = node.left 
     node = stack.pop() 
     print(node.data) # process node 
     node = node.right 

これらの実装のどちらもがそう、ノードを変更する必要あなたはあなたが望むように何度もそれらを実行することができ、彼らは働くでしょう。

私のコード例では、ノードのget_Xまたはset_Yメソッドを使用していないことに注意してください。アクセサーメソッドは通常Pythonでは必要ではなく、パブリック属性ははるかに良いです。 getterとsetterが他の言語（C++やJavaなど）で使用されている主な理由は、クラスのパブリックAPIを破棄することなく、検証の追加や属性の内部実装の変更を可能にするためです。 Pythonでは、検証を追加したり、パブリック属性の実装を変更したりする場合は、propertyを使用して、属性ルックアップをメソッド呼び出しに変えることができます。