一、二叉查找樹：

? ? ? ?將小的數(shù)放到左兒子上，將大的數(shù)放到右兒子上，于是建樹成功后，最左邊的是最小的，最右邊的是最大。中序遍歷將會得到從小到大的排序順序。這篇博客會介紹二叉搜索樹的插入和刪除，還有為了方便演示，會介紹到中序遞歸遍歷。

? ? ? 給定數(shù)組8，5，20，3，6，15，7，得到的二叉搜索樹為：

中序遍歷的結(jié)果：3，5，6，7，8，15，20，剛好是從小到大排序的。

二、叉搜索樹的類：

class BSTNode
{
public:
?? ?int val;
?? ?BSTNode *left, *right;
?? ?BSTNode(int key):
?? ??? ?val(key){}
};

class BSTree
{
public:
?? ?BSTNode *root;
?? ?BSTree();
?? ?void insert(int key);
?? ?void InOrder(BSTNode *t);
?? ?void BSTdelete(int key);
private:
?? ?void insert(BSTNode * &t,int key);
?? ?BSTNode *&find_equal(BSTNode *&t, int key);

};

BSTNode類保存BSTree類的一個節(jié)點，BSTNode對象包含一個根節(jié)點。根節(jié)點不存儲數(shù)據(jù)，根節(jié)點的*left開始儲存數(shù)據(jù)，這和頭結(jié)點不存儲數(shù)據(jù)的鏈表很想，這樣可以簡化代碼量。

1、為了根節(jié)點不存儲數(shù)據(jù)，構(gòu)造函數(shù)為：

BSTree::BSTree()
{
?? ?root = new BSTNode(-100000);
}

?

2、插入函數(shù)insert：將小的數(shù)值插入到左兒子上，大的數(shù)值插入到右兒子上，于是采取遞歸操作。

void BSTree::insert(BSTNode * &t, int key)
{
?? ?if (!t)
?? ??? ?t = new BSTNode(key);
?? ?else if (key < t->val)
?? ??? ?insert(t->left, key);
?? ?else if (key > t->val)
?? ??? ?insert(t->right, key);
?? ?else
?? ??? ?cout << "不要插入相同的鍵值" << endl;
}

為了在實際中（我為了中序遍歷書寫簡單些，將*root設(shè)為了共有變量）不訪問根節(jié)點*root，所以需要再加入一個函數(shù)：

/*插入算法*/
void BSTree::insert(int key)
{
?? ?insert(root->left, key);
}

3、刪除函數(shù)delete:刪除分為三種情況

? ?第一種：沒有兒子：比如刪除7所在節(jié)點的時候，直接找到這個節(jié)點刪除

第二種：只有一個兒子：比如刪除20的時候，直接將它的不為空的兒子取代當(dāng)前結(jié)點：

新的搜索樹：

第三種：左右兒子都不為空：比如刪除數(shù)值為5的節(jié)點，此時找到以該節(jié)點為樹根的樹的最右邊的節(jié)點，可以發(fā)現(xiàn)是7。將找到的節(jié)點和原節(jié)點替換（就是將5和7替換），刪掉原來的節(jié)點。

刪除5后的圖：

代碼如下：

/*找到需要刪除數(shù)值所在的節(jié)點*/
BSTNode *&BSTree::find_equal(BSTNode *&t, int key)
{
?? ?if (!t)
?? ?{
?? ??? ?cout << "二叉樹中不存在改數(shù)值！" << endl;
?? ??? ?return t;
?? ?}
?? ?if (key < t->val)
?? ??? ?find_equal(t->left, key);
?? ?else if (key > t->val)
?? ??? ?find_equal(t->right, key);
?? ?else
?? ??? ?return t;

}

