从Python二叉树生成Python列表

Question

我想定义一个函数，该函数返回一棵树节点值的列表。这个列表是按照层次顺序排列的（从上到下，从左到右）。

例如，从上面展示的树中生成的列表将是：[2, 29, 4, 26, None, None, 2, None, None, None, None, None, None, 9, None, end]。

这是二叉树实现。

class BinaryTree:

    def __init__(self, data, left = None, right = None):
        self.key = data
        self.left = left
        self.right  = right

    def insert(self, data):
        node = self
        while node is not None:
            parent = node
            if node.left is None:
                parent.insert_left(data)
                break
            if node.right is None:
                parent.insert_right(data)
                break
            node = node.left

    def insert_left(self, data):
        self.left = BinaryTree(data, left=self.left)  

    def insert_right(self, data):
        self.right = BinaryTree(data, right=self.right)

    def get_left_subtree(self):
        return self.left

    def set_left(self, tree):
        self.left = tree

    def set_right(self, tree):
        self.right = tree

    def get_right_subtree(self):
        return self.right

    def set_value(self, val):
        self.key = val

    def get_value(self):
        return self.key

    def create_string(self, indent):
        string = str(self.key) + '---+'
        if self.left:
            string += '\n(l)' + indent + self.left.create_string(indent + '    ')
        if self.right:
            string += '\n(r)' + indent + self.right.create_string(indent + '    ')
        return string

    def __str__(self):
        return self.create_string('  ')

- ross.c

---

https://dev59.com/KG435IYBdhLWcg3wtSYV - pvg

那是Java的。 - ross.c

这里重要的是算法。你正在寻找广度优先遍历。你可能想检查一下这与你所拥有的有何不同。 - pvg

是的，我已经尝试过了，但似乎无法使其正常工作。 - ross.c

你有没有注意到你的实现是递归的，BFS 的实现通常不是这样的。 - pvg

Answer 1

对于层序遍历，迭代算法是最自然的。例如：

def create_list(tree, templist=[]):
    """
    >>> tree = BinaryTree(2, BinaryTree(29, BinaryTree(26)), BinaryTree(4, None, BinaryTree(2, BinaryTree(9))))
    >>> create_list(tree)
    [2, 29, 4, 26, None, None, 2, None, None, None, None, None, None, 9, None]

    """
    items = []
    queue = [tree]

    while queue:
        copy = queue[:]
        queue = []

        for item in copy:
            if item is None:
                items.append(None)
                queue.append(None)
                queue.append(None)
            else:
                items.append(item.key)
                queue.append(item.left)
                queue.append(item.right)

        if all((x is None for x in queue)):
            break

    return items

如果您真的非常想要递归实现：

def create_list_rec(tree, items=[], queue=[]):
    """
    >>> tree = BinaryTree(2, BinaryTree(29, BinaryTree(26)), BinaryTree(4, None, BinaryTree(2, BinaryTree(9))))
    >>> create_list_rec(tree)
    [2, 29, 4, 26, None, None, 2, None, None, None, None, None, None, 9, None]

    """
    if not items and not queue:
        return create_list_rec(None, [], [tree])

    copy = queue[:]
    queue = []

    for item in copy:
        if item is None:
            items.append(None)
            queue.append(None)
            queue.append(None)
        else:
            items.append(item.key)
            queue.append(item.left)
            queue.append(item.right)

    if all((x is None for x in queue)):
        return items

    return create_list_rec(items, queue)

- janos