小米 6 首席研究员的研究报告集

Hi there!

Python数据结构与算法补全系列(四)--树

Posted on Edited on In ,

树的术语和定义

节点

节点是树的基础部分。节点可以有自己的名字，被称作“键”，节点也可以有附带信息，被称为“有效载荷”。

边

两个节点通过一条边相连，表示他们之间存在关系。除了根节点之外，其他每个节点仅有一条入边，出边则可能有多条。

根节点

根节点是树中唯一没有入边的节点。

路径

路径是由边连接的有序节点列表。比如，哺乳纲->食肉目->猫科->猫属->家猫。

子节点

一个节点通过出边与子节点相连。

父节点

一个节点是所有其子节点的父节点。

兄弟节点

具有同一父节点的节点互称为兄弟节点。

子树

一个父节点及其所有后代的节点和边构成一颗子树

叶子节点

叶子节点没有子节点。

层数

节点 n 的层数是从根节点到 n 的唯一长度路径。

高度

树的高度是其中节点层数的最大值。

树的定义一

树有以下属性：

  • 有一个根节点
  • 除根节点外，其他每个节点都与其唯一的父节点相连
  • 从根节点到其他每个节点都有且仅有一条路径
  • 如果每个节点最多有两个子节点，这样的树就被称为二叉树

树的定义二

一棵树要么为空，要么由一个根节点和零颗或多颗子树构成，子树本身也是一棵树。
每颗子树的根节点通过一条边连到父树的根节点。

树的 Python 实现

根据上面的定义，可以用以下的函数创建并操作二叉树。

  • BinaryTree() 创建一个二叉树实例
  • getLeftChild() 返回当前节点的左子节点所对应的二叉树
  • getRightChild() 返回当前节点的右子节点所对应的二叉树
  • setRootVal(val) 在当前节点中存储参数 val 中的对象
  • getRootVal() 返回当前节点存储的对象
  • insertLeft(val) 新建一棵二叉树，并将其作为当前节点的左子节点
  • insertRight(val) 新建一棵二叉树，并将其作为当前节点的右子节点

树的实现形式之一：列表之列表

在列表之列表的树中，根节点的值作为列表的第一个元素，第二个元素是代表左子树的列表，第三个元素代表右子树。

graph TB

a((a))
b((b))
c((c))
d((d))
e((e))
f((f))
a-->b
a-->c
b-->d
b-->e
c-->f
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
my_tree = [
  'a': # 根节点
  [
    'b': # 左子树
    [
      'd', [] ,[]
    ],
    [
      'e', [], []
    ]
    'c', # 右子树
    [
      'f', [], []
    ],
    []
  ]
]

可以通过标准的列表切片访问子树。子树的列表结构也符合树的定义，所以列表之列表的结构是递归地。这种表示法可以推广到有很多子树的情况。

1
2
3
4
5
6
7
8
9
>>> my_tree = ['a', ['b', ['d', [], []], ['e', [], []]], ['c', ['f', [], []], []]]
>>> my_tree
['a', ['b', ['d', [], []], ['e', [], []]], ['c', ['f', [], []], []]]
>>> my_tree[1]
['b', ['d', [], []], ['e', [], []]] 
>>> my_tree[0]
'a'
>>> my_tree[2]
['c', ['f', [], []], []]

通过函数定义树的数据结构：

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
def binary_tree(r):
    return [r, [], []]

## 插入左子树
def insert_left(root, new_branch):
    t = root.pop(1)
    if len(t) > 1:
        root.insert(1, [new_branch, t, []])
    else:
        root.insert(1, [new_branch, [], []])
    return root

## 插入右子树
def insert_right(root, new_branch):
    t = root.pop(2)
    if len(t) > 1:
        root.insert(2, [new_branch,[], t])
    else:
        root.insert(2, [new_branch, [], []])
    return root

def get_root_val(root):
    return root[0]

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

def get_left_child(root):
    return root[1]

def get_right_child(root):
    return root[2]

