树遍历python

Question

我必须定义三个函数：preorder(t):,postorder(t):和inorder(t):。

每个函数都会将二叉树作为输入并返回一个列表。这个列表应该以相同的方式排序，树元素将在相应的遍历中访问（后序，预订或者顺序）

我已经为它们中的每一个编写了代码，但是我保留得到一个错误，当我调用另一个函数（flat_list()），我得到

if not x or len(x) < 1 or n > len(x) or x[n] == None: 
    IndexError: list index out of range 

代码抛出的索引错误我遍历方法如下：

def postorder(t): 
    pass 
    if t != None: 
     postorder(t.get_left()) 
     postorder(t.get_right()) 
    print(t.get_data()) 

def pre_order(t): 
    if t != None: 
     print(t.get_data()) 
     pre_order(t.get_left()) 
     pre_order(t.get_right()) 

def in_order(t): 
    pass 
    if t != None: 
     in_order(t.get_left()) 
     print(t.get_data()) 
     in_order(t.get_right()) 

def flat_list2(x,n): 
    if not x or len(x) < 1 or n > len(x) or x[n] == None: 
    return None 

    bt = BinaryTree(x[n]) 
    bt.set_left(flat_list2(x, 2*n)) 
    bt.set_right(flat_list2(x, 2*n + 1)) 
return bt 

这是我如何调用flat_list2

flat_node_list = [None, 55, 24, 72, 8, 51, None, 78, None, None, 25] 
bst = create_tree_from_flat_list2(flat_node_list,1) 

    pre_order_nodes = pre_order(bst) 

    in_order_nodes = in_order(bst) 

    post_order_nodes = post_order(bst) 

    print(pre_order_nodes) 

    print(in_order_nodes) 

    print(post_order_nodes) 

Answer 1

首先，我注意到您的缩进在您提供的代码块中不一致（在修订中修复）。这是关键，您可以确保您的缩进在Python是一致的或东西会真的很快南下。另外，在下面的代码中，我假设你想让你的t.get_data()在你的postorder(t)中仍然落在if t != None之下，所以我缩进如下。最后，我注意到您的方法名称与您在问题中列出的规格不匹配，因此我更新了下面的方法名称以符合您的规范（命名中没有_）。

为了获得列表，你需要做的就是让你的遍历方法返回一个列表，然后在遍历的每个级别上使用其他遍历的值。这可以代替打印数据。

def postorder(t): 
    lst = [] 
    if t != None: 
     lst.extend(postorder(t.get_left())) 
     lst.extend(postorder(t.get_right())) 
     lst.append(t.get_data()) 
    return lst 

def preorder(t): 
    lst = [] 
    if t != None: 
     lst.append(t.get_data()) 
     lst.extend(preorder(t.get_left())) 
     lst.extend(preorder(t.get_right())) 
    return lst 

def inorder(t): 
    lst = [] 
    if t != None: 
     lst.extend(inorder(t.get_left())) 
     lst.append(t.get_data()) 
     lst.extend(inorder(t.get_right())) 
    return lst 

这将运行至满深处左，右各节点上，这取决于它是否preorder，postorder，或inorder，将追加所有，他们经过的顺序遍历元素。一旦发生这种情况，它会将正确排序的列表返回到下一级，并将其添加到列表中。这将缓解，直到你回到根级。

现在，IndexError从flat_list到来，可能是被试图访问x[n]时n可以等于len(x)造成的。请记住Python中的列表/数组索引为0，这意味着列表的最后一个元素将是x[n-1]，而不是x[n]。

因此，要解决该问题，请将x[n]替换为x[n-1]。像这样：

def flat_list2(x,n): 
    if not x or len(x) < 1 or n < 1 or n > len(x) or x[n-1] == None: 
     return None 

    bt = BinaryTree(x[n-1]) 
    bt.set_left(flat_list2(x, 2*n)) 
    bt.set_right(flat_list2(x, 2*n + 1)) 
    return bt 

Answer 2

你实际上应该写三个返回迭代器的函数。让调用者决定是否需要列表。这很容易用发电机功能完成。在3.4+中，可以使用'yield from'来代替for循环。

def in_order(t): 
    if t != None: 
     yield from in_order(t.get_left()) 
     yield t.get_data() 
     yield from in_order(t.get_right()) 

移动yield语句对于其他两个版本。