python二叉树查找、插入、删除

二叉树
参考：https://blog.csdn.net/u010089444/article/details/70854510
修改了delete的两处错误。
# encoding: utf-8
 class Node:
 def __init__(self, data, name=None, size=0, path=None):
 self.data = data
 self.name = name
 self.size = size
 self.path = path
 self.lchild = None
 self.rchild = None


 class BST:
 def __init__(self, data, name=None, size=0, path=None):
 self.root = Node(data, name, size, path)

 # 搜索
 def search(self, node, parent, data):
 if node is None:
 return False, node, parent
 if node.data == data:
 return True, node, parent
 if node.data > data:
 return self.search(node.lchild, node, data)
 else:
 return self.search(node.rchild, node, data)

 # 插入
 def insert(self, data, name=None, size=0, path=None):
 flag, n, p = self.search(self.root, self.root, data)
 if not flag:
 new_node = Node(data, name, size, path)
 # if p is None:
 # self.root = new_node
 if data > p.data:
 p.rchild = new_node
 else:
 p.lchild = new_node
 return not flag, n, p

 # 删除
 def delete(self, root, data):
 flag, n, p = self.search(root, root, data)
 if flag is False:
 print("无该关键字，删除失败")
 else:
 if n.lchild is None:
 if n == p.lchild:
 p.lchild = n.rchild
 else:
 p.rchild = n.rchild
 del p
 elif n.rchild is None:
 if n == p.lchild:
 p.lchild = n.lchild
 else:
 p.rchild = n.lchild
 del n
 else: # 左右子树均不为空
 pre = n.rchild
 if pre.lchild is None:
 n.data = pre.data
 n.rchild = pre.rchild
 del pre
 else: # leftmost leaf replace n, and the leaf's r-child replace itself
 next = pre.lchild
 while next.lchild is not None:
 pre = next
 next = next.lchild
 n.data = next.data
 pre.lchild = next.rchild
 del next

 # 先序遍历
 def preOrderTraverse(self, node):
 if node is not None:
 print(node.data)
 self.preOrderTraverse(node.lchild)
 self.preOrderTraverse(node.rchild)

 # 中序遍历
 def inOrderTraverse(self, node):
 if node is not None:
 self.inOrderTraverse(node.lchild)
 print(node.data, node.name, node.size, node.path)
 self.inOrderTraverse(node.rchild)

 # 后序遍历
 def postOrderTraverse(self, node):
 if node is not None:
 self.postOrderTraverse(node.lchild)
 self.postOrderTraverse(node.rchild)
 print(node.data)


 if __name__ == '__main__':
 print('test tree')

 a = ['49', '38', '65', '97', '49', '13', '1']
 bst = BST(a[0]) # 创建二叉查找树
 for data in a[1:]:
 print(bst.insert(data))

 print('in order traverse')
 bst.inOrderTraverse(bst.root) # 中序遍历

 bst.delete(bst.root, '49')
 print('delete 49')
 bst.postOrderTraverse(bst.root)
（可以包装一下，检测文件夹下重复文件）