要给树添加左子树时要特别注意，如果列表的左子树位置已经有内容了，要保留已有内容，并将它作为新列表的左子树。右子树同理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
>>> r = binary_tree(3)
>>> insert_left(r, 4)
[3, [4, [], []], []]
>>> insert_left(r, 5)
[3, [5, [4, [], []], []], []]
>>> insert_right(r, 6)
[3, [5, [4, [], []], []], [6, [], []]]
>>> insert_right(r, 7)
[3, [5, [4, [], []], []], [7, [], [6, [], []]]]
>>> l = get_left_child(r)
>>> l
[5, [4, [], []], []]
>>> set_root_val(l, 9)
>>> r
[3, [9, [4, [], []], []], [7, [], [6, [], []]]]
>>> insert_left(l, 11)
[9, [11, [4, [], []], []], []]
>>> r
[3, [9, [11, [4, [], []], []], []], [7, [], [6, [], []]]]
>>> get_right_child(get_right_child(r))
[6, [], []]

树的实现形式之二：节点与引用

节点与引用表示法将树定义为一个类, 其中有根节点与左右子树的属性。树的左子树属性和右子树属性会指向树类的其他实例。

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
## BinaryTree 类
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 == None:
            self.left_child = BinaryTree(new_node)
        else:
            t = BinaryTree(new_node)
            t.left_child = self.left_child
            self.left_child = t
    
    ## 插入右子节点
    def insert_right(self, new_node):
        if self.right_child == None:
            self.right_child = BinaryTree(new_node)
        else:
            t = BinaryTree(new_node)
            t.right_child = self.right_child
            self.right_child = t
    ## 二叉树的访问函数
    def get_right_child(self):
        return self.right_child
    
    def get_left_child(self):
        return self.left_child
    
    def set_root_val(self, obj):
        self.key = obj
    
    def get_root_val(self):
        return self.key

正如二叉树的子树都是二叉树，根节点的左右子节点本身都是 BinaryTree 类的实例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
>>> r = BinaryTree('a')
>>> r.get_root_val()
'a'
>>> print(r.get_left_child())
None
>>> r.insert_left('b')
>>> print(r.get_left_child())
<__main__.BinaryTree object at 0x0000019EA28B8700>
>>> print(r.get_left_child().get_root_val())
b
>>> r.insert_right('c')
>>> print(r.get_right_child())
<__main__.BinaryTree object at 0x0000019EA2793E80>
>>> print(r.get_right_child().get_root_val())
c
>>> r.get_right_child().set_root_val('hello')
>>> print(r.get_right_child().get_root_val())
hello
>>>

二叉树树的应用

解析树

可以用上面已经实现的树来解析一些实际问题，比如数学表达式这样的构造。比如，可以将 ((7 + 3) * (5 - 2)) 这样的数学表达式表示成解析树。

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
from pythonds.basic import Stack
from pythonds.trees import BinaryTree

def build_parse_tree(fpexp):
    fplist = fpexp.split()
    p_stack = Stack()
    e_tree = BinaryTree('')
    p_stack.push(e_tree)
    current_tree = e_tree
    
    for i in fplist:
        if i == '(':
            current_tree.insertLeft('')
            p_stack.push(current_tree)
            current_tree = current_tree.getLeftChild()
        elif i not in '+-*/)':
            current_tree.setRootVal(eval(i))
            parent = p_stack.pop()
            current_tree = parent
        elif i in '+-*/':
            current_tree.setRootVal(i)
            current_tree.insertRight('')
            p_stack.push(current_tree)
            current_tree = current_tree.getRightChild()
        elif i == ')':
            current_tree = p_stack.pop()
        else:
            raise ValueError("Unknown Operator: " + i)
    return e_tree

定义如下 4 条规则：

  1. 如果当前标记是 ( ，就为当前节点添加一个左子节点，并下沉至该子节点
  2. 如果当前标记在列表 [‘+’, ‘-‘, ‘/‘, ‘*’] 中，就将当前节点的值设为当前标记对应的运算符；为当前节点添加一个右子节点，并下沉至该子节点
  3. 如果当前标记是数字，就将当前节点的值设为这个数并返回至父节点
  4. 如果当前标记是 ) ，就跳到当前节点的父节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import operator
