为空二叉树输入值

Question

我正在数组实现中创建一个特定高度的空完全二叉树，其中所有节点当前都将 None 作为其值。

如何输入值列表，以便在后序遍历中打印时，值列表会反转？

示例：

create_empty_bt(height=3) # total nodes = 2^h - 1
values = [7, 6, 5, 4, 3, 2, 1]
index = 0

enter_values(index, values, root)
print_tree_postorder(root, lst)
[1, 2, 3, 4, 5, 6, 7] # output

到目前为止，我的代码将打印：[None、None、None、None、5、6、7]

class Node:
    def __init__(self, v):
        self.value = v
        self.left = None
        self.right = None


def create_empty_bt(height): # create complete binary tree
    nodes = [i for i in range(2 ** height - 1, 0, -1)]
    for i in range(height):
        start = (2 ** i) - 1
        end = (2 ** (i + 1)) - 1
        for j in range(start, end):
            nodes[j] = Node(None)
            if j == 0:
                continue
            if (j % 2) == 0:
                parent = (j - 2) // 2 # right child node
                nodes[parent].right = nodes[j]
            else:
                parent = (j - 1) // 2 # left child node
                nodes[parent].left = nodes[j]
    return nodes[0]

# Postorder = L R V, Reverse = V R L
def enter_values(index, values, root):
    if root:
        if root.value is None:
            root.value = values[index]
            enter_values(index + 1, values, root.right)
        else:
            enter_values(index + 1, values, root.left)

def print_tree(node, lst): # postorder
    if node:
        print_tree(node.left, lst)
        print_tree(node.right, lst)
        lst.append(node.value)

提前致谢！

Answer 1

你做得比你需要的要难一些。考虑一棵高度 h 的平衡树是有两个 children 高度 h - 1 的树。考虑到这一点，您可以简单地创建一个值为 None 的树：

class Node:
    def __init__(self, v):
        self.value = v
        self.left = None
        self.right = None

def create_empty_bt(height):
    if height == 0:
        return None
    n = Node(None)
    n.left = create_empty_bt(height - 1) 
    n.right = create_empty_bt(height -1)
    return n

要执行 post-order 遍历，您只需按正确顺序调用 children 上的函数：

def po_traverse(node):
    if node is None:
        return
    yield from po_traverse(node.left) 
    yield from po_traverse(node.right) 
    yield node.value

这个returns一个生成器，要得到一个列表只需要问：

list(po_traverse(node))

要插入，您使用相同的技术并将节点的值设置为递归展开时列表的最后一个元素：

def insertList(node, l):
    if node is None: 
        return 
    insertList(node.left, l)
    insertList(node.right, l)
    node.value = l.pop()

注意：这会消耗列表。您可以通过复制它或重写函数来避免这种情况，使其 returns 展开时列表的一部分 — 但我认为这更清楚地显示了结构。

使用这个给你：

> t = create_empty_bt(height=3) # total nodes = 2^h - 1
> list(po_traverse(t))
[None, None, None, None, None, None, None]

> insertList(t, [7, 6, 5, 4, 3, 2, 1])
> list(po_traverse(t))
[1, 2, 3, 4, 5, 6, 7]

为空二叉树输入值

Entering in Values for an Empty Binary Tree

python

binary-tree

data-structures

python-3.x