二叉排序樹
二叉排序樹是為了實作資料的有序排列，并可方便的對樹中的資料進行插入和洗掉操作，提高查找效率，
性質：
- 若它的左子樹不為空，則左子樹上的所有值均小于根結點的值
- 若它的右子樹不為空，則右子樹上的所有值均大于根結點的值
- 它的左右子樹也分別為二叉排序樹
下面說說二叉排序樹的查找，插入，洗掉操作實作，
二叉排序樹的結點結構：
template<class T>
class BTNode
{
public:
//資料域
T data;
//指標域
BTNode<T> *lchild,*rchild;
public:
//建構式
BTNode(T D,BTNode<T> *l = NULL,BTNode<T> *r=NULL) : data(D),lchild(l),rchild(r) {}
};
查找
二叉排序樹是一個有序的二叉樹，其左子樹永遠比根節點的值小，右子樹用于比根節點的值大，因此我們可以使用遞回技術，如果key<p->data，則在p的左子樹里面繼續尋找；若key>p->data則在p的右子樹里面繼續尋找；直到key=p->data；否則表示未搜索到，退出函式，實作程序如下圖：
代碼實作
/*
1、在rt中遞回查找key是否存在，若不存在回傳false
2、f指向rt結點的雙親，若rt為根節點，則f=NULL
3、若key存在，則回傳true，p指向該資料值為key的結點
4、若key不存在，回傳false，p指向訪問的最后一個節點
*/
bool SearchBST(BTNode<T> *rt, T key, BTNode<T> *&p = NULL, BTNode<T> *f = NULL)
{
if (!rt) //查找失敗
{
p = f;
return false;
}
else if (key == rt->data) //查找成功
{
p = rt;
return true;
}
else if (key > rt->data)
{
return SearchBST(rt->rchild, key, p, rt); //在右子樹繼續查找
}
else
{
return SearchBST(rt->lchild, key, p, rt); //在左子樹繼續查找
}
}
識訓：函式的引數串列若有指標，并且呼叫函式時，用的就是一個指標進行傳遞，則進行的是值傳遞，而*&a可以避免這種現象，這時進行的是地址傳遞，
插入
插入的關鍵是，在插入元素后還要繼續保持二叉樹的有序性，實作程序如下圖：
代碼實作：
/*
1、先搜索二叉樹rt中是否存在值key
2、若存在則回傳false，不存在則插入
*/
bool Insert(BTNode<T> *&rt, T key)
{
BTNode<T> *p = NULL;
if (!this->SearchBST(rt, key, p))//未存在key
{
BTNode<T> *s = new BTNode<T>(key, NULL, NULL);
if (!p)//p為空，即根節點為空
{
rt = s;//令根結點等于s
}
else if (key < p->data)
{
p->lchild = s;//key小于p->data，將p的左孩子置為s
}
else
{
p->rchild = s;//key大于p->data，將p的右孩子置為s
}
return true;
}
else
{
return false;
}
}
洗掉
二叉排序樹的難點是洗掉操作，
洗掉結點分三種情況：
- 結點沒有左右孩子；
- 結點只有左子樹或右子樹；
- 結點左右子樹均有；
結點沒有左右孩子：
解決辦法：洗掉該結點，將該結點的雙親指標域置為NULL
結點只有左子樹或右子樹：
解決辦法：洗掉該結點，將該結點的雙親指標域指向該結點的左子樹或右子樹，
結點左右子樹均有：
解決辦法：保留該結點，將該結點的資料域改為該結點直接前驅（或直接后繼）結點的值，洗掉該結點的直接前驅結點，
實作程序如下圖：
代碼實作：
/*
若二叉樹rt中存在key，在洗掉結點，并回傳true，否則回傳false
*/
bool DeleteBST(BTNode<T> *&rt,T key)//地址傳遞
{
if(!rt)
{
//未找到
return false;
}
else
{
if(rt->data=https://www.cnblogs.com/cqy-wt1124/p/=key)
{
//找到key
return Delete(rt);//rt只是其雙親指標域的一個別名
}
else if (rt->data>key)
{
return DeleteBST(rt->lchild,key);
}
else
{
return DeleteBST(rt->rchild,key);
}
}
}
Delete函式實作：
bool Delete(BTNode<T> *&p)//地址傳遞，p只是別名
{
BTNode<T> *q;
//只存在右子樹，或右子樹也不存在
if(!p->lchild)
{
q=p;
p=p->rchild;//重接其右子樹
delete q;//洗掉原來的結點
}
//只存在左子樹
else if (!p->rchild)
{
q=p;
p=p->lchild;
delete q;
}
//左右子樹均存在
else
{
BTNode<T> *s=p;
q=p->lchild;
//尋找其直接前驅結點
while(q->rchild)
{
s=q;//s為q的雙親
q=q->rchild;
}
//將q的值賦給p
p->data=https://www.cnblogs.com/cqy-wt1124/p/q->data;
if(s!=p)//若p和q的雙親指向不等
{
s->rchild=q->lchild;//重接s的右子樹
}
else
{
s->lchild=q->lchild;//重接s的左子樹
}
delete q;
}
return true;
}
C++代碼實作：
#include <iostream>
using namespace std;
//二叉樹結點
template <class T>
struct BTNode
{
T data; //存盤資料
BTNode<T> *lchild, *rchild; //左右孩子指標
BTNode(T D, BTNode<T> *l = NULL, BTNode<T> *r = NULL) : data(D), lchild(l), rchild(r) {}
};
//二叉樹
template <class T>
class BST
{
//屬性值
private:
//根節點指標
BTNode<T> *root;
//查找結點
bool SearchBSTP(BTNode<T> *rt, T key, BTNode<T> *&p = NULL, BTNode<T> *f = NULL)
{
if (!rt) //查找失敗
{
p = f;
return false;
}
else if (key == rt->data) //查找成功
{
p = rt;
return true;
}
else if (key > rt->data)
{
return SearchBSTP(rt->rchild, key, p, rt); //在右子樹繼續查找
}
else
{
return SearchBSTP(rt->lchild, key, p, rt); //在左子樹繼續查找
}
}
//插入結點
bool Insert(BTNode<T> *&rt, T key)
{
BTNode<T> *p = NULL;
if (!this->SearchBSTP(rt, key, p))
{
BTNode<T> *s = new BTNode<T>(key, NULL, NULL);
if (!p)
{
rt = s;
}
else if (key < p->data)
{
p->lchild = s;
}
else
{
p->rchild = s;
}
return true;
}
else
{
return false;
}
}
//洗掉結點
bool Delete(BTNode<T> *&p)
{
BTNode<T> *q;
if(!p->lchild)
{
q=p;
p=p->rchild;
delete q;
}
else if (!p->rchild)
{
q=p;
p=p->lchild;
delete q;
}
else
{
BTNode<T> *s=p;
q=p->lchild;
while(q->rchild)
{
s=q;
q=q->rchild;
}
p->data=https://www.cnblogs.com/cqy-wt1124/p/q->data;
if(s!=p)
{
s->rchild=q->lchild;
}
else
{
s->lchild=q->lchild;
}
delete q;
}
return true;
}
bool DeleteBSTP(BTNode *&rt,T key)
{
if(!rt)
{
//未找到
return false;
}
else
{
if(rt->data==key)
{
//找到key
return Delete(rt);
}
else if (rt->data>key)
{
return DeleteBSTP(rt->lchild,key);
}
else
{
return DeleteBSTP(rt->rchild,key);
}
}
}
//中序遍歷
void InOrder(BTNode *rt)
{
if(rt)
{
InOrder(rt->lchild);
cout<data<<" ";
InOrder(rt->rchild);
}
}
//洗掉二叉樹
void Destory(BTNode *&rt)
{
if(rt)
{
Destory(rt->lchild);
Destory(rt->rchild);
delete rt;
}
}
//行為屬性
public:
//建構式
BST(BTNode *r = NULL) : root(r) {}
//拷貝建構式
BST(const BST &bt) : root(NULL)
{
}
//洗掉二叉樹
void Destory()
{
this->Destory(this->root);
this->root=NULL;
}
//解構式
~BST()
{
this->Destory();
}
//獲得根指標
BTNode *Getroot()
{
return this->root;
}
//搜索值
//并將
bool SearchBST(T key, BTNode *p = NULL)
{
return this->SearchBSTP(this->root, key, p, NULL);
}
//插入結點，順序插入
/*1、先判斷此值是否存在，若存在，則回傳true
2、若不存在，創造結點s，并順序插入二叉樹中
3、若不存在，則存在指標p指向查找路徑的最后一個結點
4、判斷插入值和指標p指向的值的大小，若key>p->data,則p->rchild=s;
否則p->lchild=s;
*/
bool InsertBST(T key)
{
return this->Insert(this->root, key);
}
//shanchujiedian
bool DeleteBST(T key)
{
return this->DeleteBSTP(this->root, key);
}
void InOrder()
{
this->InOrder(this->root);
}
};
int main()
{
BST temp;
int a[] = {62,58,88,47,73,99,35,51,93,29,37,49,56,36,48,50};
for (int i = 0; i < 16; i++)
{
temp.InsertBST(a[i]);
}
temp.InOrder();
cout< *p;
cout << "查找結果：" << temp.SearchBST(51) << endl;
temp.DeleteBST(62);
cout << "查找結果：" << temp.SearchBST(50) << endl;
temp.InOrder();
cout< 轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/30645.html
標籤：C++
上一篇：透徹理解C++11 移動語意：右值、右值參考、std::move、std::forward
下一篇：圖