2022年 11月 8日

二叉搜索树（python）

 
    二叉搜索树（BST）又称二叉查找树或二叉排序树。一棵二叉搜索树是以二叉树来组织的，可以使用一个链表数据结构来表示，其中每一个结点就是一个对象。一般地，除了key和位置数据之外，每个结点还包含属性lchild、rchild和parent，分别指向结点的左孩子、右孩子和双亲（父结点）。如果某个孩子结点或父结点不存在，则相应属性的值为空（NIL）。根结点是树中唯一父指针为NULL的结点，而叶子结点的孩子结点指针也为NULL。 以上来自百度百科
实现代码如下

  1. #encoding='utf-8'
  2. class Node(object): #结点类
  3.     def __init__(self,data):
  4.         self.data = data
  5.         self.parent = None
  6.         self.lchild = None
  7.         self.rchild = None
  8. class BST(object):
  9.     def __init__(self,node_list):
  10.         self.root = Node(node_list[0])
  11.         for data in node_list[1:]:
  12.             self.insert(data)
  13.     #查找一个具有给定关键字的结点
  14.     def search(self,data):
  15.         while self.root != None and data != self.root.data:
  16.             if data < self.root.data:
  17.                 self.root = self.root.lchild
  18.             else:
  19.                 self.root = self.root.rchild
  20.         return self.root
  21.     #插入一个具有给定关键字的节点
  22.     def insert(self,data):
  23.         z =  Node(data)
  24.         y = None
  25.         x = self.root
  26.         while x != None:
  27.             y = x
  28.             if z.data < x.data:
  29.                 x = x.lchild
  30.             else :
  31.                 x = x.rchild
  32.         z.parent = y
  33.         if y == None:
  34.             self.root = z
  35.         elif z.data < y.data:
  36.             y.lchild = z
  37.         else:
  38.             y.rchild = z
  39.     #删除一个结点
  40.     def transplant(self,u,v):
  41.         if u.parent == None:
  42.             self.root = v
  43.         elif u == u.parent.lchild:
  44.             u.parent.lchild = v
  45.         else:
  46.             u.parent.rchild = v
  47.         if v != None:
  48.             v.parent = u.parent
  49.     def delete(self,z):
  50.         if z.lchild == None:
  51.             self.transplant(z,z.rchild)
  52.         elif z.rchild == None:
  53.             self.transplant(z,z.lchild)
  54.         else:
  55.             y = self.mininum(z.rchild)
  56.             if y.parent != z:
  57.                 self.transplant(y,y.rchild)
  58.                 y.rchild = z.rchild
  59.                 y.rchild.parent = y
  60.             self.transplant(z,y)
  61.             y.lchild = z.lchild
  62.             y.lchild.parent = y
  63.  
  64.     #查找最小关键字
  65.     def mininum(self,x):
  66.         while x.lchild != None:
  67.             x = x.lchild
  68.         return x
  69.     #查找最大关键字
  70.     def maxnum(self,x):
  71.         while x.rchild != None:
  72.             x = x.rchild
  73.         return x
  74.     #后继与前驱
  75.     def successor(self,x):
  76.         if x.rchild != None:
  77.             return self.mininum(x.rchild)
  78.         y = x.parent
  79.         while y != None and x == y.rchild:
  80.             x = y
  81.             y = y.parent
  82.         return y
  83.     #中序遍历
  84.     def inorder_tree_walk(self,x):
  85.         if x != None:
  86.             self.inorder_tree_walk(x.lchild)
  87.             print(x.data)
  88.             self.inorder_tree_walk(x.rchild)
  89.  
  90. if __name__ == "__main__":
  91.     BST_1 = BST([6,5,7,2,5,8])
  92.     BST_1.inorder_tree_walk(BST_1.root)
  93.     print('')
  94.     BST_1.delete(BST_1.root)
  95.     BST_1.inorder_tree_walk(BST_1.root)

输出结果：

2

5

5

6

7

8

2

5

5

7

8

 如有错误，还望指正！