二叉搜索樹(shù)

一棵二叉樹(shù)，可以為空；如果不為空，滿足以下性質(zhì)：
1. 非空左子樹(shù)的所有鍵值小于其根結(jié)點(diǎn)的鍵值。
2. 非空右子樹(shù)的所有鍵值大于其根結(jié)點(diǎn)的鍵值。
3. 左、右子樹(shù)都是二叉搜索樹(shù)。

二叉搜索樹(shù)的插入，刪除，查找

頭文件

#include "iostream" #include "string.h" #include "sstream"using namespace std;//二叉查找樹(shù)節(jié)點(diǎn)信息 template<class T> class TreeNode { public:TreeNode():lson(NULL),rson(NULL),freq(1){}//初始化T data;//值unsigned int freq;//頻率TreeNode* lson;//指向左兒子的坐標(biāo)TreeNode* rson;//指向右兒子的坐標(biāo) };//二叉查找樹(shù)類的屬性和方法聲明 template<class T> class BST { private:TreeNode<T>* root;//根節(jié)點(diǎn)void insertpri(TreeNode<T>* &node,T x);//插入TreeNode<T>* findpri(TreeNode<T>* node,T x);//void insubtree(TreeNode<T>* node);//中序遍歷void Deletepri(TreeNode<T>* &node,T x);//刪除TreeNode<T>* findMinpri(TreeNode<T>* node);TreeNode<T>* findMaxpri(TreeNode<T>* node); public:BST():root(NULL){}void insert(T x);//插入接口TreeNode<T>* find(T x);//查找接口void Delete(T x);//刪除接口void traversal();//遍歷接口TreeNode<T>* findMin();TreeNode<T>* findMax();};

實(shí)現(xiàn)

#include "head.h"template<class T> void BST<T>::insertpri(TreeNode<T>* &node,T x) {if(node==NULL)//如果節(jié)點(diǎn)為空,就在此節(jié)點(diǎn)處加入x信息{node=new TreeNode<T>();node->data=x;//cout<<x;return;}if (node->data>x){insertpri(node->lson,x);}else if (node->data<x){insertpri(node->rson,x);}else{node->freq++;}}//插入接口 template<class T> void BST<T>::insert(T x) {insertpri(root,x); }template<class T> TreeNode<T>* BST<T>::findpri(TreeNode<T>* node,T x) {if (node==NULL){return NULL;}if (node->data>x){return findpri(node->lson);}else if (node->data<x){return findpri(node->rson);}else{return node;} }template<class T> TreeNode<T>* BST<T>::find(T x) {return findpri(root,x); }template<class T> TreeNode<T>* BST<T>::findMinpri(TreeNode<T>* node) {if (node==NULL){return NULL;}if (node->lson!=NULL){return findMinpri(node->lson);}else{return node;} }template<class T> TreeNode<T>* BST<T>::findMin() {return findMinpri(root); }template<class T> void BST<T>::Deletepri(TreeNode<T>* &node,T x) {if(node==NULL) return ;//沒(méi)有找到值是x的節(jié)點(diǎn)if(x < node->data)Deletepri(node->lson,x);//如果x小于節(jié)點(diǎn)的值,就繼續(xù)在節(jié)點(diǎn)的左子樹(shù)中刪除xelse if(x > node->data)Deletepri(node->rson,x);//如果x大于節(jié)點(diǎn)的值,就繼續(xù)在節(jié)點(diǎn)的右子樹(shù)中刪除xelse//如果相等,此節(jié)點(diǎn)就是要?jiǎng)h除的節(jié)點(diǎn){if(node->lson&&node->rson)//此節(jié)點(diǎn)有兩個(gè)兒子{TreeNode<T>* temp=node->rson;//temp指向節(jié)點(diǎn)的右兒子while(temp->lson!=NULL) temp=temp->lson;//找到右子樹(shù)中值最小的節(jié)點(diǎn)//把右子樹(shù)中最小節(jié)點(diǎn)的值賦值給本節(jié)點(diǎn)node->data=temp->data;node->freq=temp->freq;Deletepri(node->rson,temp->data);//刪除右子樹(shù)中最小值的節(jié)點(diǎn)}else//此節(jié)點(diǎn)有1個(gè)或0個(gè)兒子{TreeNode<T>* temp=node;if(node->lson==NULL)//有右兒子或者沒(méi)有兒子node=node->rson;else if(node->rson==NULL)//有左兒子node=node->lson;delete(temp);}}return;}template<class T> void BST<T>::Delete(T x) {Deletepri(root,x); }//中序遍歷函數(shù) template<class T> void BST<T>::insubtree(TreeNode<T>* node) {if(node==NULL) return;insubtree(node->lson);//先遍歷左子樹(shù)cout<<node->data<<" ";//輸出根節(jié)點(diǎn)insubtree(node->rson);//再遍歷右子樹(shù) } //中序遍歷接口 template<class T> void BST<T>::traversal() {insubtree(root); }int main() {BST<int>* bst=new BST<int>();int temp;int inputNumber;cout<<"1.插入數(shù)據(jù)\n2.查找數(shù)據(jù)\n3.查找最小\n4.刪除指定數(shù)據(jù)\n5.中序遍歷\n";bst->insert(66);bst->insert(55);bst->insert(77);bst->insert(44);while (true){cout<<"請(qǐng)輸入指令\n";cin>>temp;switch (temp){case 1:cin>>inputNumber;bst->insert(inputNumber);break;case 2:break;case 3:cout<<"結(jié)果為:";cout<<bst->findMin()->data;break;case 4:cin>>inputNumber;bst->Delete(inputNumber);break;case 5:bst->traversal();break;default:break;}}system("pause");return 0;}

參考鏈接

一步一步寫(xiě)二叉查找樹(shù) - C小加 - C++博客

效果如下

總結(jié)

以上是生活随笔為你收集整理的数据结构之二叉搜索树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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