1. from pprint import pformat
    2. from typing import List
    5. class Node:
    6.     def __init__(self,data):
    7.         self.data=data
    8.         self.left=None
    9.         self.right=None
    10.         self.parent=None
    12.     def __repr__(self):
    13.         if self.left is None and self.right is None:
    14.             return str(self.data)
    15.         return pformat({"%s"%(self.data):(self.left,self.right)},indent=1)
    16. # a=Node(1)
    17. # print(a)
    18. class BST:
    19.     def  __init__(self):
    20.         self.root=None
    22.     def is_empty(self):
    23.         if self.root is None:
    24.             return True
    25.         else:
    26.             return  False
    27.     def __insert(self,data):
    28.         node=Node(data)
    29.         if self.is_empty():
    30.             self.root=node
    31.         else:
    32.             parent_node=self.root
    33.             while True:
    34.                 if data<=parent_node.data:
    35.                     if parent_node.left is None:
    36.                         parent_node.left=node
    37.                         break
    38.                     else:
    39.                         parent_node=parent_node.left
    40.                 if data>parent_node.data:
    41.                     if parent_node.right is None:
    42.                         parent_node.right=node
    43.                         break
    44.                     else:
    45.                         parent_node=parent_node.right
    46.             node.parent= parent_node
    47.     def insert(self,*datas):
    48.         for data in datas:
    49.             self.__insert(data)
    50.         return self
    51.     def search(self,data):
    52.         if self.is_empty():
    54.             raise IndexError("ddd")
    55.         else:
    56.             node=self.root
    57.             while node and node.data!=data:
    58.                 if data<=node.data:
    59.                     node=node.left
    60.                 else:
    61.                     node=node.right
    62.             return node
    63.     def is_right(self,node):
    64.         return node==node.parent.right
    66.     def __reassign_nodes(self,node,new_children):#找父亲,找孩子
    67.         if new_children is not None:#如果当前结点子结点不为空
    68.             new_children.parent=node.parent#子节点和当前结点互换位置,找父亲
    69.         if node.parent is not None:#互换位置后如果当前结点有父结点判断父亲是否为空
    70.             if self.is_right(node):#判断删除结点是左还是右,然后孩子代替他
    71.                 node.parent.right=new_children#找孩子
    72.             else:
    73.                 node.parent.left=new_children#删除根节点
    74.         else:
    75.             self.root=new_children
    76.     def remove(self,data):
    77.         if self.root is None:
    78.             raise IndexError("空树")
    79.         else:
    80.             node=self.search(data)#返回值对应的结点
    81.             if node:
    82.                 if node.left is None and node.right is None:
    83.                     self.__reassign_nodes(node,None)
    84.                 elif node.left is None:
    85.                     self.__reassign_nodes(node,node.right)
    86.                 elif node.right is None:
    87.                     self.__reassign_nodes(node,node.left)
    88.                 else:#左右孩子都有
    89.                     tmp_node=self.get_max(node.left)#找到 左子树的最大结点
    90.                     self.remove(tmp_node.data)#删除节点
    91.                     node.data=tmp_node.data#不改变树结构,只改变当前结点值
    92. #-------------------------------------------
    93.     # 栈实现前序遍历(8 3 1 6 10)根左右
    94.     def preOrderTravers(self,node):
    95.         stack=[node]#压栈
    96.         while len(stack)>0:
    97.             print(node.data)#打印弹出的结点
    98.             if node.right:#先进后出，先添加右在添加左
    99.                 stack.append(node.right)
    100.             if node.left:
    101.                 stack.append(node.left)
    102.             node=stack.pop()#弹出结点
    103.         # 递归实现前序遍历
    105.     def preOrderTravers1(self, node):
    106.         if not node:
    107.             return None
    108.         print(node.data)
    109.         self.preOrderTravers1(node.left)
    110.         self.preOrderTravers1(node.right)
    112.     def preOrderTravers2(self, node):
    113.         stack = []
    114.         while node or len(stack) > 0:
    115.             while node:
    116.                 print(node.data)  # 打印弹出的结点
    117.                 stack.append(node)
    118.                 node=node.left
    119.             if len(stack)>0:
    120.                 node = stack.pop()  # 弹出结点
    121.                 node=node.right
    123. # -------------------------------------------
    124. # 中序遍历 左根右 1,3,6,8,10
    125.     def in_order_stack(self,node):
    126.         stack=[]
    127.         # 当结点不为空或栈内有元素
    128.         while node or len(stack)>0:
    129.             # 当结点不为空
    130.             while node:
    131.                 # 将所有左结点压入栈
    132.                 stack.append(node)
    133.                 node=node.left
    134.             if len(stack)>0:#当栈不为空
    135.                 # 弹出栈顶
    136.                 node=stack.pop()
    137.                 # 打印栈顶
    138.                 print(node.data)
    139.                 # 在判断右边
    140.                 node=node.right
    141. #递归实现中序遍历
    142.     def in_order_stacck1(self,node):
    143.         if not node:
    144.             return None
    145.         else:
    146.             self.in_order_stack(node.left)
    147.             print(node.data)
    148.             self.in_order_stack(node.right)
    149. #-----------------------------
    150. #层序遍历:导入队列的包
    151.     def cc(self,root : Node):
    152.         from queue import Queue
    153.         if self.root is None:
    154.             return "empty"
    155.         queue=Queue()
    156.         queue.put(root)
    157.         while not queue.empty():
    158.             node=queue.get()
    159.             print(node.data)
    160.             if node.left:
    161.                 queue.put(node.left)
    162.             if node.right:
    163.                 queue.put(node.right)
    167.     def __str__(self):
    168.         return str(self.root)
    170.     def get_max(self, node):
    171.         if node is None:
    172.             node=self.root
    173.         if node is not None:
    174.             while node.right :
    175.                 node=node.right
    176.         return node
    177.     def get_min(self,node):
    178.         if node is None:
    179.             node=self.root
    180.         if not self.is_empty():
    181.             while node.left :
    182.                 node=node.left
    183.         return node
    184. # -------------------------
    185. # 俩个栈实现后序遍历:
    186.     def post_order_stack(self,node):
    187.         if node is None:
    188.             return False
    189.         else:
    190.             stack1=[]
    191.             stack2=[]
    192.             stack1.append(node)
    193.             while stack1:#找出后序遍历的逆序,存放在stack2
    194.                 node=stack1.pop()
    195.                 if node.left:
    196.                     stack1.append(node.left)
    197.                 if node.right:
    198.                     stack1.append(node.right)
    199.                 stack2.append(node)
    200.             while stack2:#将stack2 里的元素出站,即为后序遍历
    201.                 print(stack2.pop().data,end=" ")
    202. #总结版遍历模板:
    203.     def inorderTraversal(self,root: Node)->List[int]:
    204.         white,gray=0,1
    205.         res=[]
    206.         stack=[(white,root)]
    207.         while stack:
    208.             color,node=stack.pop()
    209.             if node is None:
    210.                 continue
    211.             if color == white:
    212. #                 前序
    213.                 stack.append((white,node.right))
    214.                 stack.append((white,node.left))
    215.                 stack.append((gray,node))
    217.                 # 中序
    218.                 stack.append((white, node.right))
    219.                 stack.append((gray, node))
    220.                 stack.append((white, node.left))
    221.             #     后序
    222.                 stack.append((gray, node))
    223.                 stack.append((white, node.right))
    224.                 stack.append((white, node.left))
    227.             else:
    228.                 return res
    230. # 根节点删除的问题
    232. if __name__ == '__main__':
    234.     n=BST().insert(8,3,1,6,10)
    235.     # print(n.search(5))\
    236.     # n.remove(8)
    237.     # n.preOrderTravers(n.root)
    238.     # n.preOrderTravers1(n.root)
    239.     # n.in_order_stack(n.root)
    240.     # n.cc(n.root)
    241.     # n.in_order_stacck1(n.root)
    242.     n.inorderTraversal(n.root)
    243.     print(n)