二叉查找樹是二叉樹的一個特化,它具有的特殊性質是:對于樹中的任何一個結點,它的左子樹的所有結點的關鍵字都小于此結點的關鍵字,而右子樹的所有結點的關鍵字都大于此結點的關鍵字.
二叉查找樹的這種特殊性質使得它在查找元素的時候特別的方便,每一次查找都可以去掉一半的元素,因此查找的時間是O(logN).
二叉查找樹的插入和查找算法也是很簡單的,就是與當前結點的關鍵字作比較決定在右邊還是左邊繼續操作.
二叉查找樹最復雜的算法就是刪除結點的算法了,根據所要刪除的結點有兩個子結點還是只有一個或者沒有子結點會有不同的處理.有兩個子結點的情況一般的處理是找到右子樹中值最小的一個結點,將它的值替代當前的結點值,然后再把這個值最小的結點刪除,也就是說有兩個子結點的情況是用最小的一個大于當前結點關鍵字的結點替代了當前的結點(很拗口,但愿我說清楚了:)在只有一個或者沒有子結點的情況就比較的簡單了,如果還有子結點就把子結點的位置往上挪,然后把當前結點刪除.
實現如下:
1)BSTree.h
/**//********************************************************************
????created:????2006/07/28
????filename:?????BSTree.h
????author:????????李創
????????????????http://www.shnenglu.com/converse/
????purpose:????二叉查找樹的實現代碼
*********************************************************************/
#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:????????李創
????????????????http://www.shnenglu.com/converse/
????purpose:????二叉查找樹的實現代碼
*********************************************************************/
#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);
}
//?中序打印出樹中的元素,這樣應該是從小到大的順序
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)
????{
????????//?找到結點且有兩個子結點
????????BTreeNode<T>*?pNode;
????????//?找到右子樹中最小的結點,把它的值替換當前結點值,然后刪除找到的那個結點
????????pNode?=?FindMin(p->pRight);
????????p->Data?=?pNode->Data;
????????p->pRight?=?Delete(p->Data,?p->pRight);
????}
????else
????{
????????//?找到結點但是只有一個或沒有子結點
????????//?如果有子結點就用子結點代替當前結點,然后刪除當前結點
????????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>
//?創建一個數組,元素值隨機設置
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;
} 需要說明一點:上面做測試用的Main.cpp如果單獨寫在一個文件中就會在鏈接的時候報錯,報的錯誤是:
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中的內容copy到BSTree.cpp中才能鏈接過去.
如果哪位朋友知道如何解決上面因為采用了模板類出現的鏈接錯誤,我不勝感激,謝謝!