Python: itérateur d'arbre binaire sans itérateur

Question

J'essaye de créer un module en python pour itérer sur un arbre binaire en utilisant les 4 traversées d'arbre standard (inorder, preorder, postorder et levelorder) sans utiliser de conditions et en utilisant seulement la méthode polymorphe expédition ou itérateurs. Les exemples suivants devraient fonctionner.

for e in t.preorder(): 
    print(e) 
for e in t.postorder(): 
    print(e) 
for e in t.inorder(): 
    print(e) 
for e in t.levelorder(): 
    print(e) 

Jusqu'à présent, je suis venu avec les éléments suivants

def build_tree(preord, inord): 
    tree = BinaryTree() 
    tree.root = buildTreeHelper(preord, inord) 
    return tree 

def buildTreeHelper(preorder, inorder): 
    if len(inorder) == 0: 
    return None 

    elem = preorder[0] 
    elemInorderIndex = inorder.find(elem) 

    if elemInorderIndex > -1: 
    leftPreorder = preorder[1:elemInorderIndex + 1] 
    rightPreorder = preorder[elemInorderIndex + 1:] 
    leftInorder = inorder[0:elemInorderIndex] 
    rightInorder = inorder[elemInorderIndex + 1:] 
    left = buildTreeHelper(leftPreorder, leftInorder) 
    right = buildTreeHelper(rightPreorder, rightInorder) 
    return BinaryTreeNode(elem, left, right) 
    else: 
    return "No valid tree for the given args" 

class BinaryTree: 
    def __init__(self): 
     self.root = None 
    def preorder(self): 
     return self.root.preorder() 
    def inorder(self): 
     return self.root.inorder() 
    def postoder(self): 
     return self.root.postorder() 

class BinaryTreeNode: 
    def __init__(self, element, left=None, right=None): 
     self.element = element 
     self.left = left 
     self.right = right 
    def preorder(self): 
     yield self.element 
     for e in self.left.preorder(): 
      yield e 
     for e in self.right.preorder(): 
      yield e 
    def inorder(self): 
     for e in self.left.inorder(): 
      yield e 
     yield self.element 
     for e in self.right.inorder(): 
      yield e 
    def postorder(self): 
     for e in self.left.postorder(): 
      yield e 
     for e in self.right.postorder(): 
      yield e 
     yield self.element 

if __name__ == "__main__": 
    t = build_tree("BAC", "ABC") 
    for e in t.inorder(): 
     print(e) 

Lorsque je tente d'exécuter l'un des itérateurs comme au bas du code, je reçois un AttributeError: objet « NoneType » n'a pas d'attribut 'inorder' message d'erreur. Je pense que c'est parce que je ne soulève jamais StopIteration. Des idées sur la façon de résoudre ce problème et de commencer à implémenter levelorder?

Answer 1

Vous avez dit que vous vouliez utiliser le polymorphisme, mais vous ne semblez pas l'avoir fait. Remplacez toutes les occurrences de 'None' dans votre code par un objet spécial qui prend en charge vos méthodes mais retourne une séquence vide et tout cela fonctionnera.

Vous devriez également prendre plus soin de l'indentation lors de l'envoi de questions Python. Le code que vous avez publié ne fonctionnera pas tel quel.

def build_tree(preord, inord): 
    tree = BinaryTree() 
    tree.root = buildTreeHelper(preord, inord) 
    return tree 

def buildTreeHelper(preorder, inorder): 
    if len(inorder) == 0: 
     return empty 

    elem = preorder[0] 
    elemInorderIndex = inorder.find(elem) 

    if elemInorderIndex > -1: 
     leftPreorder = preorder[1:elemInorderIndex + 1] 
     rightPreorder = preorder[elemInorderIndex + 1:] 
     leftInorder = inorder[0:elemInorderIndex] 
     rightInorder = inorder[elemInorderIndex + 1:] 
     left = buildTreeHelper(leftPreorder, leftInorder) 
     right = buildTreeHelper(rightPreorder, rightInorder) 
     return BinaryTreeNode(elem, left, right) 
    else: 
     return "No valid tree for the given args" 

class BinaryTree: 
    def __init__(self): 
     self.root = empty 
    def preorder(self): 
     return self.root.preorder() 
    def inorder(self): 
     return self.root.inorder() 
    def postorder(self): 
     return self.root.postorder() 

class EmptyNode: 
    def preorder(self): 
     return() 
    inorder = postorder = preorder 
empty = EmptyNode() 

class BinaryTreeNode: 
    def __init__(self, element, left=empty, right=empty): 
     self.element = element 
     self.left = left 
     self.right = right 
    def preorder(self): 
     yield self.element 
     for e in self.left.preorder(): 
      yield e 
     for e in self.right.preorder(): 
      yield e 
    def inorder(self): 
     for e in self.left.inorder(): 
      yield e 
     yield self.element 
     for e in self.right.inorder(): 
      yield e 
    def postorder(self): 
     for e in self.left.postorder(): 
      yield e 
     for e in self.right.postorder(): 
      yield e 
     yield self.element 

if __name__ == "__main__": 
    t = build_tree("BAC", "ABC") 
    for e in t.inorder(): 
     print(e)