做百度糯米网站的团队,wordpress 广告传媒,详情页设计理念,浙江小九天建设集团网站二叉树
一、概述
1、介绍
是一种非线性数据结构#xff0c;将数据一分为二#xff0c;代表根与叶的派生关系#xff0c;和链表的结构类似#xff0c;二叉树的基本单元是结点#xff0c;每个节点包括值和左右子节点引用。
每个节点都有两个引用#xff08;类似于双向链…二叉树
一、概述
1、介绍
是一种非线性数据结构将数据一分为二代表根与叶的派生关系和链表的结构类似二叉树的基本单元是结点每个节点包括值和左右子节点引用。
每个节点都有两个引用类似于双向链表分别指向左子节点和右子节点该节点被称为这两个子节点的父节点。当给定一个二叉树的结点时我们将在该节点的左子节点以及其以下结点所形成的树称为左子树同理右子节点的部分被称为右子树。
在二叉树中除了叶节点外其他的所有节点都包含子节点和非空子树。
2、常见术语 根节点 位于二叉树顶层的节点没有父节点 叶节点 没有子节点的节点左右两个指针都指向None 边 连接两个节点的线就是节点引用也就是我们用的指针 层 从树的根部开始递增根的层数为1 度 节点的子节点数量如果是普通的树没有限制如果是二叉树取值范围则被限制在012 二叉树高度 从根节点到最远的叶节点所经过边的数量也可以理解为最下层叶子节点的层数 - 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**(h1) - 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 res2、前序遍历–深度优先搜索DFS 概述 绕着整棵二叉树的外围走一圈从根节点到左子树最后到右子树。 实现 # 前序遍历
def pre_order(root: TreeNode | None):# 终止条件if root is None:return# 访问优先级根节点 - 左子树 - 右子树res.append(root.val)pre_order(rootroot.left)pre_order(rootroot.right)3、中序遍历–深度优先搜索DFS 概述 绕着整棵二叉树的外围走一圈从左子树到根节点最后到右子树。 实现 # 中序遍历
def in_order(root: TreeNode | None):# 终止条件if root is None:return# 访问优先级左子树 - 根节点 - 右子树in_order(rootroot.left)res.append(root.val)in_order(rootroot.right)4、后序遍历–深度优先搜索DFS 概述 绕着整棵二叉树的外围走一圈从左子树到右子树最后到根节点。 实现 # 后续遍历
def post_order(root: TreeNode | None):# 终止条件if root is None:return# 访问优先级左子树 - 右子树 - 根节点post_order(rootroot.left)post_order(rootroot.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, orderpre)return self.res# 中序遍历def in_order(self) - list[int]:self.res []self.dfs(0, orderin)return self.res# 后序遍历def post_order(self) - list[int]:self.res []self.dfs(0, orderpost)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 cur2、插入节点
与查找类似从根节点出发根据当前节点值和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 node3、删除节点
删除节点这个操作比较特殊因为我们在删除节点的同时需要保证删除后二叉搜索树的规则还遵守也就是 左子树.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.val4、中序遍历有序
因为中序遍历是从左子树-根节点-右子树所以当使用中序遍历遍历二叉搜索树的时候得到的序列是升序的状态。 例如 # 中序遍历
def in_order(root: TreeNode | None):# 终止条件if root is None:return# 访问优先级左子树 - 根节点 - 右子树in_order(rootroot.left)res.append(root.val)in_order(rootroot.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?spm1001.2014.3001.5506
