python怎么實現二叉查找樹

這篇文章主要介紹了python怎么實現二叉查找樹，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

具體介紹及實現如下。

1. 二叉查找樹的定義：

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

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);

結果：

1
None
>>>

感謝你能夠認真閱讀完這篇文章，希望小編分享的“python怎么實現二叉查找樹”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，更多相關知識等著你來學習!