-1

我必须定义三个函数：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)
4

2 回答 2

1

您实际上应该编写三个返回迭代器的函数。让调用者决定是否需要列表。使用生成器功能最容易做到这一点。在 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 语句。

于 2016-02-11T23:51:48.983 回答
0

首先，我注意到您提供的代码块中的缩进不一致（在修订中已修复）。确保缩进是一致的，否则东西会很快变南，这一点至关重要。Python另外，在下面的代码中，我假设您希望您t.get_data()仍然属于if t != None您的postorder(t)，所以我在下面缩进了。最后，我注意到您的方法名称与您在问题中列出的规范不匹配，因此我更新了下面的方法名称以符合您的规范（_命名中没有）。

要获取列表，您需要做的就是让您的遍历方法返回一个列表，然后extend您的列表在每个遍历级别上都带有其他遍历的值。这是代替打印数据而完成的。

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]whenn可能等于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
于 2016-02-11T22:11:04.150 回答