二叉树的基本概念二叉树是一种非线性的数据结构由每个节点一分为二引出两个子节点类似高中生物学到的祖先后代的结构图但二叉树是一个节点只能有两个子节点。基本单元结点。每个节点包含值和两个引用也就是指针分别指向左子节点和右子节点。该节点是这两个节点的父节点称这个节点的左子节点及其后续的分支为左子树同理还有右子树常见术语根节点二叉树顶层的节点没有父节点叶节点二叉树底层的节点没有子树叶节点的两个指针均为None边连接两个结点的线段也就是指针节点所在层从顶部开始数顶层为第一层节点的度子节点的数量可取012节点的深度根节点到该节点需要经历的边数从上往下数节点的高度距离该点最远的叶节点到该节点所经历的边的数量二叉树的高度从根节点到最远的叶节点所经历的边数二叉树的基本操作初始化二叉树基于链式储存的二叉树# 定义二叉树类ClassTreeNode:def__init__(self,val0,leftNone,rightNone):self.valval self.leftleft self.rightright# 初始化n1TreeNode(1)n2TreeNode(2)n3TreeNode(3)n4TreeNode(4)# 构建节点之间的关系n1.leftn2 n1.rightn3 n2.leftn4# 访问某个节点的值左子节点和右子节点n1.val n1.left n1.right插入和删除节点类似于链表插入、删除节点的方法只需要修改指针(left, right)pTreeNode(1)# 在n1,n2之间插入pn1.leftp p.leftn2# 删除节点p,即由p的父节点到子节点跳过pn1.leftn2常见二叉树的类型完美二叉树/满二叉树常见所有的节点都有两个子节点除了叶节点。完全二叉树常见仅允许最底层的节点不完全填满且最底层的节点必须从左至右依次连续填充完满二叉树除了叶叶节点外其余所有节点都有两个子节点平衡二叉树任意节点的左右子树的高度之差的绝对值不超过1二叉搜索树后续有详细内容若左子树不空则左子树上每个子节点的值都小于根节点的值若右子树不空则右子树上每个子节点的值都大于根节点的值左右子树均为二叉搜索树可以记作左子树中所有节点的值 根节点的值 右子树中所有节点的值平衡二叉搜索树是空树或者满足左右两个子树的高度差不超过1并且两个子树分别也是平衡二叉树二叉树的储存方式链式储存链表的储存方式每个节点的地址是不连续的通过左右指针索引顺序储存数组的储存方式用数组储存二叉树二叉树的退化二叉树最“满”的结构就是完美二叉树而它的退化结构每个节点只有一个子节点时就变成链表。完美二叉树可以充分发挥二叉树分治的优势链表则是另一个极端各项操作都变成线性操作时间复杂度为O(n)二叉树的遍历背景二叉树本质上是通过指针遍历逐个访问每个元素。但由于二叉树是非线性的数据结构它的遍历顺序不是只有一条路线更复杂所以需要人为设计主要有以下几个方法。层序遍历从顶部到底部按层遍历二叉树并在每层按从左到右的顺序访问节点也称广度优先遍历/广度优先搜索。代码实现def level_order(root:TreeNode|None) - list[int]: # 通过一个队列储存层序遍历树的结果 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前序、中序、后序遍历都属于深度优先遍历通常通过递归实现。这里前中后其实指的是每个小叉里中间节点root的遍历顺序。前序root, root.left, root.right中序root.left, root, root.right后序root.left, root.right, rootdef pre_order(root:TreeNode | None): if root is None: return res.append(root.val) pre_order(rootroot.left) pre_order(rootroot.right) def mid_order(root: TreeNode | None): if root is None: return mid_order(rootroot.left) res.append(root.val) mid_order(rootroot.right) def pot_order(root:TreeNode | None): if root is None: return pot_order(root root.left) pot_order(root root.right) res.append(root.val)三者递归的区别和特点依靠root is None找到向上递归点关键在于递归到左右子节点X_order(rootroot.left), X_order(rootroot.right)和赋值res.append(root.val)的顺序复杂度层序遍历和深度优先遍历的时间空间复杂度均为O(n)二叉树的数组表示数组表示完美二叉树将所有节点按照层序遍历的顺序存储在一个数组每个父节点和左右两个子节点之间的索引存在固定的公式父节点的索引是i则其左子节点索引为2i1右子节点索引为2i2数组表示任意二叉树还是同样的索引方式但是对于二叉树中某些位置是None的情况显式写出来(占位)为了不破坏2i1,2i2的映射关系。数组表示比较适合完全二叉树None的位置都在数组末尾数组表示的优势连续储存对缓存友好访问和遍历速度快允许随机访问节点不必按树的指针顺序不需要储存指针节省空间数组表示的劣势增删节点效率低不适用于二叉树有大量位置是None的情况空间利用率低数组储存需要连续内存空间所以不适合储存数据量很大的二叉树二叉搜索树 BTS左子树中所有节点的值 根节点的值 右子树中所有节点的值二叉搜索树的操作查找节点通过二分法设目标节点值为num如果当前节点cur.valnum则num在cur的右子树则curcur.right若cur.valnum则num在cur的左子树curcur.left复杂度O(logn)插入节点给定一个二叉搜索树根据“左子树 根节点 右子树”的性质找到插入位置。注意二叉搜索树要求不能有值重复的节点否则将违反其定义。所以如果插入节点的值在树中已存在那就不会插入直接返回。复杂度O(logn)def insert(self, num): if self._root is None: self._root TreeNode(num) return cur, pre self._root, None while cur is not None: if cur.val num: return pre cur if cur.val num: cur cur.right else: cur cur.left if pre.val num: pre.right TreeNode(num) else: pre.left TreeNode(num)删除节点若节点为叶节点则可以直接删除若节点的度为1有一个子节点则删除它后直接用其子节点左或右替换它的位置若节点的度为2有两个子节点这里也包括大于等于2的情况则需要用其右子树的最小节点或其左子树的最大节点进行替换两种都可以def remove(self, num: int): 删除节点 # 若树为空直接提前返回 if self._root is None: return # 循环查找越过叶节点后跳出 cur, pre self._root, None while cur is not None: # 找到待删除节点跳出循环 if cur.val num: break pre cur # 待删除节点在 cur 的右子树中 if cur.val num: cur cur.right # 待删除节点在 cur 的左子树中 else: cur cur.left # 若无待删除节点则直接返回 if cur is None: return # 子节点数量 0 or 1 if cur.left is None or cur.right is None: # 当子节点数量 0 / 1 时 child null / 该子节点 child cur.left or cur.right # 删除节点 cur if cur ! self._root: if pre.left cur: pre.left child else: pre.right child else: # 若删除节点为根节点则重新指定根节点 self._root child # 子节点数量 2这里是用右子树的最小节点也可以改成左子树的最大节点 else: # 获取中序遍历中 cur 的下一个节点 tmp: TreeNode cur.right while tmp.left is not None: tmp tmp.left # 递归删除节点 tmp self.remove(tmp.val) # 用 tmp 覆盖 cur cur.val tmp.val二叉搜索树的中序遍历有序由于二叉树的大小关系其在中序遍历时有一个性质二叉搜索树的中序遍历序列是升序的因此获取有序数据仅需O(n)的时间非常高效。二叉搜索树的效率无序数组插入时直接添加到末尾O(1)删除和查找时候需要先找到待删除和查找的位置所以是O(n)二叉搜索树由于有大小关系所以具有O(logn)的复杂度二叉搜索树的常见应用用作系统中的多级索引实现高效的查找、插入、删除操作。作为某些搜索算法的底层数据结构。用于存储数据流以保持其有序状态。AVL树background搜索二叉树经过多次插入和删除操作后会退化为链表高度不断增加每层节点数却减少导致复杂度会增加至O(n)提出AVL二叉树通过一系列操作确保其在持续添加、删除节点后不会退化仍保持O(logn)的复杂度。既是二叉搜索树也是平衡二叉树平衡二叉树任意节点的左右子树的高度之差的绝对值不超过1。在需要频繁增删查改的操作场景中能始终保持高效的数据操作。
