是否可以在 Python 中制作没有 OOP 的二叉树？

Question

我所说的 OOP 基本上是使用 Class 节点和类似这样的东西 http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/

我已经搜索过了，但我只找到了如何使用非递归方法遍历二叉树。所以现在我怀疑在 Python 中是否可以在没有 objetcs 的情况下完成二叉树。我测试的一种方法是创建多个嵌套列表，其中每个项目都是一个节点，节点内的每个项目都是另一个列表（或节点）。像这样：

t = [[root], [left], [right]]

现在我可以将其他节点附加到这些节点中的每一个

t[0][0].append(t2)
t[0][1].append(t3)

但我不得不猜测这棵树有多少维度，我最终会得到类似 t[0][0][0][0][0][0][0][0 ][0] 从某个节点获取数据。我不知道该怎么做，而且我完全是 Python 的菜鸟。我习惯了 C，但我必须帮助别人进行评估，而他们不知道 OOP。他们是只需要学习 OOP 还是有另一种方法可以在 Python 中实现二叉树？

Answer 1

这是一个使用 dict 的简单二叉树。我只实现了一个 insert 和一个 traverse 函数，但这足以使用树进行排序。

from __future__ import print_function
from random import shuffle

D, L, R = 'data', 'left', 'right'

def insert(tree, data):
    if tree is None:
        tree = {D: data, L: None, R: None}
    elif data <= tree[D]:
        tree[L] = insert(tree[L], data)
    else:
        tree[R] = insert(tree[R], data)
    return tree

def traverse(tree):
    if tree is not None:
        for data in traverse(tree[L]):
            yield data
        yield tree[D]
        for data in traverse(tree[R]):
            yield data

a = list(range(32))
shuffle(a)
print(*a)

tree = None
for i in a:
    tree = insert(tree, i)

print(*traverse(tree))

典型输出

28 0 14 3 27 15 11 31 19 5 9 22 13 2 20 30 1 8 10 26 18 25 24 6 21 23 7 4 12 29 17 16
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

此代码将在 Python 2 或 3 上运行，但在 Python 3 的最新版本中，traverse 函数可以编写得更紧凑：

def traverse(tree):
    if tree is not None:
        yield from traverse(tree[L])
        yield tree[D]
        yield from traverse(tree[R])

是否可以在 Python 中制作没有 OOP 的二叉树？

Is it possible to make a binary tree without OOP in Python?

python

tree

binary-tree