树学习笔记 - Blog

参考资料

树的定义#

树(Tree)由若干节点(Node)和两两连接节点的边(Edge)组成。

递归定义：树是空集；或由根节点及0个或多个子树组成，其中子树亦是树，每个子树的根到根节点具有边相连。

节点(Node)是树的基本部分

每个节点具有名称，或“键值”，节点还可以保存额外数据项，数据项根据不同的应用而改变

边(Edge)是组成树的另一个基本部分

每条边恰好连接两个节点，表示节点之间具有关联，边具有出入方向；每个节点（除了根节点）恰有一条来自另一节点的入边；每个节点可以有多条连到其他节点的出边。

树的性质#

其中一个节点被指定为根节点(Root)
每个节点（除了根节点）恰连接一条来自节点p的边，p是n的父节点
每个节点从根开始的路径是唯一的
如果每个节点最多有两个子节点，这样的树被称为二叉树

树的嵌套列表实现#

1
Tree = [root,left,right]
2

3
def BinaryTree(r): #创建一个二叉树
4
    return [r, [], []]
5

6
def insertLeft(root, newBranch): #插入左子树
7
    t = root.pop(1)
8
    if len(t) > 1:
9
        root.insert(1, [newBranch, t, []])
10
    else:
11
        root.insert(1, [newBranch, [], []])
12
    return root
13

14
def insertRight(root, newBranch): #插入右子树
15
    t = root.pop(2)
16
    if len(t) > 1:
17
        root.insert(2, [newBranch, [], t])
18
    else:
19
        root.insert(2, [newBranch, [], []])
20
    return root
21

22
def getRootVal(root): #获取根节点
23
    return root[0]
24

25
def setRootVal(root, newVal): #设置根节点
26
    root[0] = newVal
27

28
def getLeftChild(root): #获取左子树
29
    return root[1]
30

31
def getRightChild(root): #获取右子树
32
    return root[2]

实例

1
root = BinaryTree('a')
2
insertRight(root, 'c')
3
insertLeft(root, 'b')
4
insertRight(root, 'e')
5
# 与实例 2 相同
6

7
left = getLeftChild(root)   # b 子树
8
right = getRightChild(root) # e 子树
9

10
insertLeft(left, 'x')       # b 的左侧：空 → 挂 x
11
insertRight(left, 'y')      # b 的右侧：空 → 挂 y
12

13
insertLeft(right, 'm')      # e 的左侧：空 → 挂 m（c 仍在 e 的右侧）
14

15
c = getRightChild(right)    # c 子树
16
insertLeft(c, 'p')          # c 左侧挂 p
17
insertRight(c, 'q')         # c 右侧挂 q

flowchart TB a(("a")) b(("b")) e(("e")) x(("x")) y(("y")) m(("m")) c(("c")) p(("p")) q(("q")) a --> b a --> e b --> x b --> y e --> m e --> c c --> p c --> q

树的链表实现#

1
class BinaryTree:
2
    def __init__(self, rootObj):
3
        self.key = rootObj
4
        self.leftChild = None
5
        self.rightChild = None
6

7
def insertLeft(self,newNode):
8
    if self.leftChild == None:
9
        self.leftChild = BinaryTree(newNode)
10
    else:
11
        t = BinaryTree(newNode)
12
        t.leftChild = self.leftChild
13
        self.leftChild = t
14

15
def insertRight(self,newNode):
16
    if self.rightChild == None:
17
        self.rightChild = BinaryTree(newNode)
18
    else:
19
        t = BinaryTree(newNode)
20
        t.rightChild = self.rightChild
21
        self.rightChild = t
22

23
def getRightChild(self):
24
    return self.rightChild
25

26
def getLeftChild(self):
27
    return self.leftChild
28

29
def setRootVal(self,obj):
30
    self.key = obj
31

32
def getRootVal(self):
33
    return self.key

树的应用#

表达式解析#

实例

从图示过程可以发现，创建树的关键是对当前节点的跟踪

创建左右子树可以用insertLeft和insertRight方法
当前节点设定值可以用setRootVal方法
下降到左右子树可以用getLeftChild和getRightChild方法

但是上升到父节点没有方法支持

因此我们可以用一个栈来记录跟踪父节点

当前节点下降时，将下降前的节点push入栈；当前节点上升时，上升到pop出栈的节点即可

1
def buildParseTree(fpexp): #构建解析树
2
    fplist = fpexp.split()