## 计算二叉树的递归函数
def evaluate(parse_tree):
    opers = {
         '+':operator.add, 
          '-':operator.sub, 
          '*':operator.mul, 
          '/':operator.truediv}
    left_c = parseTree.getLeftChild() 
    right_c = parseTree.getRightChild() 
    
    if left_c and right_c:
        fn = opers[parseTree.getRootVal()] 
        return fn(evaluate(left_c), evaluate(right_c))
    else:
        return parseTree.getRootVal()
1
2
3
4
>>> fpexp = '( ( 7 + 3 ) * ( 5 - 2 ) )'
>>> fpexp_tree =  build_parse_tree(fpexp)
>>> evaluate(fpexp_tree)
30

树的遍历

树的遍历方法有三种： 前序遍历、中序遍历和后序遍历

  • 前序遍历：在前序遍历中，先访问根节点，然后递归地前序遍历左子树，最后递归地前序遍历右子树。
  • 中序遍历：在中序遍历中，先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。
  • 后序遍历：在后序遍历中，先递归地后序遍历右子树，然后递归地后序遍历左子树，最后访问根节点。
1
2
3
4
5
6
7
## 将前序遍历算法实现为 BinaryTree 类的方法
def preorder(self):
    print(self.key)
    if self.left_child:
        self.left_child.preorder()
    if self.right_child：
        self.right_child.preorder()

用后序遍历重写计算函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def post_order_eval(tree):
    opers = {
         '+':operator.add, 
          '-':operator.sub, 
          '*':operator.mul, 
          '/':operator.truediv}
    
    res1 = None
    res2 = None
    
    if tree:
        res1 = post_order_eval(tree.getLeftChild())
        res2 = post_order_eval(tree.getRightChild())
        if res1 and res2:
            return opers[tree.getRootVal()](res1, res2)
        else:
            return tree.getRootVal()

用中序遍历打印括号表达式:

1
2
3
4
5
6
7
8
9
def printexp(tree):
    s_val = ""
    
    if tree:
        s_val = '(' + printexp(tree.getLeftChild())
        s_val = s_val + str(tree.getRootVal())
        s_val = s_val + printexp(tree.getRightChild()) + ')'
    
    return s_val
1
2
3
4
5
6
7
8
9
10
11
12
13
14
>>> from pythonds.trees import BinaryTree 
>>> x = BinaryTree('*') 
>>> x.insertLeft('+')  
>>> l = x.getLeftChild() 
>>> l.insertLeft(4) 
>>> l.insertRight(5) 
>>> x.insertRight(7) 
>>> 
>>> print(printexp(x)) 
(((4) + (5)) * (7)) 
>>> 
>>> print(postordereval(x)) 
63 
>>>

二叉堆

二叉堆是实现优先级队列的经典方法。而插队的入队和出队操作都可以达到 O(logn)。二叉堆画出来很像一棵树，但实现时只用一个列表作为内部表示。
二叉堆的两个常见的变体为：最小堆（最小的元素一直在队首）与最大堆（最大的元素一直在队首）。

二叉堆的实现

如果一个二叉树除了最底层，其他每一层的节点都是满的，这个二叉树就被称为完全二叉树。引出完全二叉树的概念有助于高效地实现二叉堆。

堆的有序性：对于堆中任意元素 x 及其父元素 p，p 都不大于 x。
二叉堆类 BinaryHeap 的 heal_list 的第一个元素是 0 ，它的唯一用途是为了使后续的方法可以使用整数除法。

BinaryHeap 的 insert 方法先将元素追加到列表的末尾，然后通过比较新元素与父元素的大小。如果新元素小于其父元素就将二者交换，以此来保证堆的结构性质。通过 perc_up 方法，元素将一直沿着树向上移动，指导重获堆的结构性质。

