python二叉排序树怎么构造,二叉排序树的实现源代码

　　树形查询是指借助具有特殊属性的树形数据结构进行关键字搜索。本文涉及的具有特殊结构性质的树包括二叉排序树和平衡二叉树。本文详细介绍了两者的实现代码，可供参考。

　　00-1010前言1。二叉排序树1.1构建二叉排序树1.2二叉排序树的数据结构1.3在二叉排序树中实现方法类：2。平衡二叉排序树2.1二叉平衡排序树的数据结构3。摘要

目录

　　什么是树表查询？

　　借助具有特殊属性的树形数据结构搜索关键字。

　　本文涉及的具有特殊结构特性的树包括：

　　二叉排序树。平衡二叉树。当使用上述树结构存储数据时，它对节点的关系和顺序有特殊的要求，并且得益于这种限制，在查询某个节点时，它会带来性能优势和操作上的方便。

　　树查询是一种动态搜索算法。

　　所谓动态搜索，不仅可以轻松找到目标节点。此外，可以根据需要添加和删除节点，而不会影响树的整体结构或数据的查询。

　　本文将不深入讲解树形数据结构的基本概念，仅从使用角度讲解动态查询。在阅读本文之前，请准备一些树木的基本知识。

前言

　　它是二叉树结构的一个亮子类。

　　要求二叉树的每个节点(叶节点除外)最多有两个子节点。在二叉树的基础上，继续按顺序限制它，它就变成了二叉排序树。

　　二叉排序树的特征：

　　基于二叉树结构，从根节点开始，自上而下，每个父节点的值大于左子节点的值(如果有左子节点)，小于右子节点的值(如果有右子节点)。满足这一特征要求的树称为二叉排序树。

1. 二叉排序树

　　例如，序列nums=[5，12，4，45，32，8，10，50，32，3]。通过下面的过程，将每个数字映射到二叉排序树的节点。

　　1.如果树是空的，取第一个数字作为根节点。如下所示，数字5是根节点。

　　2.如果根节点已经存在，将数字与根节点进行比较。如果小于根节点，则为根节点的左子节点，如果大于根节点，则为根节点的右子节点。如果数字4插在左边，数字12插在右边。

　　3.序列中的下列数字根据相同的规则被插入不同的子位置。

　　原始序列中的数字是无序的。根据二叉排序树的插入算法，最终可以得到一个排序树结构。通过按中间顺序遍历这棵树，我们可以得到一个从小到大的递增有序序列。

　　看二叉排序树，搜索关键词的时候，应该接近二分搜索法算法的时候了。

　　这里有一个需要注意的地方。

　　当原序列中的数字顺序不同时，二叉排序树的结构也会不同。它将影响搜索算法的性能。

1.1 构建一棵二叉排序树

　　现在用OOP设计来描述二叉排序树的数据结构。

　　首先，设计一个结点类来描述节点本身的信息。

　　二叉排序树的节点类

　　类TreeNode():

　　def __init__(self，value):

　　#节点上的值

　　自我价值=价值

　　#左侧节点

　　self.l_child=无

　　#右节点

　　self.r_child=None

　　节点中有3个属性：

　　值：节点的附加数据信息。L_child:左边的子节点，初始值为

　　de>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->
　　

　　无论删除哪一个结点，其二叉排序树的中序遍历结果都是有序的，很好地印证了删除算法的正确性。

2. 平衡二叉排序树

　　二叉排序树中进行查找时，其时间复杂度理论上接近二分算法的时间复杂度，其查找时间与树的深度有关。但是，这里有一个问题，前面讨论过，如果数列中的数字顺序不一样时，所构建出来的二叉排序树的深度会有差异性，对最后评估时间性能也会有影响。

　　如有数列[36,45,67,28,20,40]构建的二叉排序树如下图：

　　基于上面的树结构，查询任何一个结点的次数不会超过3次。

　　稍调整一下数列中数字的顺序[20,28,36,40,45,67]，由此构建出来的树结构会出现一边倒的现象，也增加了树的深度。

　　此棵树的深度为6，最多查询次数是6次。在二叉排序树中，减少查找次数的最好办法，就是尽可能维护树左右子树之间的对称性，也就让其有平衡性。

　　所谓平衡二叉排序树，顾名思义，基于二叉排序树的基础之上，维护任一结点的左子树和右子树之间的深度之差不超过1。把二叉树上任一结点的左子树深度减去右子树深度的值称为该结点的平衡因子。

　　平衡因子只可能是:

• 0：左、右子树深度一样。
• 1：左子树深度大于右子树。
• -1：左子树深度小于右子树。

