一步一步寫二叉查找樹(shù)
作者：C小加 更新時(shí)間：2012-8-9
二叉查找樹(shù)（BST）是二叉樹(shù)的一個(gè)重要的應(yīng)用，它在二叉樹(shù)的基礎(chǔ)上加上了這樣的一個(gè)性質(zhì)：對(duì)于樹(shù)中的每一個(gè)節(jié)點(diǎn)來(lái)說(shuō)，如果有左兒子的話，它的左兒子的值一定小于它本身的值，如果有右兒子的話，它的右兒子的值一定大于它本身的值。
二叉查找樹(shù)的操作一般有插入、刪除和查找，這幾個(gè)操作的平均時(shí)間復(fù)雜度都為O(logn)，插入和查找操作很簡(jiǎn)單，刪除操作會(huì)復(fù)雜一點(diǎn)，除此之外，因?yàn)槎鏄?shù)的中序遍歷是一個(gè)有序序列，我就額外加上了一個(gè)中序遍歷操作。
二叉查找樹(shù)的應(yīng)用不是很多，因?yàn)樗顗牡臅r(shí)候跟線性表差不多，大部分會(huì)應(yīng)用到它的升級(jí)版，平衡二叉樹(shù)和紅黑樹(shù)，這兩棵樹(shù)都能把時(shí)間復(fù)雜度穩(wěn)定在O(logn)左右。雖然不會(huì)用到，但是二叉查找樹(shù)是一定要學(xué)好的，畢竟它是平衡二叉樹(shù)和紅黑樹(shù)的基礎(chǔ)。
接下來(lái)一步一步寫一個(gè)二叉查找樹(shù)模板。完整代碼下載
第一步：節(jié)點(diǎn)信息
二叉查找樹(shù)的節(jié)點(diǎn)和二叉樹(shù)的節(jié)點(diǎn)大部分是一樣的，不同的是，二叉查找樹(shù)多了一個(gè)值出現(xiàn)的次數(shù)。如圖1顯示了二叉查找樹(shù)的節(jié)點(diǎn)信息。
代碼如下：
//二叉查找樹(shù)節(jié)點(diǎn)信息
template<class T>
class TreeNode
{
public:
TreeNode():lson(NULL),rson(NULL),freq(1){}//初始化
T data;//值
unsigned int freq;//頻率
TreeNode* lson;//指向左兒子的坐標(biāo)
TreeNode* rson;//指向右兒子的坐標(biāo)
};
第二步：二叉查找樹(shù)類的聲明
代碼如下：
//二叉查找樹(shù)類的屬性和方法聲明
template<class T>
class BST
{
private:
TreeNode<T>* root;//根節(jié)點(diǎn)
void insertpri(TreeNode<T>* &node,T x);//插入
TreeNode<T>* findpri(TreeNode<T>* node,T x);//查找
void insubtree(TreeNode<T>* node);//中序遍歷
void Deletepri(TreeNode<T>* &node,T x);//刪除
public:
BST():root(NULL){}
void insert(T x);//插入接口
TreeNode<T>* find(T x);//查找接口
void Delete(T x);//刪除接口
void traversal();//遍歷接口
};
第三步：插入
根據(jù)二叉查找樹(shù)的性質(zhì)，插入一個(gè)節(jié)點(diǎn)的時(shí)候，如果根節(jié)點(diǎn)為空，就此節(jié)點(diǎn)作為根節(jié)點(diǎn)，如果根節(jié)點(diǎn)不為空，就要先和根節(jié)點(diǎn)比較，如果比根節(jié)點(diǎn)的值小，就插入到根節(jié)點(diǎn)的左子樹(shù)中，如果比根節(jié)點(diǎn)的值大就插入到根節(jié)點(diǎn)的右子樹(shù)中，如此遞歸下去，找到插入的位置。重復(fù)節(jié)點(diǎn)的插入用值域中的freq標(biāo)記。如圖2是一個(gè)插入的過(guò)程。
二叉查找樹(shù)的時(shí)間復(fù)雜度要看這棵樹(shù)的形態(tài)，如果比較接近一一棵完全二叉樹(shù)，那么時(shí)間復(fù)雜度在O(logn)左右，如果遇到如圖3這樣的二叉樹(shù)的話，那么時(shí)間復(fù)雜度就會(huì)恢復(fù)到線性的O(n)了。
平衡二叉樹(shù)會(huì)很好的解決如圖3這種情況。
插入函數(shù)的代碼如下：
//插入
template<class T>
void BST<T>::insertpri(TreeNode<T>* &node,T x)
{
if(node==NULL)//如果節(jié)點(diǎn)為空,就在此節(jié)點(diǎn)處加入x信息
{
node=new TreeNode<T>();
node->data=x;
return;
}
if(node->data>x)//如果x小于節(jié)點(diǎn)的值,就繼續(xù)在節(jié)點(diǎn)的左子樹(shù)中插入x
{
insertpri(node->lson,x);
}
else if(node->data<x)//如果x大于節(jié)點(diǎn)的值,就繼續(xù)在節(jié)點(diǎn)的右子樹(shù)中插入x
{
insertpri(node->rson,x);
}
else ++(node->freq);//如果相等,就把頻率加1
}
//插入接口
template<class T>
void BST<T>::insert(T x)
{
insertpri(root,x);
}
第四步：查找
查找的功能和插入差不多一樣，按照插入那樣的方式遞歸下去，如果找到了，就返回這個(gè)節(jié)點(diǎn)的地址，如果沒(méi)有找到，就返回NULL。
代碼如下：
//查找
template<class T>
TreeNode<T>* BST<T>::findpri(TreeNode<T>* node,T x)
{
if(node==NULL)//如果節(jié)點(diǎn)為空說(shuō)明沒(méi)找到,返回NULL
{
return NULL;
}
if(node->data>x)//如果x小于節(jié)點(diǎn)的值,就繼續(xù)在節(jié)點(diǎn)的左子樹(shù)中查找x
{
return findpri(node->lson,x);
}
else if(node->data<x)//如果x大于節(jié)點(diǎn)的值,就繼續(xù)在節(jié)點(diǎn)的左子樹(shù)中查找x
{
return findpri(node->rson,x);
}
else return node;//如果相等,就找到了此節(jié)點(diǎn)
}
//查找接口
template<class T>
TreeNode<T>* BST<T>::find(T x)
{
return findpri(root,x);
}
第五步：刪除
刪除會(huì)麻煩一點(diǎn)，如果是葉子節(jié)點(diǎn)的話，直接刪除就可以了。如果只有一個(gè)孩子的話，就讓它的父親指向它的兒子，然后刪除這個(gè)節(jié)點(diǎn)。圖4顯示了一棵初始樹(shù)和4節(jié)點(diǎn)被刪除后的結(jié)果。先用一個(gè)臨時(shí)指針指向4節(jié)點(diǎn)，再讓4節(jié)點(diǎn)的地址指向它的孩子，這個(gè)時(shí)候2節(jié)點(diǎn)的右兒子就變成了3節(jié)點(diǎn)，最后刪除臨時(shí)節(jié)點(diǎn)指向的空間，也就是4節(jié)點(diǎn)。
刪除有兩個(gè)兒子的節(jié)點(diǎn)會(huì)比較復(fù)雜一些。一般的刪除策略是用其右子樹(shù)最小的數(shù)據(jù)代替該節(jié)點(diǎn)的數(shù)據(jù)并遞歸的刪除掉右子樹(shù)中最小數(shù)據(jù)的節(jié)點(diǎn)。因?yàn)橛易訕?shù)中數(shù)據(jù)最小的節(jié)點(diǎn)肯定沒(méi)有左兒子，所以刪除的時(shí)候容易一些。圖5顯示了一棵初始樹(shù)和2節(jié)點(diǎn)被刪除后的結(jié)果。首先在2節(jié)點(diǎn)的右子樹(shù)中找到最小的節(jié)點(diǎn)3，然后把3的數(shù)據(jù)賦值給2節(jié)點(diǎn)，這個(gè)時(shí)候2節(jié)點(diǎn)的數(shù)據(jù)變?yōu)?/span>3，然后的工作就是刪除右子樹(shù)中的3節(jié)點(diǎn)了，采用遞歸刪除。
我們發(fā)現(xiàn)對(duì)2節(jié)點(diǎn)右子樹(shù)的查找進(jìn)行了兩遍，第一遍找到最小節(jié)點(diǎn)并賦值，第二遍刪除這個(gè)最小的節(jié)點(diǎn)，這樣的效率并不是很高。你能不能寫出只查找一次就可以實(shí)現(xiàn)賦值和刪除兩個(gè)功能的函數(shù)呢？
如果刪除的次數(shù)不是很多的話，有一種刪除的方法會(huì)比較快一點(diǎn)，名字叫懶惰刪除法：當(dāng)一個(gè)元素要被刪除時(shí)，它仍留在樹(shù)中，只是多了一個(gè)刪除的標(biāo)記。這種方法的優(yōu)點(diǎn)是刪除那一步的時(shí)間開(kāi)銷就可以避免了，如果重新插入刪除的節(jié)點(diǎn)的話，插入時(shí)也避免了分配空間的時(shí)間開(kāi)銷。缺點(diǎn)是樹(shù)的深度會(huì)增加，查找的時(shí)間復(fù)雜度會(huì)增加，插入的時(shí)間可能會(huì)增加。
刪除函數(shù)代碼如下：
//刪除
template<class T>
void BST<T>::Deletepri(TreeNode<T>* &node,T x)
{
if(node==NULL) return ;//沒(méi)有找到值是x的節(jié)點(diǎn)
if(x < node->data)
Deletepri(node->lson,x);//如果x小于節(jié)點(diǎn)的值,就繼續(xù)在節(jié)點(diǎn)的左子樹(shù)中刪除x
else if(x > node->data)
Deletepri(node->rson,x);//如果x大于節(jié)點(diǎn)的值,就繼續(xù)在節(jié)點(diǎn)的右子樹(shù)中刪除x
else//如果相等,此節(jié)點(diǎn)就是要?jiǎng)h除的節(jié)點(diǎn)
{
if(node->lson&&node->rson)//此節(jié)點(diǎn)有兩個(gè)兒子
{
TreeNode<T>* temp=node->rson;//temp指向節(jié)點(diǎn)的右兒子
while(temp->lson!=NULL) temp=temp->lson;//找到右子樹(shù)中值最小的節(jié)點(diǎn)
//把右子樹(shù)中最小節(jié)點(diǎn)的值賦值給本節(jié)點(diǎn)
node->data=temp->data;
node->freq=temp->freq;
Deletepri(node->rson,temp->data);//刪除右子樹(shù)中最小值的節(jié)點(diǎn)
}
else//此節(jié)點(diǎn)有1個(gè)或0個(gè)兒子
{
TreeNode<T>* temp=node;
if(node->lson==NULL)//有右兒子或者沒(méi)有兒子
node=node->rson;
else if(node->rson==NULL)//有左兒子
node=node->lson;
delete(temp);
}
}
return;
}
//刪除接口
template<class T>
void BST<T>::Delete(T x)
{
Deletepri(root,x);
}
第六步：中序遍歷
遍歷的方法和二叉樹(shù)的方法一樣，寫這個(gè)方法的目的呢，是輸出這個(gè)二叉查找樹(shù)的有序序列。
代碼如下：
//中序遍歷函數(shù)
template<class T>
void BST<T>::insubtree(TreeNode<T>* node)
{
if(node==NULL) return;
insubtree(node->lson);//先遍歷左子樹(shù)
cout<<node->data<<" ";//輸出根節(jié)點(diǎn)
insubtree(node->rson);//再遍歷右子樹(shù)
}
//中序遍歷接口
template<class T>
void BST<T>::traversal()
{
insubtree(root);
}
到此，整個(gè)代碼就完成了，代碼中肯定有很多不完善的地方請(qǐng)指出，我會(huì)加以完善，謝謝。
對(duì)于二叉查找樹(shù)不穩(wěn)定的時(shí)間復(fù)雜度的解決方案有不少，平衡二叉樹(shù)、伸展樹(shù)和紅黑樹(shù)都可以解決這個(gè)問(wèn)題，但效果是不一樣的。