void BSTree::BSTdelete(int key)
{
?? ?BSTNode *&p = find_equal(root->left, key);
?? ?if (p)
?? ?{
?? ??? ?BSTNode *t = p;
?? ??? ?if (t->left&&t->right)
?? ??? ?{
?? ??? ??? ?//左右子樹都不為空
?? ??? ??? ?BSTNode *y = t;
?? ??? ??? ?BSTNode *x = t->right;
?? ??? ??? ?while (x->left)
?? ??? ??? ?{
?? ??? ??? ??? ?y = x;
?? ??? ??? ??? ?x = x->left;
?? ??? ??? ?}
?? ??? ??? ?if (y == t) ?//y與t重合的情況
?? ??? ??? ??? ?y->right = x->right;
?? ??? ??? ?else
?? ??? ??? ??? ?y->left = x->left;
?? ??? ??? ?p = x;
?? ??? ??? ?x->left = t->left;
?? ??? ??? ?x->right = t->right;
?? ??? ?}
?? ??? ?else
?? ??? ?{
?? ??? ??? ?//只有一個兒子
?? ??? ??? ?p = t->left ? t->left : t->right;
?? ??? ?}
?? ??? ?delete t;
?? ?}
}

三、總的代碼如下：需要vs2017才能運行，因為之前的版本指針的判斷不同，我沒有對指針進(jìn)行初始化。

// BSTree.cpp : 此文件包含 "main" 函數(shù)。程序執(zhí)行將在此處開始并結(jié)束。 //#include <iostream> #include<queue> using namespace std; class BSTNode { public:int val;BSTNode *left, *right;BSTNode(int key):val(key){} };class BSTree { public:BSTNode *root;BSTree();void insert(int key);void InOrder(BSTNode *t);void BSTdelete(int key); private:void insert(BSTNode * &t,int key);BSTNode *&find_equal(BSTNode *&t, int key);};BSTree::BSTree() {root = new BSTNode(-100000); } void BSTree::insert(BSTNode * &t, int key) {if (!t)t = new BSTNode(key);else if (key < t->val)insert(t->left, key);else if (key > t->val)insert(t->right, key);elsecout << "不要插入相同的鍵值" << endl; }/*插入算法*/ void BSTree::insert(int key) {insert(root->left, key); }void BSTree::InOrder(BSTNode *t) {if (t){InOrder(t->left);cout << "<"<<t->val << ">";InOrder(t->right);} }/*找到需要刪除數(shù)值所在的節(jié)點*/ BSTNode *&BSTree::find_equal(BSTNode *&t, int key) {if (!t){cout << "二叉樹中不存在改數(shù)值！" << endl;return t;}if (key < t->val)find_equal(t->left, key);else if (key > t->val)find_equal(t->right, key);elsereturn t;}void BSTree::BSTdelete(int key) {BSTNode *&p = find_equal(root->left, key);if (p){BSTNode *t = p;if (t->left&&t->right){//左右子樹都不為空BSTNode *y = t;BSTNode *x = t->right;while (x->left){y = x;x = x->left;}if (y == t) //y與t重合的情況y->right = x->right;elsey->left = x->left;p = x;x->left = t->left;x->right = t->right;}else{//只有一個兒子p = t->left ? t->left : t->right;}delete t;} } int main() {BSTree tree;int key,count ;cout << "1、添加樹 2、輸入要刪除的數(shù)字 3、退出" << endl;cin >> count;while (count != 3){if (count == 1){cout << "請輸入要添加的數(shù)據(jù)：" << endl;cin >> key;tree.insert(key);}if (count == 2){cout << "請輸入要刪除的數(shù)據(jù)：" << endl;cin >> key;tree.BSTdelete(key);}cout << "\n搜索樹中序遍歷結(jié)果:" << endl;cout << "{";tree.InOrder(tree.root->left);cout << "}" << endl;cout << "1、添加樹 2、輸入要刪除的數(shù)字 3、退出" << endl;cin >> count;}cout << "退出！" << endl;return 0; }

?

?

?

?

?

?

?

標(biāo)題

?

總結(jié)

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

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