二叉树--python

二叉树

一、概述

1、介绍

是一种非线性数据结构，将数据一分为二，代表根与叶的派生关系，和链表的结构类似，二叉树的基本单元是结点，每个节点包括值和左右子节点引用。

每个节点都有两个引用（类似于双向链表），分别指向左子节点和右子节点，该节点被称为这两个子节点的父节点。当给定一个二叉树的结点时，我们将在该节点的左子节点以及其以下结点所形成的树称为左子树，同理，右子节点的部分被称为右子树。

在二叉树中，除了叶节点外，其他的所有节点都包含子节点和非空子树。

2、常见术语

根节点：

位于二叉树顶层的节点，没有父节点

叶节点：

没有子节点的节点，左右两个指针都指向None

边：

连接两个节点的线，就是节点引用，也就是我们用的指针

层：

从树的根部开始递增，根的层数为1

度：

节点的子节点数量，如果是普通的树，没有限制，如果是二叉树，取值范围则被限制在0，1，2

二叉树高度：

从根节点到最远的叶节点所经过边的数量，也可以理解为最下层叶子节点的层数 - 1

节点的深度：

从根节点到这个节点所经过的边的数量，同理也可以是该节点层数 - 1

节点的高度：

从距离该节点最远的叶节点到该节点所经过的边的数量

3、基本操作

(一)定义节点

class TreeNode():def __init__(self, val: int):# 节点值self.val: int = val# 左节点指针self.left: TreeNode | None = None# 右节点指针self.right: TreeNode | None = None

(二)初始化

# 初始化节点
node1 = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)# 构建二叉树
node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5

(三)添加与删除节点

# 手动
# 定义新的节点
ins = TreeNode(6)
# 在node1和node2直接插入一个节点ins
node1.left = ins
ins.left = node2
# 删除节点ins
node1.left = node2# 自动
# 定义二叉树
class BinaryTree():# 根节点def __init__(self, root: TreeNode | None):self.root = root# 添加元素def add(self, item: int):if self.root is None:self.root = TreeNode(item)return# 创建队列que: deque[TreeNode] = deque()# 将根节点加入队列que.append(self.root)# 循环，直到插入为止while True:# 队首出队node:TreeNode = que.popleft()# 出队元素左边空，就插左边，不空就继续入队if node.left is None:node.left = TreeNode(item)returnelse:que.append(node.left)# 队元素右边空，就插右边，不空就继续入队if node.right is None:node.right = TreeNode(item)returnelse:que.append(node.right)

(四)将列表反序列化为二叉树

# 通过递归将列表反序列为二叉树
def list_to_tree_dfs(arr: list[int], i: int) -> TreeNode | None:# 如果索引超出数组长度，或者对应的元素为 None ，则返回 Noneif i < 0 or i >= len(arr) or arr[i] is None:return None# 构建当前节点root = TreeNode(arr[i])# 递归构建左子树root.left = list_to_tree_dfs(arr, 2 * i + 1)# 递归构建右子树root.right = list_to_tree_dfs(arr, 2 * i + 2)return root# 输入最初始的值，开始对列表反序列化，成为二叉树
def list_to_tree(arr: list[int]) -> TreeNode | None:return list_to_tree_dfs(arr, 0)

4、常见的二叉树类型

完美二叉树–满二叉树

所有层的节点都被完全的填满，叶节点的度为0，其他的节点度都是2，如果当前树的高度为h，则节点的总数为2**(h+1) - 1，呈现指数级增长。

完全二叉树

只有最底层的节点没有被填满，且最底层的节点尽量往左填充。

完满二叉树

除了叶子节点外，其他的所有结点都有两个子节点。

平衡二叉树

任意结点的左子树和右子树高度差的绝对值不超过1

5、二叉树退化

完美二叉树是所有的节点都被填满，这是一种理想状态下的情况。现在我们假设所有的节点都偏向左边或者偏向右边，二叉树就会退化为链表，因为此时完全没有分治的思想体现，一个元素只指向一个子节点，所有的操作都变为线性，时间复杂度退化至O(n)

二、遍历方式

1、层序遍历–广度优先搜索BFS

概述

从顶部到底部逐层遍历二叉树，并是在每一层按照从左到右的顺序访问节点。

实现

# 借助队列的思想来实现，队列遵从先进先出，而广度优先搜索遵循一层一层推进，所以两者背后的思想是一致的。
from collections import dequedef level_order(root: TreeNode | None):# 初始化队列queue: deque[TreeNode] = deque()queue.append(root)# 初始化列表，用来保存结果res = []while queue:# 队列出列node: TreeNode = queue.popleft()# 保存节点值res.append(node.val)# 如果存在左子节点，就入队if node.left is not None:queue.append(node.left)# 如果存在右子节点，就入队if node.right is not None:queue.append(node.right)return res

