本文研究的主要是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é)果：

1
None
>>>

總結(jié)

以上就是本文關(guān)于python實(shí)現(xiàn)二叉查找樹實(shí)例代碼的全部內(nèi)容，希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！