您好,登錄后才能下訂單哦!
● 二叉搜索樹滿足以下條件的二叉樹:
1、每個(gè)節(jié)點(diǎn)都有一個(gè)作為搜索依據(jù)的關(guān)鍵碼(key),所有節(jié)點(diǎn)的關(guān)鍵碼互不相同。
2、左子樹上所有節(jié)點(diǎn)的關(guān)鍵碼(key)都小于根節(jié)點(diǎn)的關(guān)鍵碼(key)。
3、右子樹上所有節(jié)點(diǎn)的關(guān)鍵碼(key)都大于根節(jié)點(diǎn)的關(guān)鍵碼(key)。
4、左右子樹都是二叉搜索樹。
● 二叉搜索樹的插入過(guò)程如下:
1、若當(dāng)前的二叉搜索樹為空,則插入的元素為根節(jié)點(diǎn)。
2、若插入的元素值小于根節(jié)點(diǎn)值,則將元素插入到左子樹中。
3、若插入的元素值大于根節(jié)點(diǎn)值,則將元素插入到右子樹中。
4、找到插入的位置和插入的位置的父結(jié)點(diǎn),進(jìn)行鏈接。
template<class T> void BSTree<T>::Insert(const T& key, const T& value)//非遞歸算法進(jìn)行插入 { if (_root == NULL) { _root = new Node(key, value); return; } Node* prev = NULL; Node* cur = _root; while (cur)//在樹中找到插入的位置 { if (key < cur->_key) { prev = cur; cur = cur->_left; } else if (key > cur->_key) { prev = cur; cur = cur->_right; } } cur = new Node(key, value);//建立新結(jié)點(diǎn),并判斷具體位置進(jìn)行鏈接 if (prev->_key > cur->_key) { prev->_left = cur; } if (prev->_key < cur->_key) { prev->_right = cur; } } template<class T> void BSTree<T>::Insert_R(const T& key, const T& value)//遞歸算法進(jìn)行插入 { _insert_r(_root, key, value); } template<class T> void BSTree<T>::_insert_r(Node*& root, const T& key, const T& value)//遞歸 { if (root == NULL)//root為空時(shí),開辟新結(jié)點(diǎn) { root = new Node(key, value); return; } Node* cur = root; if (key < cur->_key) _insert_r(cur->_left, key, value); if (key > cur->_key) _insert_r(cur->_right, key, value); }
● 二叉搜索樹的查找過(guò)程如下:
1、若當(dāng)前的二叉搜索樹為空,則結(jié)束函數(shù)。
2、若查找的元素值小于根節(jié)點(diǎn)值,則在當(dāng)前結(jié)點(diǎn)的左子樹中查找。
3、若查找的元素值大于根節(jié)點(diǎn)值,則在當(dāng)前結(jié)點(diǎn)的右子樹中查找。
template<class T> BSTNode<T>* BSTree<T>::Find(const T& key)//非遞歸算法進(jìn)行查找 { Node* cur = _root; while (cur) { if (key < cur->_key) { cur = cur->_left; } else if (key > cur->_key) { cur = cur->_right; } else { return cur; } } return NULL; } template<class T> BSTNode<T>* BSTree<T>::Find_R(const T& key)//遞歸 { return _find_r(_root, key); } template<class T> BSTNode<T>* BSTree<T>::_find_r(Node*& root, const T& key)//遞歸算法進(jìn)行查找 { if (root == NULL)//root為空時(shí)為沒找到 { return NULL; } if (key < root->_key) return _find_r(root->_left, key); else if (key > root->_key) return _find_r(root->_right, key); else return root; }
● 二叉搜索樹的刪除,分兩種情況進(jìn)行處理:
1、找到要?jiǎng)h除的結(jié)點(diǎn)cur和cur的父親結(jié)點(diǎn)prev。
2、情況一:cur只有一個(gè)子樹或沒有子樹。首先考慮刪除的結(jié)點(diǎn)為根結(jié)點(diǎn)時(shí),直接_root指向它的子樹;
再考慮cur的左為空、右為空還是左右都為空,進(jìn)行刪除,鏈接。
3、情況二:cur左右子樹都不為空。首先找到cur右子樹的最左下結(jié)點(diǎn)del,然后進(jìn)行交換,通過(guò)替換法刪除del,并使prev的指向置空。
template<class T> void BSTree<T>::Remove(const T& key)//非遞歸算法進(jìn)行刪除 { if (_root == NULL) { return; } Node* prev = NULL; Node* cur = _root; while (cur)//找到要?jiǎng)h除的結(jié)點(diǎn)cur { if (key < cur->_key) { prev = cur; cur = cur->_left; } else if (key > cur->_key) { prev = cur; cur = cur->_right; } else break; } //情況一:cur只有一個(gè)孩子或沒有孩子,注意考慮cur為根結(jié)點(diǎn)時(shí),prev=NULL if (cur->_left == NULL || cur->_right == NULL) { if (cur->_left == NULL)//cur只有右孩子 { if (prev == NULL)//cur為根結(jié)點(diǎn)時(shí) _root = cur->_right; else if (prev->_left == cur) prev->_left = cur->_right; else prev->_right = cur->_right; } else if (cur->_right == NULL)//cur只有左孩子 { if (prev == NULL)//cur為根結(jié)點(diǎn)時(shí) _root = cur->_left; else if (prev->_left == cur) prev->_left = cur->_left; else prev->_right = cur->_left; } //刪除cur并置空,包含了cur的左右為空的情況 delete cur; cur = NULL; } //情況二:cur有左右子樹,替換法刪除 else { //先找到cur結(jié)點(diǎn)右子樹的最左下結(jié)點(diǎn)del Node* del = cur; prev = del; del = del->_right; while (del->_left) { prev = del; del = del->_left; } //替換法,刪除結(jié)點(diǎn)del,注意使prev的指向置空 swap(cur->_key, del->_key); swap(cur->_value, del->_value); if (prev->_left == del) prev->_left = NULL; else if (prev->_right == del) prev->_right = NULL; delete del; del = NULL; } } template<class T> void BSTree<T>::Remove_R(const T& key)//遞歸算法進(jìn)行刪除 { _remove_r(_root, key); } template<class T> void BSTree<T>::_remove_r(Node*& root, const T& key)//遞歸 { if (_root == NULL) { return; } if (key < root->_key) _remove_r(root->_left, key); else if (key > root->_key) _remove_r(root->_right, key); else { //情況一:只有一個(gè)子樹或沒有,直接使root重新賦值 if (root->_left == NULL || root->_right == NULL) { Node* del = root; if (root->_left == NULL) root = root->_right; else if (root->_right == NULL) root = root->_left; else root = NULL; delete del; del = NULL; } else//情況二:左右子樹都不為空 { Node* cur = root->_right;//root右子樹最左下結(jié)點(diǎn),交換兩個(gè)結(jié)點(diǎn)的值 while (cur->_left) { cur = cur->_left; } swap(root->_key, cur->_key); swap(root->_value, cur->_value); _remove_r(root->_right, key);//在root的右子樹上刪除key,轉(zhuǎn)換成情況一中左子樹一定為空 } } }
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。