二叉搜索樹
二叉查找樹（Binary Search Tree,BST），又稱為二叉搜索樹，二叉排序樹，是一種對(duì)查找和排序都有用的特殊二叉樹。
二叉查找樹或是空樹，或是滿足如下性質(zhì)的二叉樹：
1）若其左子樹非空，則左子樹 上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；
2）若其右子樹非空，則右子樹上所有 結(jié)點(diǎn)的值均大于等于根結(jié)點(diǎn)的值；
3）其左右子樹本省又各是一顆二叉查找樹。
二叉查找樹的特性：左子樹 < 根 < 右子樹，即二叉查找樹的中序遍歷是一個(gè)遞增序列。??
1.二叉查找樹的查找
因?yàn)槎娌檎覙涞闹行虮闅v有序性，所以查找和二分查找類似，每次縮小查找范圍，查找的效率較高。
算法步驟：
1）若二叉查找樹為空，查找失敗，返回空指針。
2）若二叉查找樹非空，將待查找關(guān)鍵字x 與根節(jié)點(diǎn)的關(guān)鍵字 T-> data 比較：
若 x == T->data,查找成功，返回根結(jié)點(diǎn)指針；
若 x < T->data, 則遞歸查找左子樹；
若 x > T-> data,則遞歸查找右子樹。
算法實(shí)現(xiàn)：
BSTree SearchBST(BSTree T, ElemType key){? ? ?//二叉排序樹的遞歸查找
????if(! T || key == T->data)
????????return T;
????else if (key < T->data)
????????return SearchBST(T->lchild, key);
? ?else
????????return SearchBST(T->rchild,key);
}
2.二叉查找樹的插入
因?yàn)槎娌檎覙涞闹行虮闅v有序性，首先要查找待插入關(guān)鍵字的插入位置，當(dāng)查找不成功時(shí)，將待插入關(guān)鍵字作為新的葉子結(jié)點(diǎn)插入到最后一個(gè)查找結(jié)點(diǎn)的左孩子或右孩子。
算法步驟：
1）若二叉查找樹為空，創(chuàng)建一個(gè)新的結(jié)點(diǎn)s,將待插入關(guān)鍵字放入新結(jié)點(diǎn)的數(shù)據(jù)域，s結(jié)點(diǎn)作為根結(jié)點(diǎn)，左右子樹均為空；
2）若二叉查找樹非空，將待查找關(guān)鍵字x 與根結(jié)點(diǎn)的關(guān)鍵字 T->data 比較：
????若 x < T-> data,則將x 插入到左子樹；
????若 x > T-> data,則將x插入到右子樹。
算法實(shí)現(xiàn)：
void InsertBST(BSTree &T, ElemType e){? ? //二叉排序樹的插入
?????if(!T){
????????BSTree s = new BSTNode;
? ? ? ? s->data = e;
????????s->lchild = s->rchild = NULL;
????????T = s;
}
else if(e < T-> data)
????????InsertBST(T->lchild,e);
else if(e > T-> data)
????????InsertBST(T ->rchild,e);
}
算法分析：
二叉查找樹的插入需要先查找插入位置，插入本身只需要常數(shù)時(shí)間，但查找插入位置的時(shí)間復(fù)雜度為O(logn) 。
3.二叉查找樹的創(chuàng)建
二叉查找樹的創(chuàng)建可以從空數(shù)開始，按照輸入關(guān)鍵字的順序依次進(jìn)行插入操作，最終得到一棵二叉樹。
算法步驟:
1) 初始化二叉查找樹為空樹，T = NULL;
2) 輸入一個(gè)關(guān)鍵字 x ,將x 插入到二叉查找樹 T中；
3）重復(fù)步驟 2），直到關(guān)鍵字輸入完畢。
算法實(shí)現(xiàn)：
void CreateBST(BSTree & T){
????????T = NULL;
????????ElemType e;
????????cin >> e;
????????while(e != ENDFLAG){? ?//ENGFALG為自定義常量，作為輸入結(jié)束標(biāo)志
? ? ? ? InsertBST(T,e);? ? //插入二叉排序樹 T 中
? ? ? ? cin >> e;
}
}
算法分析：
二叉查找樹的創(chuàng)建，需要n次插入，每次需要O(logn)時(shí)間，因此創(chuàng)建二叉查找樹的時(shí)間復(fù)雜度為O(nlogn)。相當(dāng)于把一個(gè)無序序列轉(zhuǎn)換為一個(gè)有序序列的排序過程。實(shí)質(zhì)上，創(chuàng)建二叉查找樹的過程和快速排序一樣，根節(jié)點(diǎn)相當(dāng)于快速排序中的基準(zhǔn)元素，左右兩部分劃分的情況取決于基準(zhǔn)元素，創(chuàng)建二叉查找樹時(shí)，輸入序列的次序不同，創(chuàng)建的二叉查找樹是不同的。
4.二叉查找樹的刪除
首先要在二叉查找樹中找到待刪除的結(jié)點(diǎn)，然后執(zhí)行刪除操作。假設(shè)指針p指向待刪除的結(jié)點(diǎn)，指針f指向p的雙親結(jié)點(diǎn)。根據(jù)待刪除結(jié)點(diǎn)所在位置的不同，刪除操作處理方法也不同，可分為三種情況：
（1）被刪除結(jié)點(diǎn)左子樹為空
如果被刪除結(jié)點(diǎn)左子樹為空，則令其右子樹子承父業(yè)代替其位置即可。例如，在二叉樹找樹中刪除P結(jié)點(diǎn)，如下圖所示：
（2）被刪除結(jié)點(diǎn)右子樹為空
如果被刪除結(jié)點(diǎn)右子樹為空，則令其左子樹子承父業(yè)代替其位置即可。
（3）被刪除結(jié)點(diǎn)左右子樹均不空
如果被刪除結(jié)點(diǎn)的左子樹和右子樹均不空，則沒辦法再使用子承父業(yè)的方法了。根據(jù)二叉查找樹的中序有序性，刪除該結(jié)點(diǎn)時(shí)，可以用其直接前驅(qū)（或直接后繼）代替其位置，讓然后刪除其直接前驅(qū)（或者直接后繼）即可。那么中序遍歷序列中，一個(gè)結(jié)點(diǎn)的直接前驅(qū)（或直接后繼）是哪個(gè)結(jié)點(diǎn)呢？
????直接前驅(qū)：中序遍歷中，結(jié)點(diǎn)p 的直接前驅(qū)為其左子樹的最右結(jié)點(diǎn)。即沿著p的左子樹一直訪問其右子樹，直到?jīng)]有右子樹，就找到了最右結(jié)點(diǎn)。如圖（a）所示，s指向p的直接前驅(qū)，q指向s的雙親。
????直接后繼：中序遍歷中，結(jié)點(diǎn)p的直接后繼為其右子樹的最左結(jié)點(diǎn)。如圖（b）所示。s指向p的直接后繼，q指向s的雙親。
算法步驟：
1）在二叉查找樹中查找待刪除關(guān)鍵字的位置，p指向待 刪除結(jié)點(diǎn)，f指向p的雙親結(jié)點(diǎn)，如果查找失敗，則返回。
2）如果查找成功，則分三種情況進(jìn)行刪除操作：
*如果被刪除結(jié)點(diǎn)左子樹為空，則令其右子樹子承父業(yè)代替其位置即可；
*如果被刪除結(jié)點(diǎn)右子樹為空，則令其左子樹子承父業(yè)代替其位置即可；
*如果被刪除結(jié)點(diǎn)右子樹均不空，則令其直接前驅(qū)（或直接后驅(qū)）代替之，再刪除其直接前驅(qū)（或直接后繼）。
算法分析：
二叉查找樹的刪除，主要是查找的過程，需要O(logn)時(shí)間，刪除的過程中，如果需要找被刪結(jié)點(diǎn)的前驅(qū)，也需要O(logn)時(shí)間，二叉查找樹的刪除時(shí)間復(fù)雜度為O(logn)。
