考綱中，二叉排序樹在“查找”章節(jié)，要求為：二叉排序樹及其基本操作。

其基本操作有：查找操作，插入操作，刪除操作

---

一：定義

二叉排序樹（Binary Sort Tree），又稱二叉查找樹，它是一顆空樹，或者是具有以下性質(zhì)的二叉樹：

若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值。

若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值。

它的左右子樹也都是二叉排序樹

二：首先定義一個(gè)二叉樹的結(jié)構(gòu)

1 struct BSTree 2 { 3 int data; 4 BSTree *lchild, *rchild; 5 BSTree(int d = 0, BSTree *l = NULL, BSTree *r = NULL) 6 { 7 data = d; 8 lchild = l; 9 rchild = r; 10 } 11 };

三：建立一個(gè)二叉排序樹

二叉排序樹的建立，其實(shí)就是由一個(gè)空樹，一個(gè)一個(gè)的插入數(shù)據(jù)形成的，也就是需要插入操作

而在插入操作中，我們需要找到插入數(shù)據(jù)合適的位置，這里又可以看做是查找操作

插入操作有遞歸和循環(huán)兩種寫法

循環(huán)寫法：

void insertTree1(BSTree* &root, int key) {if(root == NULL){BSTree *s = new BSTree(key);root = s;return;}BSTree *t = root;while(t->data != key){if(key > t->data && t->rchild != NULL)t = t->rchild;else if(key < t->data && t->lchild != NULL)t = t->lchild;else if(key > t->data && t->rchild == NULL){BSTree *s = new BSTree(key);t->rchild = s;}else if(key < t->data && t->lchild == NULL){BSTree *s = new BSTree(key);t->lchild = s;}} }

遞歸寫法：

void insertTree2(BSTree* &root, int key) {if(root == NULL){BSTree *s = new BSTree(key);root = s;return;}if(key > root->data)insertTree2(root->rchild, key);elseinsertTree2(root->lchild,key); }

查找操作由插入操作簡單修改得到，不再上代碼

四：刪除操作（重點(diǎn)）

刪除節(jié)點(diǎn)有三種情況：

要?jiǎng)h除的點(diǎn)為葉子節(jié)點(diǎn)，直接刪除即可；

要?jiǎng)h除的點(diǎn)只有左子樹，或只有右子樹，刪除節(jié)點(diǎn)后，將左子樹或右子樹整體移動(dòng)到被刪除節(jié)點(diǎn)的位置即可；

要?jiǎng)h除的節(jié)點(diǎn)即有左子樹，又有右子樹；

第一、二種情況可以合并為第二種，第三種情況比較復(fù)雜

根據(jù)二叉排序樹的定義，節(jié)點(diǎn)刪除后，這個(gè)位置應(yīng)該由與它大小相鄰的數(shù)代替，對(duì)于下面這張圖：

假設(shè)要?jiǎng)h除的節(jié)點(diǎn)為47，那么能夠代替這個(gè)位置的就是37和48，可以發(fā)現(xiàn)，這兩個(gè)數(shù)都有一個(gè)特點(diǎn)，37為47的左子樹中的最右子樹，48為47的右子樹的最左子樹

基于此可以這樣做：假定每次都用較小的數(shù)來代替，也就是37，此時(shí)51這邊整體就不用動(dòng)了，只需要將37移動(dòng)到47的位置，然后將37的整個(gè)左子樹移動(dòng)到37原來的位置

代碼：

void Delete(BSTree* &node) {if(node->lchild == NULL){BSTree *temp = node;node = node->rchild;delete(temp);}else if(node->rchild == NULL){BSTree *temp = node;node = node->lchild;delete(temp);}else //用與該節(jié)點(diǎn)臨近且小于的點(diǎn)代替 {BSTree *newnode = node->lchild;BSTree *temp = node;while(newnode->rchild != NULL){temp = newnode;newnode = newnode->rchild;}node->data = newnode->data;if(temp != node)temp->rchild = newnode->lchild;elsetemp->lchild = newnode->lchild;delete(newnode);} } void DeleteTree(BSTree* &root, int key) {if(root == NULL)return;if(key == root->data)Delete(root);else if(key > root->data)return DeleteTree(root->rchild, key);elsereturn DeleteTree(root->lchild, key); }

五：遍歷及測(cè)試數(shù)據(jù)

建好二叉排序樹后，使用中序遍歷，即可得到一個(gè)排好序的數(shù)列

void InOrder(BSTree *root) {if(root != NULL){InOrder(root->lchild);cout << root->data << " ";InOrder(root->rchild);} }

測(cè)試數(shù)據(jù)

int main() {int a[12] = {29, 36, 62, 88, 58, 47, 35, 73, 51, 99, 37, 93};BSTree *root = NULL;for(int i=0; i<12; i++){insertTree2(root, a[i]);}InOrder(root);cout << endl;DeleteTree(root, 47);InOrder(root);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/flyuz/p/9484100.html

總結(jié)

以上是生活随笔為你收集整理的833系列——二叉排序树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。