python实现二叉搜索树

深碍√TFBOYSˉ_ 2022-05-30 08:51 246阅读 0赞 
  1. class Node(object):
  2.     def __init__(self,data=None):
  3.         self._left=None #左节点
  4.         self._right=None #右节点
  5.         self._data=data
  6.     #一系列get set方法
  7.     def set_left(self,node):
  8.         self._left=node
  9.     def set_right(self,node):
  10.         self._right=node
  11.     def get_left(self):
  12.         return self._left
  13.     def get_right(self):
  14.         return self._right
  15.     def set_data(self,data):
  16.         self._data=data
  17.     def get_data(self):
  18.         return self._data
  20. class Binary_tree(object):
  21.     def __init__(self,root):#这个根要是Node的对象
  22.         self.__in_order=[]#中序遍历的列表
  23.         self.__pre_order=[]#前序遍历的列表
  24.         self.__post_order=[]#后序遍历的列表
  25.         self.__root=root
  26.     #下面带有help的都是私有函数
  27.     def __preorder_help(self,root):#利用递归进行前序遍历
  28.         if root:
  29.             self.__pre_order.append(root.get_data())
  30.             self.__preorder_help(root.get_left())
  31.             self.__preorder_help(root.get_right())
  32.         return self.__pre_order
  33.     def __inorder_help(self,root):#利用递归进行中序遍历
  34.         if root:
  35.             self.__inorder_help(root.get_left())
  36.             self.__in_order.append(root.get_data())
  37.             self.__inorder_help(root.get_right())
  38.         return self.__in_order
  39.     def __postorder_help(self,root):#利用递归进行后序遍历
  40.         if root:
  41.             self.__postorder_help(root.get_left())
  42.             self.__postorder_help(root.get_right())
  43.             self.__post_order.append(root.get_data)
  44.         return self.__post_order
  45.     def preorder(self):
  46.         return self.__preorder_help(self.__root)
  47.     def inorder(self):
  48.         return self.__inorder_help(self.__root)
  49.     def postorder(self):
  50.         return self.__postorder_help(self.__root)
  51. #貌似纯二叉树没什么卵用，就不写示列了。
  52. #二叉搜索树就不一样了，下面会有示列。
  54. class BSTNode(Node):
  55.     def __init__(self,data=None):
  56.         Node.__init__(self,data=data)#这继承不像c++,不会默认调用父类的构造函数，需要像这样写
  57.         self.__in_order=[]#中序遍历的列表
  58.         self.__pre_order=[]#前序遍历的列表
  59.         self.__post_order=[]#后序遍历的列表
  60.     def insert(self,data):
  61.         if data<self._data:#比此数据小就插左边，否则就插右边
  62.             if self._left:
  63.                 return self._left.insert(data)
  64.             else:
  65.                 self._left=BSTNode(data)
  66.         else:
  67.             if self._right:
  68.                 return self._right.insert(data)
  69.             else:
  70.                 self._right=BSTNode(data)
  71.     @staticmethod#静态方法
  72.     def min_val_bst_node(bst_node):
  73.         current=bst_node
  74.         while current._left is not None:
  75.             current=current._left
  76.         return current
  77.     def delete(self,data):
  78.         if self is None:#发现没有这个数据时做以下处理
  79.             return None
  80.         if data<self._data:#要删的数据比此数据小，就从左子树删起
  81.             self._left=self._left.delete(data)
  82.         elif data>self.get_data():#要删的数据比此数据大，从右子树删起
  83.             self._right=self._right.delete(data)
  84.         else:#要删的就是此数据
  85.             if self._left is None:#当左子树为空时，返回右子树，那么这个数据就删掉了，返回上层的时候，它的父节点与右子树相连
  86.                 temp=self._right
  87.                 return temp
  88.             elif self._right is None:#当右子树为空，与上面相似
  89.                 temp=self._left
  90.                 return temp
  91.         #如果左右子树都不为空时，把右子树的最左节点（最小结点）和此结点的数据替换
  92.         temp = self.min_val_bst_node(self._right)
  93.         self._data=temp._data
  94.         self._right=self._right.delete(temp._data)
  95.         return self
  96.     def find(self,data):
  97.         if data==self.get_data():
  98.             return True
  99.         elif data<self.get_data():#小就往左子树找，大就往右子树找
  100.             if self._left:
  101.                 return self._left.find(data)
  102.             else:
  103.                 return False
  104.         else:
  105.             if self.get_right():
  106.                 return self._right.find(data)
  107.             else:
  108.                 return False
  109.     #下面这些函数与纯二叉树的类似
  110.     def inorder(self,root):
  111.         if root:
  112.             self.inorder(root._left)
  113.             self.__in_order.append(root._data)
  114.             self.inorder(root._right)
  115.         return self.__in_order
  117.     def preorder(self,root):
  118.         if root:
  119.             self.__pre_order.append(root._data)
  120.             self.preorder(root._left)
  121.             self.preorder(root._right)
  122.         return self.__pre_order
  123.     def postorder(self,root):
  124.         if root:
  125.             self.postorder(root._left)
  126.             self.postorder(root._right)
  127.             self.__post_order.append(root._data)
  128.         return self.__post_order
  130. class BST(object):
  131.     def __init__(self):
  132.         self.__root=None
  133.     def insert(self,data):
  134.         if self.__root:
  135.             self.__root.insert(data)
  136.         else:
  137.             self.__root = BSTNode(data)
  139.     def delete(self,data):
  140.         if self.__root:
  141.             return self.__root.delete(data)
  143.     def find(self,data):
  144.         if self.__root:
  145.             return self.__root.find(data)
  146.         else:
  147.             return False
  149.     def preorder(self):
  150.         if self.__root:
  151.             return self.__root.preorder(self.__root)
  152.     def inorder(self):
  153.         if self.__root:
  154.             return self.__root.inorder(self.__root)
  156.     def postorder(self):
  157.         if self.__root:
  158.             return self.__root.postorder(self.__root)
  160.     def __numbers_of_nodes_help(self,root):
  161.         if root:
  162.             return self.__numbers_of_nodes_help(root._left)+self.__numbers_of_nodes_help(root._right)+1
  163.         else:
  164.             return 0
  165.     def numbers_of_nodes(self):
  166.         return self.__numbers_of_nodes_help(self.__root)
  168. my_list=[8,5,10,2,6,9,11]
  169. bst=BST()
  170. for e in my_list:
  171.     bst.insert(e)
  172. print("中序遍历：",bst.inorder())
  173. print("后序遍历：",bst.postorder())
  174. print("前序遍历：",bst.preorder())
  175. print("结点数：",bst.numbers_of_nodes())
  176. #剩下的功能可以自己尝试

