1. # -*-encoding=utf-8 -*-
    2. import random
    4. class BiTreeNode:   #定义二叉树
    5.     def __init__(self,data):
    6.         self.data=data
    7.         self.lchild=None
    8.         self.rchild=None
    9.         self.parent=None
    10.         self.bf=0
    12. class BST:
    13.     def __init__(self,li=None):  #传一个列表
    14.         self.root=None
    15.         if li:                   #构造函数中,列表不为空时，就直接调用非递归方式插入该列表
    16.             for val in li:
    17.                 self.insert_no_rec(val)
    18.     def insert(self,node,val):  #递归方式插入
    19.         if not node:
    20.             node=BiTreeNode(val)  #如果节点为空，则直接插入节点值
    21.         elif val<node.data:
    22.             node.lchild=self.insert(node.lchild,val) #插入左孩子
    23.             node.lchild.parent=node #将左孩子与父节点连起来
    24.         elif val> node.data:
    25.             node.rchild=self.insert(node.rchild,val) #插入右孩子
    26.             node.rchild.parent=node #将右孩子与父节点连起来
    27.         return node
    29.     def insert_no_rec(self,val):
    30.         p=self.root
    31.         if not p:    #空树时，直接定义个二叉树根节点
    32.             self.root=BiTreeNode(val)
    33.             return
    34.         while True:
    35.             if val<p.data:
    36.                 if p.lchild:      #此处可看出与递归的方式的区别
    37.                     p=p.lchild
    38.                 else:           #左孩子不存在
    39.                     p.lchild=BiTreeNode(val)
    40.                     p.lchild.parent=p
    41.                     return
    42.             elif val>p.data:
    43.                 if p.rchild:
    44.                     p=p.rchild
    45.                 else:
    46.                     p.rchild=BiTreeNode(val)
    47.                     p.rchild.parent=p
    48.                     return
    49.             else:
    50.                 return
    51.     def query(self,node,val):  #递归查询
    52.         if not node:
    53.             return None
    54.         if node.data<val:
    55.             return self.query(node.rchild,val)
    56.         elif node.data>val:
    57.             return self.query(node.lchild,val)
    58.         else:
    59.             return node
    60.     def query_no_rec(self,val): #非递归查询
    61.         p=self.root
    62.         while p:
    63.             if p.data<val:  #如果写成大于后，会报错AttributeError: 'NoneType' object has no attribute 'data'？？？？？
    64.                 p=p.rchild
    65.             elif p.data>val:
    66.                 p=p.lchild
    67.             else:
    68.                 return p
    69.         return None #如果 p为空，则返回空
    71.     def pre_order(self,root):  # 前序遍历     #放在类里面，需要加self,下面方法调用也一样
    72.         if root:  # 如果不是空，先访问根，再访问左子树，再访问右子树
    73.             print(root.data, end=',')
    74.             self.pre_order(root.lchild)
    75.             self.pre_order(root.rchild)
    77.     def in_order(self,root):  # 中序遍历
    78.         if root:  # 如果不是空，先访问左，再访问根，再访问右
    79.             self.in_order(root.lchild)
    80.             print(root.data, end=',')
    81.             self.in_order(root.rchild)
    83.     def post_order(self,root):  # 后序遍历
    84.         if root:  # 如果不是空，先访问左，再访问右，再访问根
    85.             self.post_order(root.lchild)
    86.             self.post_order(root.rchild)
    87.             print(root.data, end=',')
    88.     #删除
    89.     def __remove_node_1(self,node):
    90.         #情况1，node是叶子节点
    91.         if not node.parent: #判断是不是根节点
    92.             self.root=None
    93.         if node==node.parent.lchild:#node是它父亲的左孩子
    94.             node.parent.lchild=None
    95.             node.parent=None  #可写可不写
    96.         else: #node是它父亲的右孩子
    97.             node.rchild =None
    98.     def __remove_node_21(self,node):
    99.         #情况2.1:node只有一个左孩子，node的左孩子与node的父节点连起来
    100.         if not node.parent: #根节点
    101.             self.root=node.lchild
    102.             node.lchild.parent=None
    103.         elif node==node.parent.lchild:
    104.             node.parent.lchild =node.lchild
    105.             node.lchild.parent=node.parent
    106.         else:
    107.             node.parent.rchild=node.lchild
    108.             node.lchild.parent=node.parent
    109.     def __remove_node_22(self,node):
    110.         #情况2.2：node只有一个右孩子,node的右孩子与node的父节点连起来
    111.         if not node.parent:
    112.             self.root=node.rchild
    113.         elif node==node.parent.lchild:
    114.             node.parent.lchild=node.rchild
    115.             node.rchild.parent=node.parent
    116.         else:
    117.             node.parent.rchild=node.rchild
    118.             node.rchild.parent=node.parent
    119.     def delete(self,val):
    120.         if self.root: #不是空树
    121.             node=self.query_no_rec(val)
    122.             if not node: #不存在
    123.                 return False
    124.             if not node.lchild and not node.rchild: #1.叶子节点
    125.                 self.__remove_node_1(node)
    126.             elif not node.rchild: #2.1只有一个左孩子
    127.                 self.__remove_node_21(node)
    128.             elif not node.lchild: #2.2只有一个右孩子
    129.                 self.__remove_node_22(node)
    130.             else:#3.两个孩子都有
    131.                 min_node=node.rchild
    132.                 while min_node.lchild:
    133.                     min_node=min_node.lchild
    134.                 node.data=min_node.data
    135.                 #删除min_node
    136.                 if min_node.rchild:
    137.                     self.__remove_node_22(min_node)
    138.                 else:
    139.                     self.__remove_node_1(min_node)
    142. #1、插入列表，然后前中后遍历
    143. # tree=BST([4,6,7,9,2,1,3,5,8])
    144. # tree.pre_order(tree.root)
    145. # print("")
    146. # tree.in_order(tree.root)
    147. # print("")
    148. # tree.post_order(tree.root)
    150. #2、插入随机列表，然后前中后遍历
    151. # li=list(range(100))
    152. # random.shuffle(li)
    153. # tree=BST(li)
    154. #
    155. # tree.pre_order(tree.root)
    156. # print("")
    157. # tree.in_order(tree.root)   #中序一定是递增
    158. # print("")
    159. # tree.post_order(tree.root)
    161. #插入偶数列表后，执行搜索
    162. # li=list(range(0,500,2)) #偶数列表
    163. # random.shuffle(li)
    164. # tree=BST(li)
    165. # print(tree.query_no_rec(4).data)  #为何要写成.data  ????
    166. # print(tree.query_no_rec(3))
    168. #插入列表后，测试删除后中序遍历结果
    169. # tree=BST([1,4,2,5,3,8,6,9,7])
    170. # tree.in_order(tree.root)
    171. # print("")
    172. # tree.delete(4)
    173. # tree.delete(1)
    174. # tree.delete(8)
    175. # tree.in_order(tree.root)