您现在的位置是：网站首页> 编程资料编程资料
Python实现二叉排序树与平衡二叉树的示例代码_python_
2023-05-26
416人已围观
简介 Python实现二叉排序树与平衡二叉树的示例代码_python_
前言
什么是树表查询？
借助具有特殊性质的树数据结构进行关键字查找。
本文所涉及到的特殊结构性质的树包括：
- 二叉排序树。
- 平衡二叉树。
使用上述树结构存储数据时，因其本身对结点之间的关系以及顺序有特殊要求，也得益于这种限制，在查询某一个结点时会带来性能上的优势和操作上的方便。
树表查询属于动态查找算法。
所谓动态查找，不仅仅能很方便查询到目标结点。而且可以根据需要添加、删除结点，而不影响树的整体结构，也不会影响数据的查询。
本文并不会深入讲解树数据结构的基本的概念，仅是站在使用的角度说清楚动态查询。阅读此文之前，请预备一些树的基础知识。
1. 二叉排序树
二叉树是树结构中具有艳明特点的子类。
二叉树要求树的每一个结点（除叶结点）的子结点最多只能有 2 个。在二叉树的基础上，继续对其进行有序限制则变成二叉排序树。
二叉排序树特点：
基于二叉树结构，从根结点开始，从上向下，每一个父结点的值大于左子结点（如果存在左子结点）的值，而小于右子结点（如果存在右子结点）的值。则把符合这种特征要求的树称为二叉排序树。
1.1 构建一棵二叉排序树
如有数列 nums=[5,12,4,45,32,8,10,50,32,3]。通过下面流程，把每一个数字映射到二叉排序树的结点上。
1.如果树为空，把第一个数字作为根结点。如下图，数字 5 作为根结点。
2.如果已经存在根结点，则把数字和根结点比较，小于根结点则作为根结点的左子结点，大于根结点的作为根结点的右子结点。如数字 4 插入到左边，数字 12 插入到右边。
3.数列中后面的数字依据相同法则，分别插入到不同子的位置。
原始数列中的数字是无序的，根据二叉排序树的插入算法，最终可得到一棵有排序性质的树结构。对此棵树进行中序遍历就可得到从小到大的一个递增有序数列。
综观二叉排序树，进行关键字查找时，也应该是接近于二分查找算法的时间度。
这里有一个要注意的地方。
原始数列中的数字顺序不一样时，生成的二叉排序树的结构也会有差异性。对于查找算法的性能会产生影响。
1.2 二叉排序树的数据结构
现在使用OOP设计方案描述二叉排序树的数据结构。
首先，设计一个结点类，用来描述结点本身的信息。
''' 二叉排序树的结点类 ''' class TreeNode(): def __init__(self, value): # 结点上的值 self.value = value # 左结点 self.l_child = None # 右结点 self.r_child = None
结点类中有 3 个属性：
value：结点上附加的数据信息。l_child：左子结点，初始值为None。r_child：右子结点，初始值为None。
二叉排序树类： 用来实现树的增、删、改、查。
''' 二叉排序树类 ''' class BinarySortTree: # 初始化树 def __init__(self, value=None): pass ''' 在整棵树上查询是否存在给定的关键字 ''' def find(self, key): pass ''' 使用递归进行查询 ''' def find_dg(self, root, key): pass ''' 插入新结点 ''' def insert(self, value): pass ''' 中序遍历 ''' def inorder_traversal(self): pass ''' 删除结点 ''' def delete(self, key): pass ''' 检查是不是空树 ''' def is_empty(self): return self.root == None
二叉排序树中可以有更多方法，本文只关注与查找主题有关的方法。
1.3 实现二叉排序树类中的方法：
__init__ 初始化方法：
# 初始化树 def __init__(self, value=None): self.root = None if value is not None: root_node = TreeNode(value) self.root = root_node
在初始化树对象时，如果指定了数据信息，则创建有唯一结点的树，否则创建一个空树。
关键字查询方法：查询给定的关键字在二叉排序树结构中是否存在。
查询流程：
- 把给定的关键字和根结点相比较。如果相等，则返回查找成功，结束查询.
- 如果根结点的值大于关键字，则继续进入根结点的左子树中开始查找。
- 如果根结点的值小于关键字，则进入根结点的右子树中开始查找。
- 如果没有查询到关键字，则返回最后访问过的结点和查询不成功信息。
关键字查询的本质是二分思想，以当前结点为分界线，然后向左或向右进行分枝查找。
非递归实现查询方法：
''' 在整棵树上查询是否存在给定的关键字 key: 给定的关键字 ''' def find(self, key): # 从根结点开始查找。 move_node = self.root # 用来保存最后访问过的结点 last_node = None while move_node is not None: # 保存当前结点 last_node = move_node # 把关键字和当前结点相比较 if self.root.value == key: # 出口一：成功查找 return move_node elif move_node.value > key: # 在左结点查找 move_node = move_node.l_child else: # 在右结点中查找 move_node = move_node.r_child # 出口二：如果没有查询到，则返回最后访问过的结点及None（None 表示没查询到） return last_node, None
注意：当没有查询到时，返回的值有 2 个，最后访问的结点和没有查询到的信息。
为什么要返回最后一次访问过的结点？
反过来想想，本来应该在这个地方找到，但是没有，如果改成插入操作，就应该插入到此位置。
基于递归实现的查找：
''' 使用递归进行查询 ''' def find_dg(self, root, key): # 结点不存在 if root is None: return None # 相等 if root.value == key: return root if root.value > key: return self.find_dg(root.l_child, key) else: return self.find_dg(root.r_child, key)
再看看如何把数字插入到二叉排序树中，利用二叉排序树进行查找的前提条件就是要把数字映射到二叉排序树的结点上。
插入结点的流程：
- 当需要插入某一个结点时，先搜索是否已经存在于树结构中。
- 如果没有，则获取到查询时访问过的最一个结点，并和此结点比较大小。
- 如果比此结点大，则插入最后访问过结点的右子树位置。
- 如果比此结点小，则插入最后访问过结点的左子树位置。
insert 方法的实现：
''' 插入新结点 ''' def insert(self, value): # 查询是否存在此结点 res = self.find(value) if type(res) != TreeNode: # 没找到，获取查询时最后访问过的结点 last_node = res[0] # 创建新结点 new_node = TreeNode(value) # 最后访问的结点是根结点 if last_node is None: self.root = new_node if value > last_node.value: last_node.r_child = new_node else: last_node.l_child = new_node
怎么检查插入的结点是符合二叉树特征？
再看一下前面根据插入原则手工绘制的插入演示图：
上图有 4 个子结点，写几行代码测试一下，看从根结点到叶子结点的顺序是否正确。
测试插入方法：
if __name__ == "__main__": nums = [5, 12, 4, 45, 32, 8, 10, 50, 32, 3] tree = BinarySortTree(5) for i in range(1, len(nums)): tree.insert(nums[i]) print("测试根5 -> 左4 ->左3:") tmp_node = tree.root while tmp_node != None: print(tmp_node.value, end=" ->") tmp_node = tmp_node.l_child print("\n测试根5 -> 右12 ->右45->右50：") tmp_node = tree.root while tmp_node != None: print(tmp_node.value, end=" ->") tmp_node = tmp_node.r_child ''' 输出结果： 测试根5 -> 左4 ->左3: 5 ->4 ->3 -> 测试根5 -> 右12 ->右45->右50： 5 ->12 ->45 ->50 -> ''' 查看结果，可以初步判断插入的数据是符合二叉排序树特征的。当然，更科学的方式是写一个遍历方法。树的遍历方式有 3 种：
- 前序：根，左，右。
- 中序：左，根，右。
- 后序。左，右，根。
对二叉排序树进行中序遍历，理论上输出的数字应该是有序的。这里写一个中序遍历，查看输出的结点是不是有序的，从而验证查询和插入方法的正确性。
使用递归实现中序遍历：
''' 中序遍历 ''' def inorder_traversal(self, root): if root is None: return self.inorder_traversal(root.l_child) print(root.value,end="->") self.inorder_traversal(root.r_child)
测试插入的顺序：
if __name__ == "__main__": nums = [5, 12, 4, 45, 32, 8, 10, 50, 32, 3] tree = BinarySortTree(5) # res = tree.find(51) for i in range(1, len(nums)): tree.insert(nums[i]) tree.inorder_traversal(tree.root) ''' 输出结果 3->4->5->8->10->12->32->45->50-> '''
二叉排序树很有特色的数据结构，利用其存储特性，可以很方便地进行查找、排序。并且随时可添加、删除结点，而不会影响排序和查找操作。基于树表的查询操作称为动态查找。
二叉排序树中如何删除结点
从二叉树中删除结点，需要保证整棵二叉排序树的有序性依然存在。删除操作比插入操作要复杂，下面分别讨论。
- 如果要删除的结点是叶子结点。
只需要把要删除结点的父结点的左结点或右结点的引用值设置为空就可以了。
- 删除的结点只有一个右子结点。如下图删除结点
8。
因为结点8没有左子树，在删除之后，只需要把它的右子结点替换删除结点就可以了。
删除的结点即存在左子结点，如下图删除值为 25 的结点。
一种方案是：找到结点 25 的左子树中的最大值，即结点 20（该结点的特点是可能会存在左子结点，但一定不会有右子结点）。用此结点替换结点25 便可。
为什么要这么做？
道理很简单，既然是左子树中的最大值，替换删除结点后，整个二叉排序树的特性可以继续保持。
如果结点 20 存在左子结点，则把它的左子结点作为结点18的右子结点。
另一种方案：同样找到结点25中左子树中的最大值结点 20，然后把结点 25 的右子树作为结点 20 的右子树。
再把结点 25 的左子树移到 25 位置。
这种方案会让树增加树的深度。所以，建议使用第一种方案。
删除方法的实现：
''' 删除结点 key 为要要删除的结点 ''' def delete(self, key): # 从根结点开始查找，move_node 为搜索指针 move_node = self.root # 要删除的结点的父结点,因为根结点没有父结点，初始值为 None parent_node = None # 结点存在且没有匹配上要找的关键字 while move_node is not None and move_node.value != key: # 保证当前结点 parent_node = move_node if move_node.value > key: # 在左子树中继续查找 move_node = move_node.l_child else: # 在右子树中继续查找 move_node = move_node.r_child # 如果不存在 if move_node is None: return -1 # 检查要删除的结点是否存在左子结点 if move_node.l_child is None: if parent_node is None: # 如果要删除的结点是根结点 self.root = move_node.r_child elif parent_node.l_child == move_node: # 删除结点的右结点作为父结点的左结点 parent_node.l_child = move_node.r_child elif parent_node.r_child == move_node: parent_node.r_child = move_node.r_child return 1 else: # 如果删除的结点存在左子结点,则在左子树中查找最大值 s = move_node.l_child q = move_node while s.r_child is not None: q = s s = s.r_child if q == move_node: move_node.l_child = s.l_child else: q.r_child = s.l_child move_node.value = s.value q.r_child = None return 1
测试删除后的二叉树是否依然维持其有序性。
if __name__ == "__main__": nums = [5, 12, 4, 45, 32, 8, 10, 50, 32, 3] tree = BinarySortTree(5) # res = tree.find(51) for i in range(1, len(nums)): tree.insert(nums[i]) tree.delete(12) tree.inorder_traversal(tree.root) ''' 输出结果 3->4->5->8->10->32->45->50-> '''
无论删除哪一个结点，其二叉排序树的中序遍历结果都是有序的，很
相关内容
- python中class类与方法的用法实例详解_python_
- python如何利用matplotlib绘制并列双柱状图并标注数值_python_
- 使用python+Pyqt5实现串口调试助手_python_
- python数据处理之Pandas类型转换的实现_python_
- Python实现将多张图片合成视频并加入背景音乐_python_
- Python+FuzzyWuzzy实现模糊匹配的示例详解_python_
- 详解如何基于Pyecharts绘制常见的直角坐标系图表_python_
- 如何利用Pandas删除某列指定值所在的行_python_
- PyTorch模型保存与加载实例详解_python_
- Python实现视频画质增强的示例代码_python_
