二叉查找樹是二叉樹的一個特化,它具有的特殊性質(zhì)是:對于樹中的任何一個結(jié)點(diǎn),它的左子樹的所有結(jié)點(diǎn)的關(guān)鍵字都小于此結(jié)點(diǎn)的關(guān)鍵字,而右子樹的所有結(jié)點(diǎn)的關(guān)鍵字都大于此結(jié)點(diǎn)的關(guān)鍵字.
二叉查找樹的這種特殊性質(zhì)使得它在查找元素的時候特別的方便,每一次查找都可以去掉一半的元素,因此查找的時間是O(logN).
二叉查找樹的插入和查找算法也是很簡單的,就是與當(dāng)前結(jié)點(diǎn)的關(guān)鍵字作比較決定在右邊還是左邊繼續(xù)操作.
二叉查找樹最復(fù)雜的算法就是刪除結(jié)點(diǎn)的算法了,根據(jù)所要刪除的結(jié)點(diǎn)有兩個子結(jié)點(diǎn)還是只有一個或者沒有子結(jié)點(diǎn)會有不同的處理.有兩個子結(jié)點(diǎn)的情況一般的處理是找到右子樹中值最小的一個結(jié)點(diǎn),將它的值替代當(dāng)前的結(jié)點(diǎn)值,然后再把這個值最小的結(jié)點(diǎn)刪除,也就是說有兩個子結(jié)點(diǎn)的情況是用最小的一個大于當(dāng)前結(jié)點(diǎn)關(guān)鍵字的結(jié)點(diǎn)替代了當(dāng)前的結(jié)點(diǎn)(很拗口,但愿我說清楚了:)在只有一個或者沒有子結(jié)點(diǎn)的情況就比較的簡單了,如果還有子結(jié)點(diǎn)就把子結(jié)點(diǎn)的位置往上挪,然后把當(dāng)前結(jié)點(diǎn)刪除.
實(shí)現(xiàn)如下:
1)BSTree.h
/**//********************************************************************
????created:????2006/07/28
????filename:?????BSTree.h
????author:????????李創(chuàng)
????????????????http://www.shnenglu.com/converse/
????purpose:????二叉查找樹的實(shí)現(xiàn)代碼
*********************************************************************/
#ifndef?BINARY_SEARCH_TREE_H
#define?BINARY_SEARCH_TREE_H
#include?<stdio.h>
template<typename?T>
struct?BTreeNode
{
????T????Data;
????BTreeNode*?pLeft;
????BTreeNode*?pRight;
????BTreeNode*?pParent;
????BTreeNode(????T?data?=?T(),?BTreeNode<T>*?Parent?=?NULL,?
????????????????BTreeNode<T>*?Left?=?NULL,?BTreeNode<T>*?Right?=?NULL)
????????????????:?Data(data),?pLeft(Left),?pRight(Right),?pParent(Parent)
????{
????}
};
template<typename?T>
class?BSTree
{
protected:
????BTreeNode<T>*????m_pRootNode;
public:
????BSTree(BTreeNode<T>*?pRoot?=?NULL)?
????????:?m_pRootNode(pRoot)
????{
????}
????~BSTree();
????void????????????Display();
????BTreeNode<T>*????Insert(const?T&?data);
????BTreeNode<T>*????Find(const?T&?data);
????BTreeNode<T>*????FindMin();
????BTreeNode<T>*????FindMax();
????BTreeNode<T>*????Delete(const?T&?data);
private:
????void????????????Display(BTreeNode<T>*?p);
????BTreeNode<T>*????Insert(const?T&?data,?BTreeNode<T>*?p);
????BTreeNode<T>*????Find(const?T&?data,?BTreeNode<T>*?p);
????BTreeNode<T>*????FindMin(BTreeNode<T>*?p);
????BTreeNode<T>*????FindMax(BTreeNode<T>*?p);
????BTreeNode<T>*????Delete(const?T&?data,?BTreeNode<T>*?p);
????void????????????DestructImpl(BTreeNode<T>*?p);
};
#endif
2)BSTree.cpp
/**//********************************************************************
????created:????2006/07/28
????filename:?????BSTree.cpp
????author:????????李創(chuàng)
????????????????http://www.shnenglu.com/converse/
????purpose:????二叉查找樹的實(shí)現(xiàn)代碼
*********************************************************************/
#include?<iostream>
#include?"BSTree.h"
template<typename?T>
BSTree<T>::~BSTree()
{
????DestructImpl(m_pRootNode);
}
template<typename?T>
void?BSTree<T>::DestructImpl(BTreeNode<T>*?p)
{
????if?(NULL?==?p)
????????return;
????DestructImpl(p->pLeft);
????DestructImpl(p->pRight);
????p->pLeft?=?NULL;
????p->pRight?=?NULL;
????p->pParent?=?NULL;
????delete?p;
????p?=?NULL;
}
template<typename?T>
void?BSTree<T>::Display()
{
????Display(m_pRootNode);
}
//?中序打印出樹中的元素,這樣應(yīng)該是從小到大的順序
template<typename?T>
void?BSTree<T>::Display(BTreeNode<T>*?p)
{
????if?(NULL?==?p)
????????return;
????Display(p->pLeft);
????std::cout?<<?"Node?=?"?<<?p->Data?<<?std::endl;
????Display(p->pRight);
}
template<typename?T>
BTreeNode<T>*?BSTree<T>::Insert(const?T&?data)
{
????return?Insert(data,?m_pRootNode);
}
template<typename?T>
BTreeNode<T>*?BSTree<T>::Insert(const?T&?data,?BTreeNode<T>*?p)
{
????if?(NULL?==?p)
????{
????????p?=?new?BTreeNode<T>(data);
????????if?(NULL?==?p)
????????{
????????????return?NULL;
????????}
????????else?if?(NULL?==?m_pRootNode)
????????{
????????????m_pRootNode?=?p;
????????}
????}
????else?if?(data?>?p->Data)
????{
????????p->pRight?=?Insert(data,?p->pRight);
????????if?(NULL?!=?p->pRight)
????????{
????????????p->pRight->pParent?=?p;
????????}
????}
????else
????{
????????p->pLeft?=?Insert(data,?p->pLeft);
????????if?(NULL?!=?p->pLeft)
????????{
????????????p->pLeft->pParent?=?p;
????????}
????}
????return?p;
}
template<typename?T>
BTreeNode<T>*?BSTree<T>::Find(const?T&?data)
{
????return?Find(data,?m_pRootNode);
}
template<typename?T>
BTreeNode<T>*?BSTree<T>::Find(const?T&?data,?BTreeNode<T>*?p)
{
????if?(NULL?==?p)
????{
????????return?NULL;
????}
????else
????{
????????if?(data?==?p->Data)
????????{
????????????return?p;
????????}
????????else?if?(data?>?p->Data)
????????{
????????????return?Find(data,?p->pRight);
????????}
????????else
????????{
????????????return?Find(data,?p->pLeft);
????????}
????}
}
template<typename?T>
BTreeNode<T>*?BSTree<T>::FindMin()
{
????return?FindMin(m_pRootNode);
}
template<typename?T>
BTreeNode<T>*?BSTree<T>::FindMin(BTreeNode<T>*?p)
{
????if?(NULL?==?p)
????{
????????return?NULL;
????}
????if?(NULL?!=?p->pLeft)
????{
????????return?FindMin(p->pLeft);
????}
????else
????{
????????return?p;
????}
}
template<typename?T>
BTreeNode<T>*?BSTree<T>::FindMax()
{
????return?FindMax(m_pRootNode);
}
template<typename?T>
BTreeNode<T>*?BSTree<T>::FindMax(BTreeNode<T>*?p)
{
????if?(NULL?==?p)
????{
????????return?NULL;
????}
????if?(NULL?!=?p->pRight)
????{
????????return?FindMax(p->pRight);
????}
????else
????{
????????return?p;
????}
}
template<typename?T>
BTreeNode<T>*?BSTree<T>::Delete(const?T&?data)
{
????return?Delete(data,?m_pRootNode);
}
template<typename?T>
BTreeNode<T>*?BSTree<T>::Delete(const?T&?data,?BTreeNode<T>*?p)
{
????if?(NULL?==?p)
????{
????????return?NULL;
????}
????else?if?(data?<?p->Data)
????{
????????p->pLeft?=?Delete(data,?p->pLeft);
????}
????else?if?(data?>?p->Data)
????{
????????p->pRight?=?Delete(data,?p->pRight);
????}
????else?if?(NULL?!=?p->pLeft?&&?NULL?!=?p->pRight)
????{
????????//?找到結(jié)點(diǎn)且有兩個子結(jié)點(diǎn)
????????BTreeNode<T>*?pNode;
????????//?找到右子樹中最小的結(jié)點(diǎn),把它的值替換當(dāng)前結(jié)點(diǎn)值,然后刪除找到的那個結(jié)點(diǎn)
????????pNode?=?FindMin(p->pRight);
????????p->Data?=?pNode->Data;
????????p->pRight?=?Delete(p->Data,?p->pRight);
????}
????else
????{
????????//?找到結(jié)點(diǎn)但是只有一個或沒有子結(jié)點(diǎn)
????????//?如果有子結(jié)點(diǎn)就用子結(jié)點(diǎn)代替當(dāng)前結(jié)點(diǎn),然后刪除當(dāng)前結(jié)點(diǎn)
????????BTreeNode<T>*?pNode?=?p;
????????if?(NULL?==?p->pLeft)
????????{
????????????p?=?p->pRight;
????????}
????????else?if?(NULL?==?p->pRight)
????????{
????????????p?=?p->pLeft;
????????}
????????delete?pNode;
????????pNode?=?NULL;
????}
????return?p;
}
3)Main.cpp
#include?"BSTree.h"
#include?<stdlib.h>
#include?<time.h>
//?創(chuàng)建一個數(shù)組,元素值隨機(jī)設(shè)置
void?CreateNewArray(int?array[],?int?length)
{
????for?(int?i?=?0;?i?<?length;?i++)
????{
????????array[i]?=?rand()?%?256;
????}
}
int?main()
{
????int?array[10];
????srand(time(NULL));
????CreateNewArray(array,?10);
????BSTree<int>?tree;
????for?(int?i?=?0;?i?<?10;?++i)
????{
????????tree.Insert(array[i]);
????}
????tree.Display();
????if?(NULL?!=?tree.Find(array[7]))
????{
????????std::cout?<<?"Find!\n";
????}
????BTreeNode<int>*?pNode;
????if?(NULL?!=?(pNode?=?tree.FindMin()))
????{
????????std::cout?<<?"Min?=?"?<<?pNode->Data?<<?std::endl;
????}
????if?(NULL?!=?(pNode?=?tree.FindMax()))
????{
????????std::cout?<<?"Max?=?"?<<?pNode->Data?<<?std::endl;
????}
????tree.Delete(array[7]);
????std::cout?<<?"\nafter?delete?"?<<?array[7]?<<?std::endl;
????tree.Display();
????system("pause");
????return?0;
} 需要說明一點(diǎn):上面做測試用的Main.cpp如果單獨(dú)寫在一個文件中就會在鏈接的時候報錯,報的錯誤是:
BSTree error LNK2019: unresolved external symbol "public: struct BTreeNode<int> * __thiscall BSTree<int>::Insert(int const &)" (
?Insert@?$BSTree@H@@QAEPAU?$BTreeNode@H@@ABH@Z) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: __thiscall BSTree<int>::~BSTree<int>(void)" (
??1?$BSTree@H@@QAE@XZ) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: struct BTreeNode<int> * __thiscall BSTree<int>::Delete(int const &)" (
?Delete@?$BSTree@H@@QAEPAU?$BTreeNode@H@@ABH@Z) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: struct BTreeNode<int> * __thiscall BSTree<int>::FindMax(void)" (
?FindMax@?$BSTree@H@@QAEPAU?$BTreeNode@H@@XZ) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: struct BTreeNode<int> * __thiscall BSTree<int>::FindMin(void)" (
?FindMin@?$BSTree@H@@QAEPAU?$BTreeNode@H@@XZ) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: struct BTreeNode<int> * __thiscall BSTree<int>::Find(int const &)" (
?Find@?$BSTree@H@@QAEPAU?$BTreeNode@H@@ABH@Z) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: void __thiscall BSTree<int>::Display(void)" (
?Display@?$BSTree@H@@QAEXXZ) referenced in function _main
所以沒有辦法,我只能將main.cpp中的內(nèi)容copy到BSTree.cpp中才能鏈接過去.
如果哪位朋友知道如何解決上面因?yàn)椴捎昧四０孱惓霈F(xiàn)的鏈接錯誤,我不勝感激,謝謝!