Python：二叉樹遍歷迭代器不使用條件

Question

我想在python中創建一個模塊，使用4標準樹遍歷（inorder，preorder，postorder和levelorder）遍歷二叉樹而不使用條件並只使用多態方法分派或迭代器。下面的例子應該工作。

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) 

到目前爲止，我想出了以下

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) 

當我嘗試運行迭代的一個類似的代碼的底部，我得到一個 AttributeError的：「NoneType」對象沒有屬性'inorder' 錯誤消息。我認爲這是因爲我從來沒有提出StopIteration。關於如何解決這個問題並開始實施Levelorder的任何想法？

Answer 1

你說你想使用多態，但實際上你並沒有這樣做。將代碼中所有出現的「無」替換爲支持您的方法的特殊對象，但返回一個空序列，它將全部工作。

在發佈Python問題時，您還應該更加註意縮進。您發佈的代碼不會按原樣運行。

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)