　　如下图，就是平衡二叉排序树，根结点的2个子树深度相差为0， 结点28的左、右子树深度为 1，结点45的左右子树深度相差为0。

　　平衡二叉排序树相比较于二叉排序树，其API多了保持平衡的算法。

2.1 二叉平衡排序树的数据结构

　　结点类：

　　结点类
　　class TreeNode:
　　 def __init__(self,value):
　　 self.value=value
　　 self.l_child=None
　　 self.r_child=None
　　 self.balance=0
　　

　　结点类中有4个属性：

• value：结点上附加的值。
• l_child：左子结点。
• r_child：右子结点。
• balance：平衡因子，默认平衡因子为0。

　　二叉平衡排序树类：

　　树类
　　class Tree:
　　 def __init__(self, value):
　　 self.root = None
　　 LL型调整
　　 def ll_rotate(self, node):
　　 pass
　　 RR 型调整
　　 def rr_rotate(self, node):
　　 pass
　　 LR型调整
　　 def lr_rotate(self, node):
　　 pass
　　 RL型调整
　　 def rl_rotate(self, node):
　　 pass
　　 插入新结点
　　 def insert(self, value):
　　 pass
　　 中序遍历
　　 def inorder_traversal(self, root):
　　 pass
　　 def is_empty(self):
　　 pass
　　

　　在插入或删除结点时，如果导致树结构发生了不平衡性，则需要调整让其达到平衡。这里的方案可以有4种。

　　LL型调整（顺时针）：左边不平衡时，向右边旋转。

　　如上图，现在根结点36的平衡因子为1。如果现插入值为18结点，显然要作为结点20的左子结点，才符合二叉排序树的有序性。但是破坏了根结点的平衡性。根结点的左子树深度变成3，右子树深度为1，平衡被打破，结点36的平衡因子变成了2。

　　这里可以使用顺时针旋转方式，让其继续保持平衡，旋转流程：

• 让结点28成为新根结点，结点36成为结点28的左子结点。
• 结点29成为结点36的新左子结点。

　　旋转后，树结构即满足了有序性，也满足了平衡性。

　　LL旋转算法具体实现：

　　 LL型调整
　　 顺时针对调整
　　 def ll_rotate(self, p_root):
　　 # 原父结点的左子结点成为新父结点
　　 new_p_root = p_root.l_child
　　 # 新父结点的右子结点成为原父结点的左子结点
　　 p_root.l_child = new_p_root.r_child
　　 # 原父结点成为新父结点的右子结点
　　 new_p_root.r_child = p_root
　　 # 重置平衡因子
　　 p_root.balance = 0
　　 new_p_root.balance = 0
　　 return new_p_root
　　

　　RR 型调整(逆时针旋转)：RR旋转和LL旋转的算法差不多，只是当右边不平衡时，向左边旋转。

　　如下图所示，结点50插入后，树的平衡性被打破。

　　这里使用左旋转（逆时针）方案。结点36成为结点45的左子结点，结点45原来的左子结点成为结点36的右子结点。

　　向逆时针旋转后，结点45的平衡因子为0，结点36的平衡因子为0，结点48的平衡因子为-1。树的有序性和平衡性得到保持。

　　RR旋转算法具体实现：

　　 RR 型调整
　　 def rr_rotate(self, node):
　　 # 右子结点
　　 new_p_node = p_node.r_child
　　 p_node.r_child = new_p_node.l_child
　　 new_p_node.l_child = p_node
　　 # 重置平衡因子
　　 p_node.balance = 0
　　 new_p_node.balance = 0
　　 return new_p_node
　　

　　LR型调整（先逆后顺）：如下图当插入结点28后，结点36的平衡因子变成2，则可以使用LR旋转算法。

　　以结点29作为新的根结点，结点27以结点29为旋转中心，逆时针旋转。

　　结点36以结点29为旋转中心向顺时针旋转。

　　最后得到的树还是一棵二叉平衡排序树。

　　LR旋转算法实现：

　　 LR型调整
　　 def lr_rotate(self, p_node):
　　 # 左子结点
　　 b = p_node.l_child
　　 new_p_node = b.r_child
　　 p_node.l_child = new_p_node.r_child
　　 b.r_child = new_p_node.l_child
　　 new_p_node.l_child = b
　　 new_p_node.r_child = p_node
　　 if new_p_node.balance == 1:
　　 p_node.balance = -1
　　 b.balance = 0
　　 elif new_p_node.balance == -1:
　　 p_node.balance = 0
　　 b.balance = 1
　　 else:
　　 p_node.balance = 0
　　 b.balance = 0
　　 new_p_node.balance = 0
　　 return new_p_node
　　

