您好,登錄后才能下訂單哦!
這篇文章主要介紹“C++二叉搜索樹BSTree如何使用”的相關(guān)知識,小編通過實際案例向大家展示操作過程,操作方法簡單快捷,實用性強,希望這篇“C++二叉搜索樹BSTree如何使用”文章能幫助大家解決問題。
二叉搜索樹又稱二叉排序樹,它或者是一棵空樹,或者是具有以下性質(zhì)的二叉樹:
若它的左子樹不為空,則左子樹上所有節(jié)點的值都小于根節(jié)點的值
若它的右子樹不為空,則右子樹上所有節(jié)點的值都大于根節(jié)點的值
左<根<右
它的左右子樹也分別為二叉搜索樹
之所以又叫二叉排序樹,是因為二叉搜索樹中序遍歷的結(jié)果是有序的
基于二叉搜索樹的特點,查找一個數(shù)并不難,若根節(jié)點不為空的情況下:
若根節(jié)點key==查找key,直接返回true
若根節(jié)點key>查找key,那得找到更小的,則往左子樹查找
若根節(jié)點key<查找key,那得找到更大的,則往右子樹查找
最多查找高度次,走到空為止,如果還沒找到,則說明這個值不存在,返回false
bool find(const K& key) { Node* cur = _root; while (cur) { if (cur->_key < key) { cur = cur->_right; } else if (cur->_key > key) { cur = cur->_left; } else { return true; } } return false; }
1.樹為空,則直接插入,新增節(jié)點,直接插入root指針即可
2.樹不為空,按二叉搜索樹性質(zhì)查找插入位置,插入新節(jié)點。
(注意:不能插入重復的元素,并且每次插入都是要定位到空節(jié)點的位置;我們先定義一個 cur從root開始,比較元素的大?。喝舨迦氲脑乇犬斍拔恢迷匦【屯笞撸犬斍拔恢迷卮缶屯易?,直到為空,相等就不能插入了;同時定義一個parent去記錄當前 cur的前一個位置,最后判斷cur是parent的左子樹還是右子樹即可)
bool Insert(const K& key) { if (_root == nullptr) { _root = new Node(key); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_key < key) { parent = cur; cur = cur->_right; } else if (cur->_key > key) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(key); if (parent->_key < key) { parent->_right = cur; } else { parent->_left = cur; } return true; }
遞歸走起,同時由于_root是私有的,外部不能訪問,我們可以在類內(nèi)給中序提供一個方法即可,就不需要傳參了
void InOrder() { _InOrder(_root); cout << endl; } private: void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } Node* _root = nullptr;
刪除的情況比較多:
左右都為空:葉子結(jié)點,直接置空并鏈接到空指針
左為空或右為空:進行托孤:只有一個子節(jié)點,刪除自己本身,并鏈接子節(jié)點和父節(jié)點(注意:如果父親是空,也就是要刪除根結(jié)點,此時根節(jié)點沒有父親,單獨判斷一下)
左右都不為空:找出替換節(jié)點:右子樹最小節(jié)點**、**左子樹最大節(jié)點。替換節(jié)點可以作為交換和刪除進行交換,交換后刪除交換節(jié)點、交換節(jié)點要么沒有孩子,要么只有一個孩子可以直接刪除
但是左右都為空可以納入到左為空或右為空的情況
注意:
代碼實現(xiàn):
bool Erase(const K& key) { Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_key < key) { parent = cur; cur = cur->_right; } else if (cur->_key > key) { parent = cur; cur = cur->_left; } else { //左為空 if (cur->_left == nullptr) { //刪除根結(jié)點 //if(parent==nullptr) if (cur == _root) { _root = cur->_right; } else { if (parent->_left == cur) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } } delete cur; } //右為空 else if (cur->_right == nullptr) { if (cur == _root) { _root = cur->_left; } else { if (parent->_left == cur) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete cur; } //左右都不為空,找替換節(jié)點 else { //不能初始化為nullptr Node* parent = cur; //右子樹最小節(jié)點 Node* minRight = cur->_right; while (minRight->_left) { parent = minRight; minRight = minRight->_left; } cur->_key = minRight->_key; //判斷minRight是父親的左還是右 if (minRight == parent->_left) { parent->_left = minRight->_right; } else { parent->_right = minRight->_right; } delete minRight; } return true; } } return false; }
這個比較簡單:蘇醒把,遞歸時刻
bool _FindR(Node* root, const K& key) { if (root == nullptr) return false; else if (root->_key < key) return _FindR(root->_right, key); else if (root->_key > key) return _FindR(root->_left, key); else return true; }
最大的問題是插入之后跟父親進行鏈接,如果直接給root是不可以的,因為root是棧幀里面的參數(shù),只是局部變量:加上引用
bool _InsertR(Node*& root, const K& key) { if (root == nullptr) { root = new Node(key); return true; } else if (root->_key < key) return _InsertR(root->_right, key); else if (root->_key > key) return _InsertR(root->_left, key); else return false; }
遞歸刪除怎么找到父節(jié)點?root = root->_left/ root = root->_right;
bool _EraseR(Node*& root, const K& key) { if (root == nullptr) { return false; } if (root->_key < key) { return _EraseR(root->_right, key); } else if (root->_key > key) { return _EraseR(root->_left, key); } else { Node* del = root; if (root->_right == nullptr) { root = root->_left; } else if (root->_left == nullptr) { root = root->_right; } else { Node* minRight = root->_right; while (minRight->_left) { minRight = minRight->_left; } swap(root->_key, minRight->_key); return _EraseR(root->_right, key); } delete del; return true; } }
最優(yōu)情況下,二叉搜索樹為完全二叉樹,其平均比較次數(shù)為:log2N
最差情況下,二叉搜索樹退化為單支樹,其平均比較次數(shù)為: N/2
1.K模型:K模型即只有key作為關(guān)鍵碼,結(jié)構(gòu)中只需要存儲Key即可,關(guān)鍵碼即為需要搜索到的值,判斷關(guān)鍵字是否存在。
比如:給一個單詞word,判斷該單詞是否拼寫正確,具體方式如下:
以單詞集合中的每個單詞作為key,構(gòu)建一棵二叉搜索樹,在二叉搜索樹中檢索該單詞是否存在,存在則拼寫正確,不存在則拼寫錯誤。
2.KV模型:每一個關(guān)鍵碼key,都有與之對應的值Value,即**<Key, Value>**的鍵值對。
比如英漢詞典就是英文與中文的對應關(guān)系,通過英文可以快速找到與其對應的中文,英文單詞與其對應的中文<word, chinese>就構(gòu)成一種鍵值對;再比如統(tǒng)計單詞次數(shù),統(tǒng)計成功后,給定單詞就可快速找到其出現(xiàn)的次數(shù),單詞與其出現(xiàn)次數(shù)就是**<word, count>**就構(gòu)成一種鍵值對。
namespace KV { template <class K,class V> struct BSTreeNode { BSTreeNode<K,V>* _left; BSTreeNode<K,V>* _right; K _key; V _value; BSTreeNode(const K& key,const V&value) :_key(key), _value(value), _left(nullptr), _right(nullptr) {} }; template <class K,class V> class BSTree { typedef BSTreeNode<K, V> Node; public: bool Insert(const K& key, const V& value) Node* find(const K& key) void InOrder() private: Node* _root = nullptr; }; } void TestBSTree() { //key/Value的搜索模型;通過key查找或修改Value KV::BSTree<string, string> dict; dict.Insert("sort", "排序"); dict.Insert("string", "字符串"); dict.Insert("left", "左"); dict.Insert("right", "右"); string str; while (cin >> str) { KV::BSTreeNode<string, string>* ret = dict.find(str); if (ret) { cout << ret->_value << endl; } else { cout << "找不到" << endl; } } }
源代碼:
BSTree.h
#include <iostream> using namespace std; namespace K { template <class K> struct BSTreeNode { BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key; BSTreeNode(const K& key) :_key(key), _left(nullptr), _right(nullptr) {} }; template <class K> class BSTree { typedef BSTreeNode<K> Node; public: BSTree() :_root(nullptr) {} BSTree(const BSTree<K>& t) { _root = Copy(t._root); } BSTree<K>& operator = (BSTree<K> t) { swap(_root, t._root); return *this; } ~BSTree() { Destroy(_root); _root = nullptr; } bool Insert(const K& key) { if (_root == nullptr) { _root = new Node(key); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_key < key) { parent = cur; cur = cur->_right; } else if (cur->_key > key) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(key); if (parent->_key < key) { parent->_right = cur; } else { parent->_left = cur; } return true; } bool find(const K& key) { Node* cur = _root; while (cur) { if (cur->_key < key) { cur = cur->_right; } else if (cur->_key > key) { cur = cur->_left; } else { return true; } } return false; } bool Erase(const K& key) { Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_key < key) { parent = cur; cur = cur->_right; } else if (cur->_key > key) { parent = cur; cur = cur->_left; } else { //左為空 if (cur->_left == nullptr) { //刪除根結(jié)點 //if(parent==nullptr) if (cur == _root) { _root = cur->_right; } else { if (parent->_left == cur) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } } delete cur; } //右為空 else if (cur->_right == nullptr) { if (cur == _root) { _root = cur->_left; } else { if (parent->_left == cur) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete cur; } //左右都不為空,找替換節(jié)點 else { //不能初始化為nullptr Node* parent = cur; //右子樹最小節(jié)點 Node* minRight = cur->_right; while (minRight->_left) { parent = minRight; minRight = minRight->_left; } cur->_key = minRight->_key; //判斷minRight是父親的左還是右 if (minRight == parent->_left) { parent->_left = minRight->_right; } else { parent->_right = minRight->_right; } delete minRight; } return true; } } return false; } void InOrder() { _InOrder(_root); cout << endl; } //遞歸 bool InsertR(const K& key) { return _InsertR(_root, key); } bool FindR(const K& key) { return _FindR(_root, key); } bool EraseR(const K& key) { return _EraseR(_root, key); } private: void Destroy(Node* root) { if (root == nullptr) { return; } Destroy(root->_left); Destroy(root->_right); delete root; } Node* Copy(Node* root) { if (root == nullptr) return nullptr; Node* newRoot = new Node(root->_key); newRoot->_left = Copy(root->_left); newRoot->_right = Copy(root->_right); return newRoot; } bool _EraseR(Node*& root, const K& key) { if (root == nullptr) { return false; } if (root->_key < key) { return _EraseR(root->_right, key); } else if (root->_key > key) { return _EraseR(root->_left, key); } else { Node* del = root; if (root->_right == nullptr) { root = root->_left; } else if (root->_left == nullptr) { root = root->_right; } else { Node* minRight = root->_right; while (minRight->_left) { minRight = minRight->_left; } swap(root->_key, minRight->_key); return _EraseR(root->_right, key); } delete del; return true; } } bool _InsertR(Node*& root, const K& key) { if (root == nullptr) { root = new Node(key); return true; } else if (root->_key < key) return _InsertR(root->_right, key); else if (root->_key > key) return _InsertR(root->_left, key); else return false; } bool _FindR(Node* root, const K& key) { if (root == nullptr) return false; else if (root->_key < key) return _FindR(root->_right, key); else if (root->_key > key) return _FindR(root->_left, key); else return true; } void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } Node* _root = nullptr; }; } namespace KV { template <class K,class V> struct BSTreeNode { BSTreeNode<K,V>* _left; BSTreeNode<K,V>* _right; K _key; V _value; BSTreeNode(const K& key,const V&value) :_key(key), _value(value), _left(nullptr), _right(nullptr) {} }; template <class K,class V> class BSTree { typedef BSTreeNode<K, V> Node; public: bool Insert(const K& key, const V& value) { if (_root == nullptr) { _root = new Node(key, value); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_key < key) { parent = cur; cur = cur->_right; } else if (cur->_key > key) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(key, value); if (parent->_key < key) { parent->_right = cur; } else { parent->_left = cur; } return true; } Node* find(const K& key) { Node* cur = _root; while (cur) { if (cur->_key < key) { cur = cur->_right; } else if (cur->_key > key) { cur = cur->_left; } else { return cur; } } return nullptr; } void InOrder() { _InOrder(_root); } private: void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_key << ":"<<root->_value<<endl; _InOrder(root->_right); } Node* _root = nullptr; }; } void TestBSTree1() { int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 }; K::BSTree<int> t; for (auto e : a) { t.Insert(e); } t.InOrder(); K::BSTree<int> copyt(t); copyt.InOrder(); t.InsertR(9); t.InOrder(); t.EraseR(9); t.InOrder(); t.EraseR(3); t.InOrder(); for (auto e : a) { t.EraseR(e); t.InOrder(); } } void TestBSTree2() { KV::BSTree<string, string> dict; dict.Insert("sort", "排序"); dict.Insert("string", "字符串"); dict.Insert("left", "左"); dict.Insert("right", "右"); string str; while (cin >> str) { KV::BSTreeNode<string, string>* ret = dict.find(str); if (ret) { cout << ret->_value << endl; } else { cout << "找不到" << endl; } } } void TestBSTree3() { string arr[] = { "蘋果","西瓜","蘋果" }; KV::BSTree<string, int> countTree; for (auto e : arr) { auto* ret = countTree.find(e); if (ret == nullptr) { countTree.Insert(e, 1); } else { ret->_value++; } } countTree.InOrder(); }
#include "BSTree.h" int main() { //TestBSTree1(); TestBSTree2(); //TestBSTree3(); return 0; }
根據(jù)二叉樹創(chuàng)建字符串
前序遍歷,左為空,右不為空的括號不可以省略,右為空的括號可以省略
class Solution { public: string tree2str(TreeNode* root) { if(root == nullptr) return string(); string ret; ret += to_string(root->val); if(root->left) { ret+='('; ret+= tree2str(root->left); ret+=')'; } else if(root->right) { ret+="()"; } if(root->right) { ret+='('; ret+=tree2str(root->right); ret+=')'; } return ret; } };
二叉樹的層序遍歷
層序遍歷,可以通過一個隊列來實現(xiàn),同時定義每次隊列的大小
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*> q; vector<vector<int>> vv; size_t levelSize = 0; if(root) { q.push(root); levelSize=1; } while(!q.empty()) { vector<int> v; while(levelSize--) { TreeNode* front = q.front(); q.pop(); v.push_back(front->val); if(front->left) { q.push(front->left); } if(front->right) { q.push(front->right); } } vv.push_back(v); levelSize = q.size(); } return vv; } };
二叉樹的最近公共祖先
class Solution { bool isInTree(TreeNode*root,TreeNode*x) { if(root == nullptr) return false; if(root == x) return true; else return isInTree(root->left,x) || isInTree(root->right,x); } public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root==nullptr) return nullptr; if(root == p||root==q) return root; bool pLeft = isInTree(root->left,p); bool pRight = !pLeft; bool qLeft = isInTree(root->left,q); bool qRight = !qLeft; //一個在左一個在右 if((pLeft&&qRight)||(pRight&&qLeft)) return root; //同左 if(pLeft&&qLeft) return lowestCommonAncestor(root->left,p,q); //同右 else return lowestCommonAncestor(root->right,p,q); } };
把根到對應節(jié)點的路徑存儲起來,在找出相交的結(jié)點即是最近的公共結(jié)點:
class Solution { bool GetPath(TreeNode*root,TreeNode*x,stack<TreeNode*>& stack) { if(root == nullptr) return false; stack.push(root); if(root == x) { return true; } if(GetPath(root->left,x,stack)) return true; if(GetPath(root->right,x,stack)) return true; stack.pop(); return false; } public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root==nullptr) return nullptr; stack<TreeNode*> pPath; stack<TreeNode*> qPath; GetPath(root,p,pPath); GetPath(root,q,qPath); //長的先pop while(pPath.size()!=qPath.size()) { if(pPath.size()>qPath.size()) { pPath.pop(); } else qPath.pop(); } //同時pop,找出交點 while(pPath.top()!=qPath.top()) { pPath.pop(); qPath.pop(); } return pPath.top(); } };
二叉搜索樹與雙向鏈表
思路一:中序遍歷,將節(jié)點放到一個vector中,在鏈接節(jié)點,但是空間復雜度不符合題目要求:
class Solution { void InOrder(TreeNode*root,vector<TreeNode*>& v) { if(root==nullptr) return; InOrder(root->left,v); v.push_back(root); InOrder(root->right,v); } public: TreeNode* Convert(TreeNode* pRootOfTree) { if(pRootOfTree==nullptr) return nullptr; vector<TreeNode*> v; InOrder(pRootOfTree,v); if(v.size()<=1) return v[0]; v[0]->left =nullptr; v[0]->right = v[1]; for(int i =1;i<v.size()-1;i++) { v[i]->left = v[i-1]; v[i]->right = v[i+1]; } v[v.size()-1]->left = v[v.size()-2]; v[v.size()-1]->right = nullptr; return v[0]; } };
思路二:遞歸直接進行轉(zhuǎn)換
class Solution { void InOrder(TreeNode*cur,TreeNode*&prev) { if(cur==nullptr) { return; } InOrder(cur->left,prev); cur->left = prev; if(prev) { prev->right = cur; } prev = cur; InOrder(cur->right,prev); } public: TreeNode* Convert(TreeNode* pRootOfTree) { TreeNode*prev = nullptr; InOrder(pRootOfTree,prev); //找頭 TreeNode*head = pRootOfTree; while(head&&head->left) { head = head->left; } return head; } };
從前序與中序遍歷序列構(gòu)造二叉樹
根據(jù)前序結(jié)果去創(chuàng)建樹,前序是根左右,前序第一個元素就是根,在通過中序去進行分割左右子樹。子樹區(qū)間確認是否繼續(xù)遞歸創(chuàng)建子樹,區(qū)間不存在則是空樹。所以根據(jù)前序先構(gòu)造根,在通過中序構(gòu)造左子樹、在構(gòu)造右子樹即可。
class Solution { TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder,int&prei,int inbegin,int inend) { if(inbegin>inend) { return nullptr; } TreeNode*root = new TreeNode(preorder[prei]); int rooti = inbegin; while(inbegin<=inend) { if(preorder[prei] == inorder[rooti]) { break; } else rooti++; } prei++; //[inbegin,rooti-1]rooti[rooti+1,inend] root->left= _buildTree(preorder,inorder,prei,inbegin,rooti-1); root->right = _buildTree(preorder,inorder,prei,rooti+1,inend); return root; } public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int prei = 0; return _buildTree(preorder,inorder,prei,0,inorder.size()-1); } };
傳引用問題:因為prei是遍歷前序數(shù)組開始的下標,整個遞歸遍歷中都要使用,所以我們需要傳引用。如果不是傳引用而是傳值的話,左子樹構(gòu)建好返回,如果此時prei不是傳引用,只是形參,無法將上一次遞歸的結(jié)果保留下來,那么也就無構(gòu)建右子樹了。
從中序與后序遍歷序列構(gòu)造二叉樹
根據(jù)后序遍歷的最后一個元素可以確定根結(jié)點,有了根結(jié)點做為切割點然后再去根據(jù)中序遍歷劃分左右區(qū)間,在繼續(xù)下去,構(gòu)造成二叉樹,區(qū)間不存在就是空樹了。同時,后序遍歷是左右根,所以最后一個是根節(jié)點。所以當我們構(gòu)造根結(jié)點后,由于前面是右子樹,所以先構(gòu)造右子樹,在構(gòu)造左子數(shù)。
class Solution { TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder,int &posi,int inbegin,int inend) { if(inbegin>inend) { return nullptr; } TreeNode* root = new TreeNode(postorder[posi]); int rooti = inbegin; while(inbegin<=inend) { if(postorder[posi] == inorder[rooti]) { break; } else rooti++; } posi--; //[inbegin,rooti-1]rooti[rooti+1,inend]; root->right = _buildTree(inorder,postorder,posi,rooti+1,inend); root->left = _buildTree(inorder,postorder,posi,inbegin,rooti-1); return root; } public: TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { int posi = postorder.size()-1; return _buildTree(inorder,postorder,posi,0,inorder.size()-1); } };
關(guān)于“C++二叉搜索樹BSTree如何使用”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識,可以關(guān)注億速云行業(yè)資訊頻道,小編每天都會為大家更新不同的知識點。
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。