3
    pStack = Stack()
4
    eTree = BinaryTree('')
5
    pStack.push(eTree) #将根节点压入栈
6
    currentTree = eTree
7
    for i in fplist:
8
        if i == '(': #左括号
9
            currentTree.insertLeft('')
10
            pStack.push(currentTree) #入栈下降
11
            currentTree = currentTree.getLeftChild()
12
        elif i not in ['+','-','*','/',')']: #操作数
13
            currentTree.setRootVal(int(i))
14
            parent = pStack.pop() #出栈上升
15
            currentTree = parent
16
        elif i in ['+','-','*','/']: #操作符
17
            currentTree.setRootVal(i)
18
            currentTree.insertRight('')
19
            pStack.push(currentTree) #入栈下降
20
            currentTree = currentTree.getRightChild()
21
        elif i == ')': #右括号
22
            currentTree = pStack.pop() #出栈上升
23
        else:
24
            raise ValueError
25
    return eTree
26

27
import operator
28
def evaluate(parseTree): #计算解析树(递归)
29
    opers = {'+':operator.add, '-':operator.sub, '*':operator.mul, '/':operator.truediv}
30

31
    leftC = parseTree.getLeftChild() #缩小规模
32
    rightC = parseTree.getRightChild()
33

34
    if leftC and rightC:
35
        return opers[parseTree.getRootVal()](evaluate(leftC), evaluate(rightC)) #递归调用
36
    else:
37
        return parseTree.getRootVal() #叶子节点直接返回值(基本结束条件)
38
    ''' # 后序遍历实现
39
    res1 = None
40
    res2 = None
41
    if tree:
42
        res1 = evaluate(parseTree.getLeftChild())
43
        res2 = evaluate(parseTree.getRightChild())
44
        if res1 and res2:
45
            return opers[parseTree.getRootVal()](res1, res2)
46
        else:
47
            return parseTree.getRootVal()
48
    '''

树的遍历#

深度优先搜索 (DFS)#

前序遍历先访问根节点，再递归前序访问左子树，最后前序访问右子树

1
def preorder(tree):
2
    if tree != None:
3
        print(tree.getRootVal())
4
        preorder(tree.getLeftChild())
5
        preorder(tree.getRightChild())

中序遍历先递归中序访问左子树，再访问根节点，最后中序访问右子树

1
def inorder(tree):
2
    if tree != None:
3
        inorder(tree.getLeftChild())
4
        print(tree.getRootVal())
5
        inorder(tree.getRightChild())

后序遍历先递归后序访问左子树，再后序访问右子树，最后访问根节点

1
def postorder(tree):
2
    if tree != None:
3
        postorder(tree.getLeftChild())
4
        postorder(tree.getRightChild())
5
        print(tree.getRootVal())

广度优先搜索 (BFS)#

层序遍历

先访问根节点，再访问左子树，最后访问右子树

1
def levelorder(tree):
2
    if tree != None:
3
        print(tree.getRootVal())
4
        levelorder(tree.getLeftChild())
5
        levelorder(tree.getRightChild())

优先队列和二叉堆#

ADT BinaryHeap的操作定义如下

BinaryHeap() 创建一个空二叉堆对象
insert(k) 添加一个新key到堆中
findMin() 返回堆中最小的元素
delMin() 返回堆中最小的元素，并从堆中删除
isEmpty() 返回堆是否为空
size() 返回堆中key的个数
buildHeap(list) 从一个key列表中创建一个堆

python实现

1
class BinaryHeap:
2
   def __init__(self):
3
       self.heapList = [0]
4
       self.currentSize = 0
5

6
   def percUp(self,i): #上浮
7
       while i // 2 > 0:
