python实现二叉查找树实例代码_Python

本文研究的主要是python实现二叉查找树的相关内容，具体介绍及实现如下。

左子树不为空的时候，左子树的结点值小于根节点，右子树不为空时，右子树的结点值大于根节点，左右子树分别为二叉查找树

2. 二叉查找树的最左边的结点即为最小值，要查找最小值，只需遍历左子树的结点直到为空为止，同理，最右边的结点结尾最大值，要查找最大值，只需遍历右子树的结点直到为空为止。二叉查找树的插入查找和删除都是通过递归的方式来实现的，删除一个结点的时候，先找到这个结点S，如果这个结点左右孩子都不为空，这时并不是真正的删除这个结点S，而是在其右子树找到后继结点，将后继结点的值付给S，然后删除这个后继结点即可。如果结点S的左孩子或者右孩子为空，可以直接删除这个结点S。

3. 二叉查找树的python实现：

									class TreeNode: 

									  def __init__(self,val): 

									    self.val=val; 

									    self.left=None; 

									    self.right=None; 

									def insert(root,val): 

									  if root is None: 

									    root=TreeNode(val); 

									  else: 

									    if val<root.val: 

									      root.left=insert(root.left,val);  #递归地插入元素 

									    elif val>root.val: 

									      root.right=insert(root.right,val);  

									  return root; 

									def query(root,val): 

									  if root is None: 

									    return ; 

									  if root.val is val: 

									    return 1; 

									  if root.val <val: 

									    return query(root.right,val); #递归地查询 

									  else:  

									    return query(root.left,val); 

									def findmin(root): 

									  if root.left: 

									    return findmin(root.left); 

									  else: 

									    return root; 

									def delnum(root,val): 

									  if root is None: 

									    return ; 

									  if val<root.val: 

									    return delnum(root.left,val); 

									  elif val>root.val: 

									    return delnum(root.right,val); 

									  else:                       # 删除要区分左右孩子是否为空的情况 

									    if(root.left and root.right): 

									      tmp=finmin(root.right);       #找到后继结点 

									      root.val=tmp.val; 

									      root.right=delnum(root.right,val);  #实际删除的是这个后继结点 

									    else: 

									      if root.left is None: 

									        root=root.right; 

									      elif root.right is None: 

									        root=root.left; 

									  return root; 

									#测试代码       

									root=TreeNode(3); 

									root=insert(root,2); 

									root=insert(root,1); 

									root=insert(root,4); 

									#print query(root,3); 

									print query(root,1); 

									root=delnum(root,1); 

									print query(root,1);