在计算机内存中存储二叉树

Question

下面的table表示计算机内存中存储的一棵树。树的每个节点包含三个单元格。第一个单元格包含要存储的数据；第二个单元格包含指向第一个单元格左子节点的指针，第三个单元格包含指向第一个单元格右子节点的指针。作为指针的值 00 表示 nil 指针。一个单独的变量指向树的根。树的根是从 4F 开始的单元格；也就是说，保存根指针的变量的值为 4F。填写生成的树。绘制生成的树的图片。（使用打字机图形绘制二叉树的一种方法是使用 / 表示左指针，使用 \ 表示右指针。您可以在下一个问题中看到这方面的示例。）

Address    Contents

40        A1
41        00
42        00
43        B2
44        00
45        00
46        D4
47        49
48        00
49        C3
4A        00
4B        00
4C       E5
4D       43
4E        40
4F        F6
50        46
51        4C

我知道如何解决这个问题。但是有没有人有解决这个问题的想法

Answer 1

第一个节点在地址4F，所以根节点是[value=F6, leftChildAddr=46, rightChildAddr=4C]。然后读取从地址46开始的3个字节长的左子节点。然后读取右子节点的3个字节。就这样往下走，直到没有指针可以跟随（结束节点可以有值，但是结束节点的第二个和第三个字节为空）。

Answer 2

解决方法如下：

它是从这个 Python 代码生成的，使用 python tree.py | dot -T png a.png

data = """
40        A1
41        00
42        00
43        B2
44        00
45        00
46        D4
47        49
48        00
49        C3
4A        00
4B        00
4C       E5
4D       43
4E        40
4F        F6
50        46
51        4C""".split("\n")

data = [line.split() for line in filter(None, data)]
data = dict(map((lambda x: int(x, 16)), line) for line in data)

def print_tree(data, p):
    print '  n%x [label="%d"];' % (p, data[p])
    for c in data[p+1], data[p+2]:
        if not c: continue
        print_tree(data, c)
        print '  n%x -> n%x;' % (p, c)

print 'digraph tree {'
print_tree(data, 0x4f)
print '}'

在计算机内存中存储二叉树

Storing a Binary Tree in computer memory

algorithm

binary-tree