在Python中不使用OOP可以生成二叉树吗?

2024-03-29 14:40:39 发布

您现在位置:Python中文网/ 问答频道 /正文

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

我已经搜索过了,但是我只找到了如何用非递归方法遍历二叉树。所以现在我怀疑在Python中没有objetcs是否可以实现二叉树。 每一个节点都有一个列表,每个节点都有一个列表。像这样:

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

现在我可以将其他节点附加到每个节点上

^{pr2}$

但是我必须猜测树有多少维,最后我会得到类似t[0][0][0][0][0][0][0][0][0][0][0]来从某个节点获取数据。我不知道怎么做,而且我对Python一无所知。我习惯用C语言,但我必须帮助别人完成他们的任务,而他们却不懂。他们只需要学习OOP,还是有其他方法在Python中实现二叉树?在


Tags: 方法orgtreehttp列表节点wwwoop
1条回答
网友
1楼 · 发布于 2024-03-29 14:40:39

下面是一个使用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))

典型输出

^{pr2}$

此代码将在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])

相关问题 更多 >