BinaryHeap 的 del_min 方法的难点是，如何在移除根节点后重构堆的性质和有序性。可以分两步重建堆：第一步，取出列表中最后一个元素，将其移到根节点的位置;第二步，将新的根节点沿着树推到正确的位置。通过辅助函数 perc_down 和 min_child 方法来实现上述 del_min 方法。

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
class BinaryHeap:
    def __init__(self):
        self.heap_list = [0]
        self.current_size = 0
    
    def perc_up(self, i):
        while i // 2 > 0:
            if self.heap_list[i] < self.heap_list[i // 2]:
                self.heap_list[i // 2], self.heap_list[i] = self.heap_list[i], self.heap_list[i // 2]
            i = i // 2
    
    def insert(self, k):
        self.heap_list.append(k)
        self.curent_size = self.current_size + 1
        self.perc_up(self.current_size)
    
    def perc_down(self, i):
        while (i * 2) <= self.current_size:
            mc = self.min_child(i)
            if self.heap_list[i] > self.heap_list[mc]:
                self.heap_list[i], self.heap_list[mc] = self.heap_list[mc], self.heap_list[i]
            i = mc
    
    def min_child(self, i):
        if i * 2 + 1 > self.current_size:
            return i * 2
        else:
            if self.heap_list[i * 2] < self.heap_list[i * 2 + 1]:
                return i * 2
            else:
                return i * 2 + 1
    
    def del_min(self):
        ret_val = self.heap_list[i]
        self.heap_list[1] = self.heap_list[self.current_size]
        self.current_size = self.current_size - 1
        self.heap_list.pop()
        self.perc_down(1)
        return ret_val
    
    def build_heap(self, alist):
        i = len(alist) // 2
        self.current_size = len(alist)
        self.heap_list = [0] + alist[:]
        while (i > 0):
            self.perc_down(i)
            i = i - 1
1
2
3
4
>>>a = BinaryHeap()
>>>a.build_heap([9, 5, 6, 2, 3])
>>>print(a.heap_list)
[0, 2, 3, 6, 5, 9]

二叉搜索树

二叉搜索树是映射的另一种实现。

二叉搜索树依赖于这样一个性质：小于父节点的键都在左子树中，大于父节点的键则都在右子树中。

使用 BinarySearchTree 类和 TreeNode 类来实现二叉搜索树：

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
class BinarySearchTree:

    def __init__(self):
        self.root = None
        self.size = 0

    def length(self):
        return self.size

    def __len__(self):
        return self.size

    def __iter__(self):
        return self.root.__iter__()

    def put(self,key,val):
        if self.root:
            self._put(key,val,self.root)
        else:
            self.root = TreeNode(key,val)
        self.size = self.size + 1

    def _put(self,key,val,currentNode):
        if key < currentNode.key:
            if currentNode.hasLeftChild():
                self._put(key,val,currentNode.leftChild)
            else:
                currentNode.leftChild = TreeNode(key,val,parent=currentNode)
        else:
            if currentNode.hasRightChild():
                self._put(key,val,currentNode.rightChild)
            else:
                currentNode.rightChild = TreeNode(key,val,parent=currentNode)

    def __setitem__(self,k,v):
        self.put(k,v)

    def get(self,key):
        if self.root:
            res = self._get(key,self.root)
            if res:
                return res.payload
            else:
                return None
        else:
            return None

    def _get(self,key,currentNode):
        if not currentNode:
            return None
        elif currentNode.key == key:
            return currentNode
        elif key < currentNode.key:
            return self._get(key,currentNode.leftChild)
        else:
            return self._get(key,currentNode.rightChild)

    def __getitem__(self,key):
        return self.get(key)

    def __contains__(self,key):
        if self._get(key,self.root):
            return True
        else:
            return False

    def delete(self,key):
    if self.size > 1:
        nodeToRemove = self._get(key,self.root)
        if nodeToRemove:
            self.remove(nodeToRemove)
            self.size = self.size-1
        else:
            raise KeyError('Error, key not in tree')
    elif self.size == 1 and self.root.key == key:
        self.root = None
        self.size = self.size - 1
    else:
        raise KeyError('Error, key not in tree')

    def __delitem__(self,key):
        self.delete(key)

    def findSuccessor(self):
        succ = None
        if self.hasRightChild():
            succ = self.rightChild.findMin()
        else:
            if self.parent:
                if self.isLeftChild():
                    succ = self.parent
                else:
                    self.parent.rightChild = None
                    succ = self.parent.findSuccessor()
                    self.parent.rightChild = self
        return succ

    def findMin(self):
        current = self
        while current.hasLeftChild():
            current = current.leftChild
        return current

    def spliceOut(self):
        if self.isLeaf():
            if self.isLeftChild():
                self.parent.leftChild = None
            else:
                self.parent.rightChild = None
        elif self.hasAnyChildren():
            if self.hasLeftChild():
                if self.isLeftChild():
                    self.parent.leftChild = self.leftChild
                else:
                    self.parent.rightChild = self.leftChild
                self.leftChild.parent = self.parent
            else:
                if self.isLeftChild():
                    self.parent.leftChild = self.rightChild
                else:
                    self.parent.rightChild = self.rightChild
                self.rightChild.parent = self.parent

    def remove(self, currentNode):
        if currentNode.isLeaf():
            if currentNode == currentNode.parent.leftChild:
                currentNode.parent.leftChild = None
            else:
                currentNode.parent.rightChild = None

        else: # this node has one child
            if currentNode.hasLeftChild():
                if currentNode.isLeftChild():
                currentNode.leftChild.parent = currentNode.parent
                currentNode.parent.leftChild = currentNode.leftChild
                elif currentNode.isRightChild():
                currentNode.leftChild.parent = currentNode.parent
                currentNode.parent.rightChild = currentNode.leftChild
                else:
                currentNode.replaceNodeData(currentNode.leftChild.key,
                                    currentNode.leftChild.payload,
                                    currentNode.leftChild.leftChild,
                                    currentNode.leftChild.rightChild)
            else:
                if currentNode.isLeftChild():
                currentNode.rightChild.parent = currentNode.parent
                currentNode.parent.leftChild = currentNode.rightChild
                elif currentNode.isRightChild():
                currentNode.rightChild.parent = currentNode.parent
                currentNode.parent.rightChild = currentNode.rightChild
                else:
                currentNode.replaceNodeData(currentNode.rightChild.key,
                                    currentNode.rightChild.payload,
                                    currentNode.rightChild.leftChild,
                                    currentNode.rightChild.rightChild)

        elif currentNode.hasBothChildren(): #interior
                succ = currentNode.findSuccessor()
                succ.spliceOut()
                currentNode.key = succ.key
                currentNode.payload = succ.payload

    def __iter__(self):
    if self:
        if self.hasLeftChild():
                for elem in self.leftChiLd:
                    yield elem
        yield self.key
        if self.hasRightChild():
                for elem in self.rightChild:
                    yield elem

class TreeNode:
   def __init__(self,key,val,left=None,right=None,
                                       parent=None):
        self.key = key
        self.payload = val
        self.leftChild = left
        self.rightChild = right
        self.parent = parent

    def hasLeftChild(self):
        return self.leftChild

    def hasRightChild(self):
        return self.rightChild

    def isLeftChild(self):
        return self.parent and self.parent.leftChild == self

    def isRightChild(self):
        return self.parent and self.parent.rightChild == self

    def isRoot(self):
        return not self.parent

    def isLeaf(self):
        return not (self.rightChild or self.leftChild)

    def hasAnyChildren(self):
        return self.rightChild or self.leftChild

    def hasBothChildren(self):
        return self.rightChild and self.leftChild

    def replaceNodeData(self,key,value,lc,rc):
        self.key = key
        self.payload = value
        self.leftChild = lc
        self.rightChild = rc
        if self.hasLeftChild():
            self.leftChild.parent = self
        if self.hasRightChild():
            self.rightChild.parent = self