　　RL型调整：如下图插入结点39后，整棵树的平衡打破，这时可以使用RL旋转算法进行调整。

　　把结点40设置为新的根结点，结点45以结点40为中心点顺时针旋转，结点36逆时针旋转。

　　RL算法具体实现：

　　 RL型调整
　　 def rl_rotate(self, p_node):
　　 b = p_node.r_child
　　 new_p_node = b.l_child
　　 p_node.r_child = new_p_node.l_child
　　 b.l_child = new_p_node.r_child
　　 new_p_node.l_child = p_node
　　 new_p_node.r_child = b
　　 if new_p_node.balance == 1:
　　 p_node.balance = 0
　　 b.balance = -1
　　 elif new_p_node.balance == -1:
　　 p_node.balance = 1
　　 b.balance = 0
　　 else:
　　 p_node.balance = 0
　　 b.balance = 0
　　 new_p_node.balance = 0
　　 return new_p_node
　　

　　编写完上述算法后，就可以编写插入算法。在插入新结点时，检查是否破坏二叉平衡排序树的的平衡性，否则调用平衡算法。

　　当插入一个结点后，为了保持平衡，需要找到最小不平衡子树。

　　什么是最小不平衡子树？

　　指离插入结点最近，且平衡因子绝对值大于1的结点为根结点构成的子树。

　　 插入新结点
　　 def insert(self, val):
　　 # 新的结点
　　 new_node = TreeNode(val)
　　 if self.root is None:
　　 # 空树
　　 self.root = new_node
　　 return
　　 # 记录离 s 最近的平衡因子不为 0 的结点。
　　 min_b = self.root
　　 # f 指向 a 的父结点
　　 f_node = None
　　 move_node = self.root
　　 f_move_node = None
　　 while move_node is not None:
　　 if move_node.value == new_node.value:
　　 # 结点已经存在
　　 return
　　 if move_node.balance != 0:
　　 # 寻找最小不平衡子树
　　 min_b = move_node
　　 f_node = f_move_node
　　 f_move_node = move_node
　　 if new_node.value < move_node.value:
　　 move_node = move_node.l_child
　　 else:
　　 move_node = move_node.r_child
　　 if new_node.value < f_move_node.value:
　　 f_move_node.l_child = new_node
　　 else:
　　 f_move_node.r_child = new_node
　　 move_node = min_b
　　 # 修改相关结点的平衡因子
　　 while move_node != new_node:
　　 if new_node.value < move_node.value:
　　 move_node.balance += 1
　　 move_node = move_node.l_child
　　 else:
　　 move_node.balance -= 1
　　 move_node = move_node.r_child
　　 if min_b.balance > -2 and min_b.balance < 2:
　　 # 插入结点后没有破坏平衡性
　　 return
　　 if min_b.balance == 2:
　　 b = min_b.l_child
　　 if b.balance == 1:
　　 move_node = self.ll_rotate(min_b)
　　 else:
　　 move_node = self.lr_rotate(min_b)
　　 else:
　　 b = min_b.r_child
　　 if b.balance == 1:
　　 move_node = self.rl_rotate(min_b)
　　 else:
　　 move_node = self.rr_rotate(min_b)
　　 if f_node is None:
　　 self.root = move_node
　　 elif f_node.l_child == min_b:
　　 f_node.l_child = move_node
　　 else:
　　 f_node.r_child = move_node
　　

　　中序遍历：此方法为了验证树结构还是排序的。

　　 中序遍历
　　 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 = [3, 12, 8, 10, 9, 1, 7]
　　 tree = Tree(3)
　　 for i in range(1, len(nums)):
　　 tree.inster(nums[i])
　　 # 中序遍历 
　　 tree.inorder_traversal(tree.root)
　　 输出结果
　　 1->3->7->8->9->10->12->
　　

3. 总结

　　利用二叉排序树的特性，可以实现动态查找。在添加、删除结点之后，理论上查找到某一个结点的时间复杂度与树的结点在树中的深度是相同的。

　　但是，在构建二叉排序树时，因原始数列中数字顺序的不同，则会影响二叉排序树的深度。

　　这里引用二叉平衡排序树，用来保持树的整体结构是平衡，方能保证查询的时间复杂度为Ologn(n为结点的数量)。

　　到此这篇关于Python实现二叉排序树与平衡二叉树的示例代码的文章就介绍到这了,更多相关Python二叉树内容请搜索盛行IT软件开发工作室以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT软件开发工作室！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。