在Python中从列表构造二叉树的最佳方法

Question

假设每个节点都有

self.left

、

self.right

和

self.data

，从每个级别给出数字的列表构造二叉树而不是二叉搜索树 (BST) 的最佳方法是什么。其中第一个数字是级别 1，接下来的 2 个数字是级别 2，接下来的 4 个数字是级别 3，依此类推。例如

input: [3,5,2,1,4,6,7,8,9,10,11,12,13,14] 

构建一棵树：

          3
       /     \
     5         2
    /\         /\
   1  4       6   7
  /\  /\     /\   /\
 8 9 10 11 12 13 14

一种解决方案是：

for node at index i,
left child index = 2i+1
right child index = 2i+2

想知道是否还有其他可能的方法

Answer 1

您可以直接使用这个工具：

drawtree

by

pip install drawtree

，如果您对它的实现感到好奇，可以参考这个源代码：https://github.com/msbanik/drawtree。

对于您在问题中的情况：

from drawtree import draw_level_order
draw_level_order('[3,5,2,1,4,6,7,8,9,10,11,12,13,14]')

您将得到如下所示的文本图：

               3
              / \
             /   \
            /     \
           /       \
          /         \
         /           \
        /             \
       /               \
      5                 2
     / \               / \
    /   \             /   \
   /     \           /     \
  1       4         6       7
 / \     / \       / \     /
8   9   /   \     /   \   14
       10   11   12   13

另外，你可以尝试Graphviz。

Answer 2

class TreeNode:
    def __init__(self, val: int, left=None, right=None) -> None:
        self.val = val
        self.left = left
        self.right = right

    def __repr__(self) -> str:
        return f"val: {self.val}, left: {self.left}, right: {self.right}"

    def __str__(self) -> str:
        return str(self.val)


def to_binary_tree(items: list[int]) -> TreeNode:
    """Create BT from list of values."""
    n = len(items)
    if n == 0:
        return None

    def inner(index: int = 0) -> TreeNode:
        """Closure function using recursion bo build tree"""
        if n <= index or items[index] is None:
            return None

        node = TreeNode(items[index])
        node.left = inner(2 * index + 1)
        node.right = inner(2 * index + 2)
        return node

    return inner()

用途：

root = to_binary_tree([1, 2, 3, None, None, 4, 5])

Answer 3

一种方法是构建当前叶子的

fringe

。

假设有

Node

类：

class Node(object):
    def __init__(self, data):
        self.data = data
        self.left = '*'
        self.right = '*'
    def __str__(self):
        return f'<{self.data}, {self.left}, {self.right}>'  # Py 3.6

然后你可以管理

fringe

并迭代

data

:

from collections import deque

data = [3,5,2,1,4,6,7,8,9,10,11,12,13,14]
n = iter(data)
tree = Node(next(n))
fringe = deque([tree])
while True:
    head = fringe.popleft()
    try:
        head.left = Node(next(n))
        fringe.append(head.left)
        head.right = Node(next(n))
        fringe.append(head.right)
    except StopIteration:
        break

print(tree)
# <3, <5, <1, <8, *, *>, <9, *, *>>, <4, <10, *, *>, <11, *, *>>>, <2, <6, <12, *, *>, <13, *, *>>, <7, <14, *, *>, *>>>

Answer 4

这是我想出的一个快速解决方案：

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

    def __str__(self):
        return f'<{self.data}, {self.left}, {self.right}>'


def build_binary_tree(values, index):
    if len(values) == 0:
        raise Exception('Node list is empty')

    if index > len(values) - 1:
        raise Exception('Index out of range')

    root = BT_Node(values[index])
    if 2*index+1 < len(values):
        root.left = build_binary_tree(values, 2*index+1)
    if 2*index+2 < len(values):
        root.right = build_binary_tree(values, 2*index+2)

    return root

Answer 5

这是实现解决方案的一种方法：创建一个树节点列表，每个树节点的索引位置对应于原始数据列表。然后，我们可以修复左右链接。

import logging

logging.basicConfig(level=logging.DEBUG)
logger = logging.getLogger(__name__)

class Tree(object):
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    def __repr__(self):
        left = None if self.left is None else self.left.data
        right = None if self.right is None else self.right.data
        return '(D:{}, L:{}, R:{})'.format(self.data, left, right)

def build_tree_breadth_first(sequence):
    # Create a list of trees
    forest = [Tree(x) for x in sequence]

    # Fix up the left- and right links
    count = len(forest)
    for index, tree in enumerate(forest):
        left_index = 2 * index + 1
        if left_index < count:
            tree.left = forest[left_index]

        right_index = 2 * index + 2
        if right_index < count:
            tree.right = forest[right_index]

    for index, tree in enumerate(forest):
        logger.debug('[{}]: {}'.format(index, tree))
    return forest[0]  # root

def main():
    data = [3, 5, 2, 1, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14]
    root = build_tree_breadth_first(data)
    print 'Root is:', root

if __name__ == '__main__':
    main()

输出：

DEBUG:__main__:[0]: (D:3, L:5, R:2)
DEBUG:__main__:[1]: (D:5, L:1, R:4)
DEBUG:__main__:[2]: (D:2, L:6, R:7)
DEBUG:__main__:[3]: (D:1, L:8, R:9)
DEBUG:__main__:[4]: (D:4, L:10, R:11)
DEBUG:__main__:[5]: (D:6, L:12, R:13)
DEBUG:__main__:[6]: (D:7, L:14, R:None)
DEBUG:__main__:[7]: (D:8, L:None, R:None)
DEBUG:__main__:[8]: (D:9, L:None, R:None)
DEBUG:__main__:[9]: (D:10, L:None, R:None)
DEBUG:__main__:[10]: (D:11, L:None, R:None)
DEBUG:__main__:[11]: (D:12, L:None, R:None)
DEBUG:__main__:[12]: (D:13, L:None, R:None)
DEBUG:__main__:[13]: (D:14, L:None, R:None)
Root is: (D:3, L:5, R:2)

Answer 6

我浏览了上面的一些答案，并修改了其中一些答案，并创建了一个适用于我正在处理的树的解决方案：

[5,4,8,11,None,13,4,7,2,None,None,None,1]

诀窍是，每当您在列表中遇到“无”时，请将“无”推到正确的索引。 要检查索引是否超出范围，请继续使用更新的列表进行检查，而不是之前的

n = len(items)

。

我认为它适用于大多数情况。

将我的代码粘贴到此处：

def to_binary_tree(items: list[int]) -> TreeNode: 
    if len(items) <= 0:
        return None

    def inner(index: int = 0) -> TreeNode:
        if len(items) <= index:
            return None

        elif items[index] is None:\
            # identify the index and add null to them in the list
            items.insert(2 * index + 1, None)
            items.insert(2 * index + 2, None)
            return None

        node = TreeNode(items[index])
        node.left = inner(2 * index + 1)
        node.right = inner(2 * index + 2)
        return node

    return inner()