2、前序遍历–深度优先搜索DFS

概述

绕着整棵二叉树的外围走一圈，从根节点到左子树最后到右子树。

实现

# 前序遍历
def pre_order(root: TreeNode | None):# 终止条件if root is None:return# 访问优先级：根节点 -> 左子树 -> 右子树res.append(root.val)pre_order(root=root.left)pre_order(root=root.right)

3、中序遍历–深度优先搜索DFS

概述

绕着整棵二叉树的外围走一圈，从左子树到根节点最后到右子树。

实现

# 中序遍历
def in_order(root: TreeNode | None):# 终止条件if root is None:return# 访问优先级：左子树 -> 根节点 -> 右子树in_order(root=root.left)res.append(root.val)in_order(root=root.right)

4、后序遍历–深度优先搜索DFS

概述

绕着整棵二叉树的外围走一圈，从左子树到右子树最后到根节点。

实现

# 后续遍历
def post_order(root: TreeNode | None):# 终止条件if root is None:return# 访问优先级：左子树 -> 右子树 -> 根节点post_order(root=root.left)post_order(root=root.right)res.append(root.val)

三、二叉树数组表示

上述我们都是用链表去实现的二叉树，下面我们尝试用数组去表示二叉树。我们先从最简单的完美二叉树开始表示。

完美二叉树

从层序遍历可以看的出来，某个节点的索引为i，则该节点的左子节点索引为2i + 1，右子节点索引为2i + 2，而这两个公式的角色就相当于是链表的节点引用。

然而完美二叉树属于一个特殊的案例，在实际的开发中，二叉树通常存在许多的None值，而层序遍历的时候是对这些值做了排除的，所以根据上面的公式就没办法判断具体节点的位置了。为了解决这个问题，我们需要手动的在缺少的位置填上None，这样就可以利用上面的公式写出正确的下标了。

二叉树

在层序遍历时，为所有缺少的填上None，这样处理完后，层序遍历得到的数组就可以唯一表示二叉树了。

例如

# 数组表示二叉树
class ArrayBinaryTree:# 创建数组来承载二叉树def __init__(self, arr: list[int | None]):self._tree = list(arr)# 规定列表的大小def size(self):return len(self._tree)# 索引为i的节点值def val(self, i: int) -> int | None:# 若索引越界，则返回 None ，代表空位if i < 0 or i >= self.size():return Nonereturn self._tree[i]# 左子节点的索引def left(self, i: int) -> int | None:return 2 * i + 1# 右子节点的索引def right(self, i: int) -> int | None:return 2 * i + 2# 父节点索引def parent(self, i: int) -> int | None:return (i - 1) // 2# 层序遍历def level_order(self) -> list[int]:self.res = []# 直接遍历数组for i in range(self.size()):if self.val(i) is not None:self.res.append(self.val(i))return self.res# 深度优先遍历def dfs(self, i: int, order: str):# 判空if self.val(i) is None:return# 前序遍历if order == "pre":self.res.append(self.val(i))self.dfs(self.left(i), order)# 中序遍历if order == "in":self.res.append(self.val(i))self.dfs(self.right(i), order)# 后序遍历if order == "post":self.res.append(self.val(i))# 前序遍历def pre_order(self) -> list[int]:self.res = []self.dfs(0, order="pre")return self.res# 中序遍历def in_order(self) -> list[int]:self.res = []self.dfs(0, order="in")return self.res# 后序遍历def post_order(self) -> list[int]:self.res = []self.dfs(0, order="post")return self.res

对比链表

数组访问和遍历的速度要快于链表

因为自带索引，不需要指针指向下一个空间，所以更省空间

可以通过索引访问随机节点

但是由于数组存储需要连续空间，所以储存的树不可能过大

增删节点相较链表较慢

当二叉树缺少元素过多，会导致None值很多，回影响效率

四、一些基本操作

标准的二叉树存储数据的思想和二分查找一样，比目标值小的在左子树，比目标值大的在右子树，每次都可以排除一般的情况，大大提高了查找效率。

1、查找节点

规则

• val < target，说明目标节点在 cur 的右子树中，因此执行 cur = cur.right

• val > target，说明目标节点在 cur 的左子树中，因此执行 cur = cur.left

• val = target，说明找到目标节点，跳出循环并返回该节点

例如

