Luna Tech | 树结构的两种实现方式（python）

March 7, 2021 字数 863 2 min

0. 相关文章

前言

树结构是一个非常重要的 nonlinear data structure（非线性数据结构），它可以用来实现：

Associative Array (也就是 Map) ADT
min/max heap（最大/最小堆）
priority queue（优先队列）

那么如何实现树结构呢？

用 list of list
用 classes and references

这篇文章我们就来看看如何用以上两种方法实现树结构。

Reference

Quiz: 树结构到底是一个 ADT 还是一个 Data Structure 呢？ Answer: Nonlinear data structure

1. 用 list of lists 来实现树结构

把 root node 的值存为 list 的第一个值，list[0] = root-value
list 的第二个值就是一个单独的 list，代表左边的那颗 subtree，list[1] = left-sublist
list 的第三个值也是一个单独的 list，代表右边的那颗 subtree, list[2] = right-sublist
以此类推，每个 subtree 都和 parent 一样的结构
叶子节点：有 parent node 和两个空 list

虽然这种树是 binary tree，但是可以非常容易地通过再增加一个 sublist 来进行扩展（成为三叉树，四叉树…）。

 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54


# 1. Use list of lists to implement Tree
def make_binary_tree(root):
    return [root, [], []]

# 插入左节点
def insert_left(root, new_child):
    old_child = root.pop(1)
    # 假如左边本来就有 subtree，我就替换掉它的位置，让它成为我的左 subtree
    if len(old_child) > 1: 
        root.insert(1, [new_child, old_child, []])
    # 假如左边的长度 = 1（也就是空的），那我就直接用一个长度 = 3 的 sublist 代替它
    else:
        root.insert(1, [new_child, [], []])
    return root

# 插入右节点
def insert_right(root, new_child):
    old_child = root.pop(2)
    if len(old_child) > 1:
        root.insert(2, [new_child, [], old_child])
    else:
        root.insert(2, [new_child, [], []])
    return root


def get_root_val(root):
    return root[0]


def set_root_val(root, new_value):
    root[0] = new_value


def get_left_child(root):
    return root[1]


def get_right_child(root):
    return root[2]


a_tree = make_binary_tree(3)
insert_left(a_tree, 4)
insert_left(a_tree, 5)
insert_right(a_tree, 6)
insert_right(a_tree, 7)
left_child = get_left_child(a_tree)
print(left_child)

set_root_val(left_child, 9)
print(a_tree)
insert_left(left_child, 11)
print(a_tree)
print(get_right_child(get_right_child(a_tree)))

2. 用 Class and References 来实现树结构

定义一个 class (BinaryTree)，它有 root value, left subtree, right subtree 这三个 attribute
每个 node 都是一个 BinaryTree object

 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


class BinaryTree:
    def __init__(self, root_obj):
        self.key = root_obj
        self.left_child = None
        self.right_child = None

    def insert_left(self, new_node):
        if self.left_child is None:
            self.left_child = BinaryTree(new_node)
        else:
            new_child = BinaryTree(new_node)
            new_child.left_child = self.left_child
            self.left_child = new_child

    def insert_right(self, new_node):
        if self.right_child == None:
            self.right_child = BinaryTree(new_node)
        else:
            new_child = BinaryTree(new_node)
            new_child.right_child = self.right_child
            self.right_child = new_child

    def get_root_val(self):
        return self.key

    def set_root_val(self, new_obj):
        self.key = new_obj

    def get_left_child(self):
        return self.left_child

    def get_right_child(self):
        return self.right_child


a_tree = BinaryTree("a")
print(a_tree.get_root_val())
print(a_tree.get_left_child())
a_tree.insert_left("b")
print(a_tree.get_left_child())
print(a_tree.get_left_child().get_root_val())
a_tree.insert_right("c")
print(a_tree.get_right_child())
print(a_tree.get_right_child().get_root_val())
a_tree.get_right_child().set_root_val("hello")
print(a_tree.get_right_child().get_root_val())