输出：

  1. 中序遍历： [2, 5, 6, 8, 9, 10, 11]
  2. 后序遍历： [2, 6, 5, 9, 11, 10, 8]
  3. 前序遍历： [8, 5, 2, 6, 10, 9, 11]
  4. 结点数： 7

对了，那个二叉搜索树的图是这样的：

20180308180045166

发表评论

表情：
评论列表 （有 0 条评论，246人围观）

还没有评论，来说两句吧...

相关阅读

    相关 Python实现二叉搜索

    1、什么是二叉搜索 二叉搜索是在一个有序的列表中，寻找目标元素。因此我们需要对半查找即可。当目标元素比中间元素小，则在中间元素的左边查找；反之，则在目标元素的右边查找。直

    桃扇骨桃扇骨/ 0 赞/ 208 阅读

    相关 二叉搜索树实现

    本文给出二叉搜索树介绍和实现 首先说它的性质：所有的节点都满足，左子树上所有的节点都比自己小，右边的都比自己大。 那这个结构有什么有用呢？ 首先可以快速二分查找。还可以中

    傷城~傷城~/ 0 赞/ 266 阅读

    相关 二叉搜索树

    二叉搜索树 基本概念 二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树: 1. 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

    妖狐艹你老母妖狐艹你老母/ 0 赞/ 466 阅读

    相关 java实现二叉搜索树

    二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。定义如下 > （1）若左子树不空，则左子树上所有结点的

    红太狼红太狼/ 0 赞/ 415 阅读