树结构的两种实现方式（python）
2021-03-07
0. 相关文章
- 聊聊数据类型（Data Type）
- 聊聊数据结构（Data Structure）
- 聊聊关联数组（Associative Array）
- 聊聊树结构（Tree）
- 聊聊自我平衡树（Self-balancing Tree）
前言
树结构是一个非常重要的 nonlinear data structure（非线性数据结构），它可以用来实现：
- Associative Array (也就是 Map) ADT
- min/max heap（最大/最小堆）
- priority queue（优先队列）
那么如何实现树结构呢？
- 用 list of list
- 用 classes and references
这篇文章我们就来看看如何用以上两种方法实现树结构。
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. 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
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())