İkili ağaç geçişi işlevi Adımları yanıtlıyor, bu yüzden bir kereden fazla çalıştırılamıyor mu?

Question

İkili bir ağaç sıralı çapraz işlev uyguladım. Esasen 3 özyinelemeli adım vardır: sol çocuğa git, kargo verisini al, doğru çocuğa git. Bu nedenle, belirli bir düğümdeki adımlar travers sırasında çekilip çekilmediğini kaydetmek için artımlı bayraklar (Düğüm sınıfına ait bir özellik) tasarladım. Bir kez çalıştırırsam bayraklar iyi çalışır. 2. kez çalıştırdığınızda, bayraklar amaca karşı çalışır.

Çözüm: Bayrakları sıfırlamak için düğüm nesnelerini oluşturmak için kullandığım ile benzer bir işlevi olabilir. Ama çok gereksiz ve kendimi tekrar ediyor gibi görünüyor. Çizgileri çaprazlama amacı için sıfırlamak veya adımları kullanmamak için farklı bir çözüm bulmak için bana daha iyi bir çözüm sağlayabilir misiniz?

Teşekkür ederiz! Aşağıda Python uygulamasıdır:

"""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

Sana gerekli olandan çok daha karmaşık şeyler yaptığını düşünüyorum. Eğer Özyinelemeyi kullanmak istemiyorsanız

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) 

, bir kullanarak iteratif sürüm içine aynı algoritmayı kapatabilirsiniz: düğümleri yapıyoruz hangi Ne izlemek için özyinelemeli fonksiyon icra çerçevesini kullanabilirsiniz yığını. böylece,

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 

Bu uygulamaların hiçbiri değiştirerek gerektiren düğümleri: Burada ziyaret etmiş çocukları kalan üst düğümlerine takip etmek için bir yığın olarak bir list kullanan bir versiyonu, ama kim henüz kendilerini işlenecek olan onları istediğiniz kadar çalıştırabilir ve çalışacaklardır.

Örnek kodumda, düğümlerinizin get_X veya set_Y yöntemlerini kullanmıyorum. Access metotları genellikle Python'da gerekmemektedir ve kamu özellikleri çok daha iyidir. Diğer dillerdeki (C++ ve Java gibi) ana nedenler ve ayarlayıcılar, sınıfın genel API'sini bozmadan, özniteliğin içsel uygulamasının doğrulama ekleme veya değiştirme işlemine olanak tanımaktır. Python'da, doğrulama eklemek veya genel bir özelliğin uygulanmasını değiştirmek istiyorsanız, öznitelik aramasını bir yöntem çağrısına dönüştürmek için property kullanabilirsiniz.