第C++數(shù)據(jù)結(jié)構(gòu)之二叉搜索樹的實現(xiàn)詳解目錄前言介紹實現(xiàn)節(jié)點的實現(xiàn)二叉搜索樹的查找二叉搜索樹的插入二叉搜索樹的刪除總結(jié)

前言

今天我們來學(xué)一個新的數(shù)據(jù)結(jié)構(gòu)：二叉搜索樹。

介紹

二叉搜索樹也稱作二叉排序樹，它具有以下性質(zhì)：

非空左子樹的所有鍵值小于其根節(jié)點的鍵值非空右子樹的所有鍵值大于其根節(jié)點的鍵值左，右子樹都是二叉搜索樹

那么我先畫一個二叉搜索樹給大家看看，是不是真的滿足上面的性質(zhì)。

我們就以根節(jié)點6為例子來看，我們會發(fā)現(xiàn)比6小的都在6的左邊，而比6大的都在6的右邊。對于6的左右子樹來說，所有的節(jié)點都遵循這個規(guī)則。

同時我們還可以發(fā)現(xiàn)如果對搜索二叉樹進行一個中序遍歷，我們得到的序列是個有序序列，這就是為什么二叉搜索樹也可以稱作二叉排序樹。

實現(xiàn)

節(jié)點的實現(xiàn)

templatetypenameK

structBTreeNode

BTreeNodeK*_left;

BTreeNodeK*_right;

K_key;

BTreeNode(constKkey)

:_key(key),_left(nullptr),_right(nullptr)

二叉搜索樹的查找

二叉搜索樹的查找思路很簡單：要找的值比當(dāng)前節(jié)點小就去左子樹找，比當(dāng)前節(jié)點大就往右子樹找，找到空節(jié)點就說明沒找到返回false即可。

首先我們先看看遞歸的版本。

boolfindR(constTval,Node*root)//T為節(jié)點的K,Node為節(jié)點

if(root==nullptr)

returnfalse;

if(root-_keyval)

returnfindR(root-_right,val);

elseif(root-_keyval)

returnfindR(root-_left,val);

else

returntrue;

接著看看非遞歸的版本

boolfind(constTval)

Node*cur=_root;//_root為二叉搜索樹的根節(jié)點

while(cur)

if(valcur-_key)

cur=cur-_left;

elseif(valcur-_key)

cur=cur-_right;

else

returntrue;

returnfalse;

}

二叉搜索樹的插入

二叉搜索樹的插入和查找差別不大，首先尋找插入位置，比當(dāng)前節(jié)點小就往左子樹找，比當(dāng)前節(jié)點大就往右子樹找，直到找到空指針時，就可以進行一個插入。

那么要插入的值和當(dāng)前節(jié)點相同該怎么辦呢？我們此時實現(xiàn)的二叉搜索樹是一個無重復(fù)元素的二叉搜索樹，所以對于相同的值我采取的方式是返回一個false，大家如果想實現(xiàn)一個有重復(fù)元素的二叉搜索樹，可以選擇將重復(fù)的值放在右子樹或左子樹都可。

二叉搜索樹的插入和查找一樣，有遞歸和非遞歸兩個版本，首先我們先來看看非遞歸的版本。

boolinsert(constTval)

//空樹直接改變根節(jié)點

if(_root==nullptr)

_root=newNode(val);

returntrue;

//非空樹先尋找插入位置

Node*pre=nullptr;

Node*cur=_root;

while(cur)

if(valcur-_key)

pre=cur;

cur=cur-_right;

elseif(valcur-_key)

pre=cur;

cur=cur-_left;

else

returnfalse;

//判斷新節(jié)點該插入到哪里

cur=newNode(val);

if(valpre-_key)

pre-_left=cur;

else

pre-_right=cur;

returntrue;

}

接下來用一個動畫來表示一下這個插入過程。

接下來我們來看看遞歸版本是如何實現(xiàn)的

boolinsertR(constTval,Node*root)

if(root==nullptr)

Node*newNode=newNode(val);

root=newNode;

if(root-_keyval)

returninsertR(val,root-_right);

elseif(root-_keyval)

returninsertR(val,root-_left);

else

returnfalse;

此時我們可以發(fā)現(xiàn)，遞歸版本沒有非遞歸版本中的parent指針了，參數(shù)列表中只有一個root指針，這是為什么呢？

我們可以看見我們的root指針不僅是一個指針，同時它還是一個引用。這就意味著我們對root的修改也可以影響上一層傳遞過來的指針的值。所以此時我們不需要parent指針，就可以對上一個節(jié)點的指針進行一個修改。

二叉搜索樹的刪除

理論部分：

二叉搜索樹的刪除相比前面兩個要麻煩那么一丟丟，首先當(dāng)然是找要刪除的節(jié)點，找到后通常有以下三種情況：

此節(jié)點無左右子樹此節(jié)點有右子樹或右子樹此節(jié)點有左右子樹

我們要做的就是對這三種情況分別進行一個處理。

1.首先是此節(jié)點無左右子樹，這種情況我們直接將此節(jié)點刪除即可

2.然后是此節(jié)點只有一顆子樹，這個也比較簡單，如果此節(jié)點是父節(jié)點的左節(jié)點，那么我們只需要將父節(jié)點的左指針改成指向此節(jié)點的子樹即可。

3.最后一種就是既有左子樹又有右子樹的情況了，此時為了不破壞結(jié)構(gòu)，我們需要用到替換刪除法。首先我們先找到要刪除的節(jié)點，然后找節(jié)點的左子樹的最右節(jié)點或右子樹的最左節(jié)點，將兩個節(jié)點進行一下互換，再將原節(jié)點刪除。

代碼部分：

首先是非遞歸版本

boolerase(constTval)

Node*cur=_root;

Node*pre=nullptr;

//尋找刪除位置

while(cur)

if(cur-_keyval)

pre=cur;

cur=cur-_right;

elseif(cur-_keyval)

pre=cur;

cur=cur-_left;

else//找到了進行刪除

if(cur-_left==nullptr)//左子樹為空

if(cur==_root)

_root=cur-_right;

else

if(cur==pre-_left)

pre-_left=cur-_right;

else

pre-_right=cur-_right;

deletecur;

elseif(cur-_right==nullptr)//右子樹為空

if(cur==_root)

_root=cur-_left;

else

if(cur==pre-_left)

pre-_left=cur-_left;

else

pre-_right=cur-_left;

deletecur;

else//左右子樹都不為空

//找左子樹的最右節(jié)點

Node*tmp=cur-_left;

Node*tmp_pre=cur;

while(tmp-_right)

tmp_pre=tmp;

tmp=tmp-_right;

//節(jié)點互換

cur-_key=tmp-_key;

if(tmp==tmp_pre-_left)

tmp_pre-_left=tmp-_left;

else

tmp_pre-_right=tmp-_left;

deletetmp;

returntrue;

returnfalse;

接下來是遞歸版本

booleraseR(constTval,Node*root)

//找不到返回false

if(root==nullptr)

returnfalse;

//尋找插入位置

if(root-_keyval)

returneraseR(val,root-_right);

elseif(root-_keyval)

returneraseR(val,root-_left);

else

if(root-_left==nullptr)//左子樹為空

root=root-_right;

elseif(root-_right==nullptr)//右子樹為空

root=root-_left;

else//左右子樹都不為空

Node*cur=root-_left;

while(cur-_right)

cur=cur-_right;

swap(cur-_key,root-_key)