python-3.x - 来自 python 二叉树的 python 列表

Question

我想定义一个返回树节点值列表的函数。该列表按级别顺序排列(从上到下，从左到右)。

例如，从上面显示的树生成的列表将是:[2, 29, 4, 26, None, None, 2, None, None, None, None, None, None, 9, None , 结束].

这是二叉树的实现

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('  ')

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)