python - 将搜索树（非二进制）的条目写入列表。（迭代）

Question

我正在尝试将搜索树的所有条目写入列表。以不变的顺序，子节点之前的节点。但我在途中的某个地方把订单混在一起了。

def n(value, children=[]):
    return [value,children]

#I want to keep this order in the list
tree = (n(5,[n(2,[n(3)]),n(6),n(8,[n(7),n(9)])]))

def is_empty(tree) :
    return tree == []

def to_list_iter(tree) :

    stack = []
    stack.append(tree)
    l = []
    while stack != [] :
        tree = stack.pop()
        if not is_empty(tree) :
            l.append(tree[0])
            n = len(tree[1])
            while n > 0:
                stack.append(tree[1][len(tree[1])-n])
                n -= 1

    return l

print (to_list_iter(tree))
# This will print the following output:
# [5, 8, 9, 7, 6, 2, 3]
# Instead of the desired [5, 2, 3, 6, 8, 7, 9]

Answer 1

该解决方案与您的代码非常接近，但经过了简化：

def n(value, children=[]):
    return [value,children]

tree = (n(5,[n(2,[n(3)]),n(6),n(8,[n(7),n(9)])]))

def to_list_iter(tree) :

    stack = [tree]
    l = []
    while stack :
        tree = stack.pop()
        if tree:
            l.append(tree[0])
            stack.extend(reversed(tree[1]))

    return l

print (to_list_iter(tree))

主要区别在于您需要使用反向子列表来扩展堆栈，因为堆栈总是从列表的后面弹出。