8
           if self.heapList[i] < self.heapList[i // 2]:
9
               tmp = self.heapList[i // 2]
10
               self.heapList[i // 2] = self.heapList[i] #与父节点交换
11
               self.heapList[i] = tmp
12
           i = i // 2
13

14
   def insert(self,k): #插入
15
       self.heapList.append(k)
16
       self.currentSize = self.currentSize + 1
17
       self.percUp(self.currentSize)
18

19
   def percDown(self,i): #下沉
20
       while (i * 2) <= self.currentSize:
21
           mc = self.minChild(i)
22
           if self.heapList[i] > self.heapList[mc]:
23
               tmp = self.heapList[i]
24
               self.heapList[i] = self.heapList[mc]
25
               self.heapList[mc] = tmp
26
           i = mc
27

28
   def minChild(self,i): #最小子节点
29
       if i * 2 + 1 > self.currentSize:
30
           return i * 2
31
       else:
32
           if self.heapList[i*2] < self.heapList[i*2+1]:
33
               return i * 2
34
           else:
35
               return i * 2 + 1
36

37
   def delMin(self): #删除最小值
38
       retval = self.heapList[1]
39
       self.heapList[1] = self.heapList[self.currentSize]
40
       self.currentSize = self.currentSize - 1
41
       self.heapList.pop()
42
       self.percDown(1)
43
       return retval

二叉查找树(BST)#

1
class BinarySearchTree:
2
   def __init__(self):
3
       self.root = None
4
       self.size = 0
5

6
   def length(self):
7
       return self.size
8

9
   def __len__(self):
10
       return self.size
11

12
   def __iter__(self):
13
       return self.root.__iter__()
14

15
   def put(self,key,val): #插入节点
16
       if self.root:
17
           self._put(key,val,self.root)
18
       else:
19
           self.root = TreeNode(key,val)
20
           self.size = self.size + 1
21

22
   def _put(self,key,val,currentNode): #插入节点
23
       if key < currentNode.key:
24
           if currentNode.hasLeftChild():
25
               self._put(key,val,currentNode.leftChild)
26
           else:
27
               currentNode.leftChild = TreeNode(key,val,parent=currentNode)
28
       else:
29
           if currentNode.hasRightChild():
30
               self._put(key,val,currentNode.rightChild)
31
           else:
32
               currentNode.rightChild = TreeNode(key,val,parent=currentNode)
33

34
   def __setitem__(self,k,v):
35
       self.put(k,v)
36

37
   def get(self,key): #获取节点
38
       if self.root:
39
           res = self._get(key,self.root)
40
           if res:
41
               return res.payload
42
           else:
43
               return None
44
       else:
45
           return None
46

47
   def _get(self,key,currentNode): #获取节点
48
       if not currentNode:
49
           return None
50
       elif currentNode.key == key:
51
           return currentNode
52
       elif key < currentNode.key:
53
           return self._get(key,currentNode.leftChild)
54
       else:
55
           return self._get(key,currentNode.rightChild)
56

57
   def  __getitem__(self,key): #获取节点
58
       return self.get(key)
59

60
   def __contains__(self,key): #是否包含节点
61
       if self._get(key,self.root):
62
           return True
63
       else:
64
           return False
65

66
   def delete(self,key): #删除节点
67
       if self.size > 1:
68
           nodeToRemove = self._get(key,self.root)
69
           if nodeToRemove:
70
               self.remove(nodeToRemove)
71
               self.size = self.size - 1
72
           else:
73
               raise KeyError('Error, key not in tree')
74
       elif self.size == 1 and self.root.key == key:
75
           self.root = None
76
           self.size = self.size - 1
77
       else:
78
           raise KeyError('Error, key not in tree')
79

80
   def __delitem__(self,key):
81
       self.delete(key)
82

83
   def remove(self,currentNode): #删除节点
84
       if currentNode.isLeaf():  # 1) 叶子节点
85
           if currentNode.isRoot():
86
               self.root = None
87
           elif currentNode.isLeftChild():
88
               currentNode.parent.leftChild = None
89
           else:
90
               currentNode.parent.rightChild = None
91
       elif currentNode.hasBothChildren():  # 2) 两个子节点
92
           succ = currentNode.findSuccessor()
93
           succ.spliceOut()
94
           currentNode.key = succ.key
95
           currentNode.payload = succ.payload
96
       else:  # 3) 只有一个子节点
97
           child = currentNode.leftChild if currentNode.hasLeftChild() else currentNode.rightChild
98
           if currentNode.isRoot():
99
               self.root = child
100
               child.parent = None
101
           elif currentNode.isLeftChild():
102
               currentNode.parent.leftChild = child
103
               child.parent = currentNode.parent
104
           else:
105
               currentNode.parent.rightChild = child
106
               child.parent = currentNode.parent
107

108

109
class TreeNode:
110
   def __init__(self,key,val,left=None,right=None,parent=None):
111
       self.key = key
112
       self.payload = val
113
       self.leftChild = left
114
       self.rightChild = right
115
       self.parent = parent
116

117
   def hasLeftChild(self): #是否有左子节点
118
       return self.leftChild
119

120
   def hasRightChild(self): #是否有右子节点
121
       return self.rightChild
122

123
   def isLeftChild(self): #是否是左子节点
124
       return self.parent and self.parent.leftChild == self
125

126
   def isRightChild(self): #是否是右子节点
127
       return self.parent and self.parent.rightChild == self
128

129
   def isRoot(self): #是否是根节点
130
       return not self.parent
131

132
   def isLeaf(self): #是否是叶子节点
133
       return not (self.rightChild or self.leftChild)
134

135
   def hasAnyChildren(self): #是否有子节点
136
       return self.rightChild or self.leftChild
137

138
   def hasBothChildren(self): #是否有两个子节点
139
       return self.rightChild and self.leftChild
140

141
   def replaceNodeData(self,key,value,lc,rc): #替换节点数据
142
       self.key = key
143
       self.payload = value
144
       self.leftChild = lc
145
       self.rightChild = rc
146
       if self.hasLeftChild():
147
           self.leftChild.parent = self
148
       if self.hasRightChild():
149
           self.rightChild.parent = self
150

151
   def __iter__(self): #中序遍历
152
       if self:
153
           if self.hasLeftChild():
154
               for elem in self.leftChild:
155
                   yield elem
156
           yield self.key
157
           if self.hasRightChild():
158
               for elem in self.rightChild:
159
                   yield elem
160

161
   def findSuccessor(self): #删除节点时找到后继节点
162
       succ = None
163
       if self.hasRightChild():
164
           succ = self.rightChild.findMin()
165
       else:
166
           if self.parent:
167
               if self.isLeftChild():
168
                   succ = self.parent
169
               else:
170
                   self.parent.rightChild = None
171
                   succ = self.parent.findSuccessor()
172
                   self.parent.rightChild = self
173
       return succ
174

175
   def findMin(self): #找到最小节点
176
       current = self
177
       while current.hasLeftChild():
178
           current = current.leftChild
179
       return current
180

181
   def spliceOut(self): #删除节点时摘除当前节点
182
       if self.isLeaf():
183
           if self.isLeftChild():
184
               self.parent.leftChild = None
185
           else:
186
               self.parent.rightChild = None
187
       elif self.hasAnyChildren():
188
           if self.hasLeftChild():
189
               if self.isLeftChild():
190
                   self.parent.leftChild = self.leftChild
191
               else:
192
                   self.parent.rightChild = self.leftChild
193
               self.leftChild.parent = self.parent
194
           else:
195
               if self.isLeftChild():
196
                   self.parent.leftChild = self.rightChild
197
               else:
198
                   self.parent.rightChild = self.rightChild
199
               self.rightChild.parent = self.parent

AVL树(平衡二叉查找树)#

复杂度最差为O(log n)

实现方法：在插入和删除节点时，通过旋转操作保持树的平衡

Mermaid：4 种失衡与旋转示意#

LL（左左）：对失衡节点做一次右旋

flowchart TB subgraph Before_LL["LL 失衡（插入到左子树的左侧）"] A1(("A")) --> B1(("B")) A1 --> Ar1(("T3")) B1 --> C1(("C")) B1 --> Br1(("T2")) C1 --> Cl1(("T0")) C1 --> Cr1(("T1")) end subgraph After_LL["右旋 A 后"] B2(("B")) --> C2(("C")) B2 --> A2(("A")) C2 --> Cl2(("T0")) C2 --> Cr2(("T1")) A2 --> Ar2(("T3")) A2 --> Al2(("T2")) end

RR（右右）：对失衡节点做一次左旋

flowchart TB subgraph Before_RR["RR 失衡（插入到右子树的右侧）"] A1(("A")) --> Al1(("T0")) A1 --> B1(("B")) B1 --> Bl1(("T1")) B1 --> C1(("C")) C1 --> Cl1(("T2")) C1 --> Cr1(("T3")) end subgraph After_RR["左旋 A 后"] B2(("B")) --> A2(("A")) B2 --> C2(("C")) A2 --> Al2(("T0")) A2 --> Ar2(("T1")) C2 --> Cl2(("T2")) C2 --> Cr2(("T3")) end

LR（左右）：先对左子节点左旋，再对失衡节点右旋

flowchart TB subgraph Before_LR["LR 失衡（插入到左子树的右侧）"] A1(("A")) --> B1(("B")) A1 --> Ar1(("T3")) B1 --> Bl1(("T0")) B1 --> C1(("C")) C1 --> Cl1(("T1")) C1 --> Cr1(("T2")) end subgraph After_LR["左旋 B，再右旋 A 后"] C2(("C")) --> B2(("B")) C2 --> A2(("A")) B2 --> Bl2(("T0")) B2 --> Br2(("T1")) A2 --> Al2(("T2")) A2 --> Ar2(("T3")) end

RL（右左）：先对右子节点右旋，再对失衡节点左旋

flowchart TB subgraph Before_RL["RL 失衡（插入到右子树的左侧）"] A1(("A")) --> Al1(("T0")) A1 --> B1(("B")) B1 --> C1(("C")) B1 --> Br1(("T3")) C1 --> Cl1(("T1")) C1 --> Cr1(("T2")) end subgraph After_RL["右旋 B，再左旋 A 后"] C2(("C")) --> A2(("A")) C2 --> B2(("B")) A2 --> Al2(("T0")) A2 --> Ar2(("T1")) B2 --> Bl2(("T2")) B2 --> Br2(("T3")) end

1
def __put(self,key,val,currentNode):
2
    if key < currentNode.key:
3
        if currentNode.hasLeftChild():
4
            self.__put(key,val,currentNode.leftChild)
5
        else:
6
            currentNode.leftChild = TreeNode(key,val,parent=currentNode)
7
            self.updateBalance(currentNode.leftChild)
8
    else:
9
        if currentNode.hasRightChild():
10
            self.__put(key,val,currentNode.rightChild)
11
        else:
12
            currentNode.rightChild = TreeNode(key,val,parent=currentNode)
13
            self.updateBalance(currentNode.rightChild)
14

15
def updateBalance(self,node):
16
    if node.balanceFactor > 1 or node.balanceFactor < -1:
17
        self.rebalance(node) #重新平衡
18
        return
19
    if node.parent != None:
20
        if node.isLeftChild():
21
            node.parent.balanceFactor += 1
22
        elif node.isRightChild():
23
            node.parent.balanceFactor -= 1
24

25
        if node.parent.balanceFactor != 0:
26
            self.updateBalance(node.parent) #调整父节点因子
27

28
def rotateLeft(self,rotRoot):
29
    newRoot = rotRoot.rightChild
30
    rotRoot.rightChild = newRoot.leftChild
31
    if newRoot.leftChild != None:
32
        newRoot.leftChild.parent = rotRoot
33
    newRoot.parent = rotRoot.parent
34
    if rotRoot.isRoot():
35
        self.root = newRoot
36
    else:
37
        if rotRoot.isLeftChild():
38
            rotRoot.parent.leftChild = newRoot
39
        else:
40
            rotRoot.parent.rightChild = newRoot
41
    newRoot.leftChild = rotRoot
42
    rotRoot.parent = newRoot
43
    rotRoot.balanceFactor = rotRoot.balanceFactor + 1 - min(newRoot.balanceFactor, 0)
44
    newRoot.balanceFactor = newRoot.balanceFactor + 1 + max(rotRoot.balanceFactor, 0)
45

46
def rebalance(self,node):
47
    if node.balanceFactor < 0:
48
        if node.rightChild.balanceFactor > 0:
49
            #右左旋
50
            self.rotateRight(node.rightChild)
51
            self.rotateLeft(node)
52
        else:
53
            #左旋
54
            self.rotateLeft(node)
55
    elif node.balanceFactor > 0:
56
        if node.leftChild.balanceFactor < 0:
57
            #左右旋
58
            self.rotateLeft(node.leftChild)
59
            self.rotateRight(node)
60
        else:
61
            #右旋
62
            self.rotateRight(node)

红黑树（Red-Black Tree）#

性质

每个节点要么是红色，要么是黑色
根节点是黑色
所有叶子（指空节点）都是黑色
不允许出现两个相邻的红色节点（不能出现“红-红相连”）
从任一节点到其所有叶子节点（空节点）的路径上，黑色节点数相同

直观理解：红黑树允许“局部不平衡”，但通过黑高约束避免退化成链表。

由性质 4 与性质 5 可以推出：任一路径上红节点不会连续出现，最长路径不会超过最短路径的 2 倍，因此高度是O(log n)。

红黑树插入操作#

红黑树删除操作#

AVL：更严格平衡，通常查找更快，但插删调整可能更多
红黑：更宽松平衡，插删更“省旋转/更稳定”，工程中常用（如很多语言库的有序映射/集合）

人よ、幸福に生きよ