# 寻找节点
def search(self, num: int) -> TreeNode | None:# 要找的节点cur = self._root# 循环查找，越过叶节点后跳出while cur is not None:# 目标节点在 cur 的右子树中if cur.val < num:cur = cur.right# 目标节点在 cur 的左子树中elif cur.val > num:cur = cur.left# 找到目标节点，跳出循环else:breakreturn cur

2、插入节点

与查找类似，从根节点出发，根据当前节点值和num的大小关系找到对应的叶节点位置，然后在该节点插入目标元素。

规则

二叉搜索树不允许有重复元素存在，否则会导致位置不确定，当待插入的元素在树内已经存在，就不执行，直接返回。

例如

# 插入元素
def insert(self, num: int):# 若树为空，则初始化根节点if self._root is None:self._root = TreeNode(num)return# 循环查找，越过叶节点后跳出cur, pre = self._root, Nonewhile cur is not None:# 找到重复节点，直接返回if cur.val == num:returnpre = cur# 插入位置在 cur 的右子树中if cur.val < num:cur = cur.right# 插入位置在 cur 的左子树中else:cur = cur.left# 插入节点node = TreeNode(num)if pre.val < num:pre.right = nodeelse:pre.left = node

3、删除节点

删除节点这个操作比较特殊，因为我们在删除节点的同时，需要保证删除后二叉搜索树的规则还遵守，也就是 左子树.value < 根节点.value < 右子树.value

代码

# 删除节点
def remove(self, num: int):# 若树为空，直接提前返回if self._root is None:return# 循环查找，越过叶节点后跳出cur, pre = self._root, Nonewhile cur is not None:# 找到待删除节点，跳出循环if cur.val == num:breakpre = cur# 待删除节点在 cur 的右子树中if cur.val < num:cur = cur.right# 待删除节点在 cur 的左子树中else:cur = cur.left# 若无待删除节点，则直接返回if cur is None:return# 子节点数量 = 0 or 1if cur.left is None or cur.right is None:# 当子节点数量 = 0 / 1 时， child = null / 该子节点child = cur.left or cur.right# 删除节点 curif cur != self._root:if pre.left == cur:pre.left = childelse:pre.right = childelse:# 若删除节点为根节点，则重新指定根节点self._root = child# 子节点数量 = 2else:# 获取中序遍历中 cur 的下一个节点tmp: TreeNode = cur.rightwhile tmp.left is not None:tmp = tmp.left# 递归删除节点 tmpself.remove(tmp.val)# 用 tmp 覆盖 curcur.val = tmp.val

4、中序遍历有序

因为中序遍历是从左子树->根节点->右子树，所以当使用中序遍历遍历二叉搜索树的时候，得到的序列是升序的状态。

例如

# 中序遍历
def in_order(root: TreeNode | None):# 终止条件if root is None:return# 访问优先级：左子树 -> 根节点 -> 右子树in_order(root=root.left)res.append(root.val)in_order(root=root.right)

五、AVL树

1、概述

介绍

既是二叉搜索树也是平衡二叉树。

基本参数

class TreeNode:"""AVL 树节点类"""def __init__(self, val: int):# 节点值self.val: int = val     # 节点高度self.height: int = 0    # 左子节点引用self.left: TreeNode | None = None   # 右子节点引用self.right: TreeNode | None = None  

在数据操作过程中，树的高度会发生改变，因此我们还需要两个函数分别来获取和更新节点的高度值。

获取节点高度

def height(self, node: TreeNode | None) -> int:# 如果不是空的节点就赋值if node is not None:return node.height# 空节点高度-1return -1def update_height(self, node: TreeNode | None):# 节点高度为最高子树的高度+1node.height = max(self.height(node.left), self.height(node.right)) + 1

获取节点平衡因子

节点平衡因子为左子树高度减去右子树高度，同时空节点的平衡因子为0.

def balance_factor(self, node: TreeNode | None) -> int:# 空节点平衡因子为0if node is None:return 0# 节点平衡因子 = 左子树高度 - 右子树高度return self.height(node.left) - self.height(node.right)

2、AVL旋转

我们将平衡因子绝对值大于1的节点称为失衡节点，根据节点失衡的情况，我们会将旋转分为四种：右旋，左旋，先右旋再左旋，先左旋再右旋。

(一)、右旋

我们将失衡节点设置为node，它的左子节点记为child，如果child有右子节点，则设置为grandchild节点。以child为原点，将node向右旋转，child代替之前node的位置。

def right_rotate(self, node: TreeNode | None) -> TreeNode | None:# 定义子节点和孙子节点child = node.leftgrand_child = child.right# 以child为原点，将node向右旋转child.right = nodenode.left = grand_child# 更新节点高度self.update_height(node)self.update_height(child)# 返回旋转后子树的根节点return child

