二叉排序樹又稱為二叉查找樹，對樹中任意一個結(jié)點來說，如果它的左子樹不為空，那么左子樹中的數(shù)一定小于該結(jié)點中的數(shù)，同理，非空右子樹中的數(shù)一定大于該結(jié)點中的數(shù)。（也可以設(shè)置為左大右小）

查找

在二叉排序樹中查找一個數(shù)的算法如下:

bTree* searchT(bTree* T, int key) {if (T == NULL)return NULL;if (T->data == key)return T;else if (T->data < key)return searchT((T->rc, key);elsereturn searchT(T->lc, key); }

插入

如何構(gòu)造一棵二叉排序樹，可以通過插入一個個結(jié)點來實現(xiàn)，下面是在二叉樹中插入結(jié)點的算法：

bool insertBtree(bTree* T, int ele) {if (T == NULL)//空結(jié)點{T = new bTree;T->data = ele;T->lc = T->rc = NULL;return true;}bTree* f;bTree* temp = new bTree;while (T!=NULL&&T->data!=ele){f = T;if (T->data < ele)T = T->rc;else(T->data > ele)T = T->lc;}if (T)return false;//樹中已存在該數(shù)據(jù)temp->data = ele;temp->lc = temp->rc = NULL;if (ele > f->data)f->rc = temp;elsef->lc = temp;return true; }

刪除

刪除二叉樹結(jié)點a
1，若a為葉子結(jié)點，直接刪除
2，若a只有一個子樹，用其子樹代替其位置
3，若a有兩個子樹，有一個比較好用的方法：因為二叉樹中任何一個結(jié)點及其子樹的排序結(jié)果都為左-根-右，它符合中序遍歷的順序，故如果要刪除a，可以用中序遍歷中a的直接前驅(qū)代替a或者用a的直接后繼代替a。

總結(jié)

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

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