快捷導(dǎo)航

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

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

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

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

1. 二叉查找樹的定義：

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

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

3. 二叉查找樹的python實(shí)現(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);       #找到后繼結(jié)點(diǎn) 
      root.val=tmp.val; 
      root.right=delnum(root.right,val);  #實(shí)際刪除的是這個(gè)后繼結(jié)點(diǎn) 
       
    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);

結(jié)果：