python-3.x - 如何使用python将二叉树表示为数组?
问题描述
我想使用 Python 将二叉树转换为数组,但我不知道如何为树节点提供索引?
我已经使用公式 left_son=(2*p)+1; 和 right_son=(2*p)+2; 在java中但我被困在python中。是否有任何函数可以为 python 中的树节点提供索引?
解决方案
您可以以完全相同的方式将 Python 中的二叉树表示为一维列表。
例如,如果您将 at 树表示为:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15]
0
是根
1
&是&的
子2
级的下一级1
2
[3, 4]
[5, 6]
这对应于您的公式。对于索引处的给定节点,i
该节点的子节点是(2*i)+1
(2*i)+2
。这是对堆建模的常用方法。您可以在其 [heapq 库] 中阅读有关 Python 如何使用它的更多信息。(https://docs.python.org/3.0/library/heapq.html)
您可以使用它来深入遍历树,例如:
a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15]
def childNodes(i):
return (2*i)+1, (2*i)+2
def traversed(a, i=0, d = 0):
if i >= len(a):
return
l, r = childNodes(i)
traversed(a, r, d = d+1)
print(" "*d + str(a[i]))
traversed(a, l, d = d+1)
traversed(a)
这打印
15
6
14
2
13
5
11
0
10
4
9
1
8
3
7
推荐阅读
- javascript - 如何获取具有特定样式属性值的循环中元素的长度
- java - Strange print behavior using Unicode symbols in Eclipse (Java)
- bash - Replacing in place only on specific column using bash
- python - TypeError: cannot unpack non-iterable object
- c - 如何引用结构数组的所有字段
- c++ - 创建一个可以在一个成员变量中存储 int、std::string 或 double 的类
- python - 如果将 Windows 用户目录移动到 Python 中的不同驱动器,如何返回该目录?
- css - bootstrap 4中不同col大小的备用背景颜色
- python - 循环测试功能时如何让Pytest识别迭代次数
- android - 带有自定义视图的 AlertDialog(带有 ConstraintLayout)占用所有屏幕空间(ConstraintLayout 的 wrap_content 不起作用)