python實現(xiàn)二叉查找樹實例代碼

更新時間：2018年02月08日 11:25:20 作者：零丁若嘆

這篇文章主要介紹了python實現(xiàn)二叉查找樹實例代碼，分享了相關代碼示例，小編覺得還是挺不錯的，具有一定借鑒價值，需要的朋友可以參考下

本文研究的主要是python實現(xiàn)二叉查找樹的相關內容，具體介紹及實現(xiàn)如下。

1. 二叉查找樹的定義：

左子樹不為空的時候，左子樹的結點值小于根節(jié)點，右子樹不為空時，右子樹的結點值大于根節(jié)點，左右子樹分別為二叉查找樹

2. 二叉查找樹的最左邊的結點即為最小值，要查找最小值，只需遍歷左子樹的結點直到為空為止，同理，最右邊的結點結尾最大值，要查找最大值，只需遍歷右子樹的結點直到為空為止。二叉查找樹的插入查找和刪除都是通過遞歸的方式來實現(xiàn)的，刪除一個結點的時候，先找到這個結點S，如果這個結點左右孩子都不為空，這時并不是真正的刪除這個結點S，而是在其右子樹找到后繼結點，將后繼結點的值付給S，然后刪除這個后繼結點即可。如果結點S的左孩子或者右孩子為空，可以直接刪除這個結點S。

3. 二叉查找樹的python實現(xiàn)：

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:                       # 刪除要區(qū)分左右孩子是否為空的情況 
    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);

結果：