python实现二分搜索树

在了解二分搜索树之前，我们要先来了解一下二叉树。

1.1 二叉树

二叉树是一种动态的数据结构。他每个节点都可以有两个子节点，成为左孩子节点和右孩子节点。没有一个孩子节点的节点称为叶子节点。每个节点还可以最多有一个父节点。如下图，40为该该二叉树的根节点，35和20分别为40的左孩子和右孩子。60，45，30，10都可被成为叶子节点。

1.1.1 满二叉树与完全二叉树

二叉树根据节点分布的不同可分为满二叉树与完全二叉树。假设一颗二叉树的深度为k，那满二叉树就是该树第k-1层的节点都有两个孩子节点且第k层的节点都为叶子节点，从外形来看就像是一个三角形。而完全二叉树就是去除最后一层的叶子节点后就变成一个满二叉树，且最后层的叶子节点都连续分布在左边。以下为满二叉树与完全二叉树的对比图。

1.2 二分查找树

了解了二叉树后，我们再来看二分查找树。二分查找树也是二叉树，它有二叉树的所有性质。其本身又有自身特殊的性质：

• 二分查找树每个节点的左孩子的值都小于其本身节点的值，每个节点的右孩子的值都大于其本身的值。
• 任意节点的每颗子树也都满足以上的性质

1.2.1 二分查找树的节点建立、插入

二分查找树是通过节点建立的，所以要先建立一个节点类，一个节点的属性有其本身的值，其左孩子、有孩子以及其父节点。代码如下：

from pprint import pformat


class Node:
    def __init__(self, data): 
        self.data = data			#节点的值
        self.left = None			#节点的左孩子
        self.right = None			#节点的右孩子
        self.parent = None			#节点的父节点

    def __repr__(self):				#本方法是为最后打印树所写
        if self.left is None and self.right is None:
            return str(self.data)
        return pformat({"%s" % (self.data): (self.left, self.right)}, indent=1)

接着要定义一个二分查找树类，一个树的自身的属性只有一个根属性。代码如下：

class BST:
    def __init__(self, root=None):
        self.root = root

    def __str__(self):
        return str(self.root)

    def is_empty(self):					#判断树是否为空
        if self.root is None:
            return True
        else:
            return False

二叉树的插入，根据二叉树的定义，左孩子节点的值要小于本身的值，右孩子的值大于本身的值。故先从根节点判断，如果根节点为空，则直接定义插入的节点为根节点；如不为空，则先比较要插入节点的值与根节点的值，如果小于根节点的值，则该值应该位于根节点的左子树。接着判断根节点的左孩子是否为空，如果为空，则直接将要插入的值赋给其左孩子节点；若不为空，则将该左孩子视为上述步骤的根节点，再判断要插入的值与当前节点的值的大小。上述步骤中如果是大于，则步骤中的左孩子变为右孩子。下图为插入的图示：

代码实现：

   def __insert(self, value):
       new_node = Node(value)				#定义新插入的节点
       if self.is_empty():					#判断根节点是否为空
           self.root = new_node
       else:
           parent_node = self.root			#定义一个父亲节点，初始为根节点
           while True:
               if value < parent_node.data:		#判断插入的值与父亲节点的值的大小
                   if parent_node.left is None:	#如果小于，则先判断该父亲节点是否为空，如果为空
                       parent_node.left = new_node	#则将要新插入的节点赋给该父亲节点的左孩子
                       break
                   else:
                       parent_node = parent_node.left	#否则将该父亲节点的左孩子重新定义为父亲节点
               else:	#如果大于，则步骤与小于的步骤类似，将左孩子换成有孩子即可
                   if parent_node.right is None:
                       parent_node.right = new_node
                       break
                   else:
                       parent_node = parent_node.right
           new_node.parent=parent_node	#最后定义插入的节点的父节点为定义的父亲节点
    def insert(self, *args):	#插入时定义一个插入的方法，再调用上述写好的私有方法
        for i in args:
            self.__insert(i)
        return self

1.2.2 二分查找树的查找

由于二分查找树没有索引，故需从根节点来遍历整个树来查找元素。从根节点开始，判断当前节点的值和查找的值是否相等，若不等，则继续向下遍历，而向左边遍历还是向右边遍历，则需要比较当前节点值和查找的值的大小。直至最后值相等或值不存在停止遍历。代码实现如下：

   def search(self, value):
       if self.is_empty():		#判断树是否为空
           raise Exception('空树')
       else:
           node = self.root		#将当前节点node赋值为根节点
           while node and node.data != value:	#判断节点是否为空和是否等于要查找的值
               node = node.left if value < node.data else node.right  #如果查找的值大于当前节点的值，则将当前节点的右孩子赋为当前节点，否则赋为左孩子
           return node  #最后返回node

1.2.3 二次查找树的删除

二分查找树的删除的实现较为繁琐，故我将直接在代码中写注释加以说明：

    def remove(self, value):
        search_node = self.search(value)	#先通过查找函数找到要删除的节点
        if search_node is not None:
            if search_node.left is None and search_node.right is None: #判断要删除的节点的左孩子和右孩子，若都为空
                self.__reassin(search_node, None)   #通过一个reassin方法来实现删除操作，该方法实质上就是一个交换函数，传入要删除的节点和None
            elif search_node.left is None:	#如果只有左孩子为空
                self.__reassin(search_node, search_node.right)	#则方法中传入删除的节点和其右孩子
            elif search_node.right is None: #如果只有右孩子为空
                self.__reassin(search_node, search_node.left)	#则方法中传入删除的节点和其左孩子
            else: 		#如果两个孩子节点都不空
                temp = self.get_max(search_node.left)  #先找到删除的节点的左子树的最大值节点
                self.remove(temp.data)	#接着删除该最大值节点
                search_node.data = temp.data	#最后将要删除的节点的值赋为最大值节点的值，这样就完成了删除操作

    def __reassin(self, node, new_chird):	#该方法就是交换的方法
        if new_chird is not None:		#判断传入的孩子节点是否为空，若不为空
            new_chird.parent = node.parent		#则先将该孩子节点的父节点设为传入的要删除的节点的父节点
        if node.parent is not None:		#判断要删除的节点的父节点是否为空，若不为空
            if self.is_right(node):		#则先判断该删除的节点是否为其父节点的右孩子，若是
                node.parent.right = new_chird	#则直接将其父节点的右孩子赋为传入的孩子节点
            else:
                node.parent.left = new_chird	#若不是右孩子，则将其父节点的左孩子赋为传入的孩子节点
        else:					#如果要删除的节点的父节点为空
            self.root = new_chird	#直接将根节点赋为传入的孩子节点

    def get_max(self, node=None):	#该方法为找到某一节点下的最大值
        if node is None:
            node = self.root
        if not self.is_empty(): 	#判断是否为空，若不空
            while node.right is not None:	#一直遍历右孩子，直到为空
                node = node.right
        return node			#最后返回的就是最大节点

	def is_right(self, node):		#该方法就是判断某一节点是否为其父节点的右孩子
        return node == node.parent.right

本文地址：https://blog.csdn.net/weixin_48753895/article/details/107143465