算法总结-二叉树
今天来总结一下二叉树，二叉树是一种树形结构，一个父节点有左右两个孩子节点（与二路树不一样），二叉树大概有以下几类：
- 二叉搜索树
- 满二叉树
- 完全二叉树
- 平衡二叉树(AVL)
- 红黑树
二叉树的有一些重要的性质：
- 在二叉树第k层最多有
2^(k-1)个节点 - 深度为h的树最多有
2^h-1个节点 N0 = N2 + 1,N0,N1,N2分别为度为0，1，2的节点数
对于性质3，显然二叉树节点数N = N0 + N1 + N2，设二叉树边数为e，根据树的性质有e = N - 1，根据二叉树的定义有e = 2*N2 + N1，于是N = 2*N2 + N1 + 1 => N0 = N2 + 1。
二叉树的节点结构通常定义如下：
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None # 指向左孩子
self.right = None # 指向右孩子
def __repr__(self):
return f'{{ {self.val}, left:{{{self.left}}}, right{{{self.right}}}}}'
```
#### 二叉树的遍历
二叉树的基础操作就是遍历，先中后序有递归和非递两种实现方法，递归很简单。非递归的实现写的比较少，但也应该保证能很快的写出来。大多数题目用递归的遍历就可以解，而且写起来简单。非递归的话，先序是**入栈前访问**节点，中序是**出栈后访问**节点，后序是**出栈**并且**右孩子访问过/或者没有右孩子**时访问节点，记住这些就好了。
层序访问需要使用到队列，也写过很多遍了。
```python
class BinaryTree:
def __init__(self, root):
self.root = root
def pre_recursive(self):
"""先序的递归写法"""
res = []
def pre(root):
nonlocal res
if root:
res += [root.val]
pre(root.left)
pre(root.right)
pre(self.root)
return res
def pre_non_recursive(self):
"""先序的非递归写法，注意时在入栈前访问"""
stack = []
res = []
p = self.root
while stack or p:
while p:
res += [p.val] # 访问节点
stack.append(p) # 入栈
p = p.left
if stack:
p = stack.pop()
p = p.right # 右子树
return res
def in_recursive(self):
"""中序的递归写法"""
res = []
def in_order(root):
nonlocal res
if root:
in_order(root.left)
res += [root.val]
in_order(root.right)
in_order(self.root)
return res
def in_non_recursive(self):
"""中序的非递归写法，注意在出栈后访问节点"""
stack = []
res = []
p = self.root
while stack or p:
while p:
stack.append(p) # 入栈
p = p.left
if stack:
p = stack.pop() # 出栈
res += [p.val] # 访问节点
p = p.right
return res
def post_recursive(self):
"""后序的递归写法"""
res = []
def post(root):
nonlocal res
if root:
post(root.left)
post(root.right)
res += [root.val]
post(self.root)
return res
def post_non_recursive(self):
"""后序的非递归写法，后续的非递归写法比较复杂，因为需要判断一个节点
的右孩子是否被访问过，实际中尝试用last来标记上一个访问的节点，判断上
一个访问是否时当前栈顶节点的右孩子。"""
res = []
stack = []
p = self.root
last = None
while stack or p:
while p:
stack.append(p) # 入栈
p = p.left
if stack:
p = stack[-1] # peek(not pop)
if p.right is None or last == p.right: # 没有右孩子/访问过右孩子
res += [p.val] # 访问节点
last = p
stack.pop() # 出栈
p = None # 别忘了这一步，不然会重复入栈
else:
p = p.right # 未访问过右子树
return res
def level(self):
p = self.root
from collections import deque
que = deque([p])
res = []
while que:
t = que.popleft()
res += [t.val] # 访问节点
if t.left:
que.append(t.left)
if t.right:
que.append(t.right)
return res
二叉搜索树
左孩子节点key < 父节点key <= 右孩子节点key的二叉树, 因此二叉树的中序序列是有序的。
之前总结的查找中提到树表查找，二叉搜索树就是其中一种，是一种应用十分广发的数据结构，实际上，平衡二叉树和红黑树都是为了优化二叉搜索树的的性能的数据结构。
1、BST的建树和插入
二叉树建树有插入建树和中序+先序/后序序列递归建树两种方法。 插入建树就是按照二叉树的先序顺序依次插入建树，这个过程中需要找到合适的插入位置，使用的二叉树的查找方法。
def build(pre):
def insert(root, x):
if not root: return TreeNode(x)
q = p = root
# 查找插入位置
while p:
q = p
if x >= p.val:
p = p.right
else:
p = p.left
# 插入
if q.val < x:
q.left = TreeNode(x)
else:
q.right = TreeNode(x)
return root
root = None
for x in pre:
root = insert(root, x)
return root
插入建树在最糟糕的情况下（插入序列有序）。有n个数要插入，对每个数插入时查找插入位置的比较次数为1+2+3+…+n-1，所以时间复杂度是O(n²)。这个时候的查找树是一个单支的树。我自己在当初考研PAT机试的时候就因为建树是偷懒直接写了插入的方法，然后导致后面两个测试用例TLE而没有拿到满分。
使用递归建树在最好时间复杂度为O(logn)，单支树的最坏情况是O(n)。方法如下。
def build(pre, ino):
# 使用先序和中序序列建树
if len(pre) == 0:
return None
root = TreeNode(pre[0])
idx = ino.index(pre[0])
n = idx
root.left = build(pre[1:n + 1], ino[:idx])
root.right = build(pre[n + 1:], ino[idx + 1:])
return root
2、BST的查找
小于就向左子树，大于就像右子树，等于就是找到了， 到叶子节点也没找到就是不存在，代码跟插入过程种的查找插入位置差不多，有递归和非递归两种写法，具体不写了。
3、BST的删除
删除要保持BST的有序结构，根据要删除的节点p的类型不同，具体有以下几种情况:
- p是叶子节点，可以直接删除
- p是非叶节点，但只有一个子树，则直接提升子树即可
- p是非叶节点，且有两个子树，则根据性质可以使用左子树的最大值或者右子树的最小值替换掉当前节点。
LeetCode 450.就是删除BST节点的题目。
class Solution_450:
def deleteNode(self, root, key):
def delete(root, key):
if not root:
return None
if root.val > key:
root.left = delete(root.left, key)
elif root.val < key:
root.right = delete(root.right, key)
else: # root.val == key:
if not root.left:
return root.right
elif not root.right:
return root.left
rsmall = root.right
while rsmall.left:
rsmall = rsmall.left
# 一般方法，交换值，递归的删除右子树的最小值节点
root.val = rsmall.val
root.right = delete(root.right, rsmall.val)
return root
return delete(root, key)
def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
def delete(root, key):
if not root:
return None
if root.val == key: # 找到了要删除的节点
# 叶子节点/只有一个子树的情况，提升另一个子树
if not root.left: # 没有左孩子（包括是叶子节点的情况)
return root.right
if not root.right:
return root.left
# 两个子树都存在，找右边的最小值
rsmall = root.right
while rsmall.left:
rsmall = rsmall.left
# trick, 把要删除节点的左子树放到，右子树的最小值左边，因为右子树的最小值
# 是一路向左查找到的，所以其原本左子树应该为空。相比于交换数据并把右子树的
# 最小值删除，这是更快速的做法（但会大幅打乱原树的结构）
rsmall.left = root.left
return root.right
else:
if root.val > key:
# 递归，在左子树上删除
root.left = delete(root.left, key)
elif root.val < key:
# 递归，在右子树上删除
root.right = delete(root.right, key)
return root
return delete(root, key)
完全二叉树
完全二叉树中，N1的数目为0/1，因此可以用二叉树的性质N = 2*N2 + N1 + 1求各种节点数。
N为奇数，显然N1 = 0, 则N2 = (N - 1) // 2,N0 = N2 + 1N为偶数，显然N1 = 1, 则N2 = N // 2 - 1,N0 = N2 + 1
经典题目LeetCode 958.检查一个二叉树树是否是完全二叉树。
class Solution_958:
# determine if root is a complete binary tree
def isCompleteTree(self, root):
# 层序遍历，我们遇到第一个None之后的所有节点
# 都应该是None, 如果有非None就不是完全二叉树。
bfs = [root]
i = 0
while bfs[i]:
bfs.append(bfs[i].left)
bfs.append(bfs[i].right)
i += 1
return not any(bfs[i:])
def isCompleteTree(self, root: TreeNode) -> bool:
nodes = [(root, 1)]
m = 1
num = 0
while num < len(nodes):
node, v = nodes[num]
m = max(m, v)
num += 1
if node.left:
nodes.append((node.left, 2 * v))
if node.right:
nodes.append((node.right, 2 * v + 1))
return num == m
值得注意的是第二种解法，我们在层序遍历的时候每次，都向队列中放入了一个索引值。根据完全二叉树由满二叉树而来的性质，对完全二叉树的节点层序从1开始编号，这样我们对一个编号为v的节点，它的左子树为2*v，右子树为2*v+1。实际上，完全二叉树可以用数组存储，这也是堆的原理，对于完全二叉树或者堆，节点数目等于最大的节点编号,关于堆还有很多可以讲的，不过留到以后再说。
平衡二叉搜索树(AVL)
要么空树，要么左右两个子树高度差绝对值不超过1，左右子树也是AVL树（树结构都是递归定义）。
AVL树为了优化查询性能而对二叉搜索树做的优化，与红黑树相比，AVL树是严格balanced的（左右子树高度差绝对值不超过1）。为了保持平衡的性质，插入和删除的时候需要进行旋转，而旋转比较费时，还很蛮烦，所以插入次数比较少的时候适合使用这个数据结构。 旋转的情况有四种，分开来看
1、RR型，一次左旋
# 1
# \ 2
# 2 ==> / \
# \ 1 3
# 3
def RR(root):
t = root.right
root.right = t.left
t.left = root
return t
2、LL型，一次右旋
# 3
# / 2
# 2 ==> / \
# / 1 3
# 1
def LL(root):
t = root.left
root.left = t.right
t.right = root
return t
3、RL型，先右旋一次变为RR型，再左旋一次
# 1 1
# \ \ 2
# 3 ==> 2 ==> / \
# / \ 1 3
# 2 3
def RL(root):
root.right = LL(root.right) # 右子树当做LL型向右旋
root = RR(root) #经第一步旋转后变为RR型，向左旋
return root
4、LR型，先左旋一次变为LL型，再右旋一次
# 3 3
# / / 2
# 1 ==> 2 ==> / \
# \ / 1 3
# 2 1
def LR(root):
root.left = RR(root.left)
root = LL(root)
return root
有了旋转操作之后，我们就可以在插入每一个节点后检查是否满足AVL树的要求，不满足就要根据各种类型进行旋转，判断类型的方式是树的高度差，因此我们需要一个求树高度的函数。
def height(root):
if not root: return 0
return 1 + max(height(root.left), height(root.right))
我们根据上述各种类型的定义和示意图，插入过程如下：
- 插入到一个节点的左子树，如果出现了不平衡（左子树比右子树高2），即出现了第一个L，可能会出现LL型或者LR型不平衡。如果该节点的左子树是平衡的则为LL型，否则是LR型。
- 插入到一个节点的右子树，如果出现了不平衡（右子树比左子树高2），即出现了第一个R，可能会出现RR型或者RL型不平衡，如果该节点的右子树是平衡的则为RR型，否则是RL型。
具体的代码如下。
def insert(root, x):
if not root:
root = TreeNode(x)
return root
if x <= root.val:
insert(root.left, x) # 插入到左子树
# 插入左子树之后可能出现：左子树高于右子树，可能出现LL/LR型
if height(root.left) - height(root.right) == 2:
if height(root.left.left) - height(root.left.right) == 1:
root = LL(root) # LL型，向右旋转
else:
root=LR(root) # LR型，先左旋，再右旋
else:
insert(root.right, x) # 插入到右子树
# 插入右子树之后可能出现：右子树高于左子树
if height(root.right) - height(root.left) == 2:
if height(root.right.right) - height(root.right. left)==1:
root = RR(root) # RR型，向左旋转
else:
root=RL(root) # RL型，先右旋，再左旋
AVL树也是一种二叉搜索树，删除的操作对应的和二叉树的操作相同，不过是每次删除之后从删除的父节点开始向跟逐层的调整平衡（进行旋转操作）。
def AVLdelete(root, key):
"""这里有比较多的重复代码，和插入过程的平衡代码一样，
只是为了说明情况，实际写的时候应该封装一下"""
if not root:
return None
if root.val > key:
root.left = AVLdelete(root.left, key)
# =============================================================
# 删除了左子树的节点，右子树可能高于左子树，可能出现RR型或者RL型
if height(root.right) - height(root.left) == 2:
if height(root.right.right) - height(root.right. left)==1:
root = RR(root) # RR型，向左旋转
else:
root=RL(root) # RL型，先右旋，再左旋
# =============================================================
elif root.val < key:
root.right = AVLdelete(root.right, key)
# =============================================================
# 删除了右子树的节点，左子树可能高于右子树，可能出现LL型或LR型
if height(root.left) - height(root.right) == 2:
if height(root.left.left) - height(root.left.right) == 1:
root = LL(root) # LL型，向右旋转
else:
root = LR(root) # LR型，先左旋，再右旋
# =============================================================
else: # root.val == key:
if not root.left:
return root.right
elif not root.right:
return root.left
rsmall = root.right
while rsmall.left:
rsmall = rsmall.left
# 一般方法，交换值，递归的删除右子树的最小值节点
root.val = rsmall.val
root.right = AVLdelete(root.right, rsmall.val)
# =============================================================
# 删除了右子树的节点，左子树可能高于右子树，可能出现LL型或LR型
if height(root.left) - height(root.right) == 2:
if height(root.left.left) - height(root.left.right) == 1:
root = LL(root) # LL型，向右旋转
else:
root = LR(root) # LR型，先左旋，再右旋
# =============================================================
return root
二叉树的题算是做的比较多，基本就是先中后序和层序访问节点时进行操作来解题。这篇只是写了一些基本知识和操作，就这么长了，后面再单独说一说红黑树和做到的一些有趣的树的题目。