(二)、左旋

我们将失衡节点设置为node，它的右子节点记为child，如果child有左子节点，则设置为grandchild节点。以child为原点，将node向左旋转，child代替之前node的位置。

def left_rotate(self, node: TreeNode | None) -> TreeNode | None:# 定义子节点和孙子节点child = node.rightgrand_child = child.left# 以child为原点，将node向左旋转child.left = nodenode.right = grand_child# 更新节点高度self.update_height(node)self.update_height(child)# 返回旋转后子树的根节点return child

(三)、先右旋再左旋

先执行右旋代码再执行左旋代码。

(四)、先左旋再右旋

先执行左旋代码再执行右旋代码。

(五)、判断用什么旋转

失衡节点的平衡因子 > 1(左偏树) 子节点的平衡因子 >= 0 右旋

失衡节点的平衡因子 > 1(左偏树) 子节点的平衡因子 < 0 先左旋再右旋

失衡节点的平衡因子 < -1(右偏树) 子节点的平衡因子 <= 0 左旋

失衡节点的平衡因子 < -1(右偏树) 子节点的平衡因子 > 0 先右旋再左旋

def rotate(self, node: TreeNode | None) -> TreeNode | None:balance_factor = self.balance_factor(node)# 左偏树if balance_factor > 1:# 需要右旋if self.balance_factor(node.left) >= 0:return self.right_rotate(node)# 需要左旋再右旋else:node.left = self.left_rotate(node.left)return self.right_rotate(node)# 右偏树elif balance_factor < -1:# 左旋if self.balance_factor(node.right) <= 0:return self.left_rotate(node)# 先右旋再左旋else:node.right = self.right_rotate(node.right)return self.left_rotate(node)return node

(六)、常用操作

(1)、插入节点

输入目标值，根据值的大小寻找插入位置，找到位置后插入目标值，此时二叉树可能不满足AVL树的条件，需要更新节点高度，再根据节点高度去恢复树的平衡。

def insert(self, val):self._root = self.insert_helper(self._root, val)def insert_helper(self, node:TreeNode | None, val: int) -> TreeNode:# 找到位置了，插入目标值if node is None:return TreeNode(val)# 如果插入值小于当前节点，则和左节点比较if val < node.val:node.left = self.insert_helper(node.left, val)# 如果插入值大于当前节点，则和右节点比较elif val > node.val:node.right = self.insert_helper(node.right, val)# 二叉树不允许有重复值，直接返回else:return node# 更新节点高度self.update_height(node)# 恢复子树平衡return self.rotate(node)

(2)、删除节点

输入目标值，查找目标值当前位置，当找到后分两种情况：左右子节点都存在，至多有一个叶子节点。当没有子节点时，直接删除目标节点；当有一个子节点时，直接用子节点替换目标节点；当有两个子节点时，取右子节点替换当前节点。

def remove(self, val):self._root = self.remove_helper(self._root, val)def remove_helper(self, node: TreeNode | None, val: int) -> TreeNode | None:# 判空if node is None:return None# 目标值小于当前节点的值，则和左子节点比较if val < node.val:node.left = self.remove_helper(node.left, val)# 目标值小于当前节点的值，则和右子节点比较elif val > node.val:node.right = self.remove_helper(node.right, val)# 找到目标值else:# 只有左节点或者右节点或者两个都没有if node.left is None or node.right is None:# 设置child等于子节点  顺序 左子节点->右子节点->空child = node.left or node.right# 如果没有子节点，直接删除if child is None:return None# 有一个子节点则用子节点替换目标节点else:node = child# 两个节点都存在else:# 记录右节点tmp = node.right# 找右子节点的左子节点while tmp.left is not None:tmp = tmp.leftnode.right = self.remove_helper(node.right, tmp.val)node.val = tmp.val# 更新节点高度self.update_height(node)# 重新平衡二叉树return self.rotate(node)  

(3)、查找元素

与普通查找没有区别，不再过多解释。

# 寻找节点
def search(self, num: int) -> TreeNode | None:# 要找的节点cur = self._root# 循环查找，越过叶节点后跳出while cur is not None:# 目标节点在 cur 的右子树中if cur.val < num:cur = cur.right# 目标节点在 cur 的左子树中elif cur.val > num:cur = cur.left# 找到目标节点，跳出循环else:breakreturn cur

六、红黑树

这哥们写太好了，看这个~

https://blog.csdn.net/cy973071263/article/details/122543826?spm=1001.2014.3001.5506