Luna Tech | 树结构的两种实现方式(python)

March 7, 2021 字数 863 2 min


0. 相关文章

  1. Luna Tech | 聊聊数据类型(Data Type)
  2. Luna Tech | 聊聊数据结构(Data Structure)
  3. Luna Tech | 聊聊关联数组(Associative Array)
  4. Luna Tech | 聊聊树结构(Tree)
  5. Luna Tech | 聊聊自我平衡树(Self-balancing Tree)

前言

树结构是一个非常重要的 nonlinear data structure(非线性数据结构),它可以用来实现:

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

那么如何实现树结构呢?

  1. 用 list of list
  2. 用 classes and references

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

Reference

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


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

  1. 把 root node 的值存为 list 的第一个值,list[0] = root-value
  2. list 的第二个值就是一个单独的 list,代表左边的那颗 subtree,list[1] = left-sublist
  3. list 的第三个值也是一个单独的 list,代表右边的那颗 subtree, list[2] = right-sublist
  4. 以此类推,每个 subtree 都和 parent 一样的结构
  5. 叶子节点:有 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 来实现树结构

  1. 定义一个 class (BinaryTree),它有 root value, left subtree, right subtree 这三个 attribute
  2. 每个 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())

Talk to Luna


Support Luna