?? bst.h
字號(hào):
#ifndef BST_H
#define BST_H
#include <assert.h>
#include <iostream>
#include <stdlib.h>
using namespace std;
int max(int a, int b)
{
return ((a >= b) ? a : b);
}
template<class Type> class BST;
// 二叉搜索樹(shù)的節(jié)點(diǎn)類
template<class Type> class BSTNode {
friend class BST<Type>;
public:
BSTNode(Type d = 0, BSTNode<Type> *left = 0, BSTNode<Type> *right = 0) : data(d), leftChild(left), rightChild(right) { }
Type getData() const { return data; }
private:
BSTNode<Type> *leftChild; // 指向左子女結(jié)點(diǎn)
BSTNode<Type> *rightChild; // 指向右子女結(jié)點(diǎn)
Type data; // 數(shù)據(jù)
};
//////////////////////////////////////////////////////////////////////////////////////////
// 二叉搜索樹(shù)的類BST
template<class Type> class BST {
public:
BST() : root(0) { } // 構(gòu)造函數(shù)：創(chuàng)建一個(gè)空樹(shù)
BST(const BST<Type> &); // 復(fù)制構(gòu)造函數(shù)
BST& operator=(const BST<Type> &); // 重載運(yùn)算符'='
~BST(); // 析構(gòu)函數(shù)
bool isEmpty() const { return root == 0; } // 判斷二叉搜索樹(shù)是否為空
bool operator==(const BST<Type> &t) const; // 判斷當(dāng)前樹(shù)（*this）與樹(shù)t是否相等
BSTNode<Type> *getRoot() const { return root; } // 取根root的指針值
BSTNode<Type> *parent(BSTNode<Type> *current) const; // 返回雙親節(jié)點(diǎn)的地址
BSTNode<Type> *leftChild(BSTNode<Type> *current) const; // 返回左子女的節(jié)點(diǎn)地址
BSTNode<Type> *rightChild(BSTNode<Type> *current) const; // 返回右子女的節(jié)點(diǎn)地址
bool find(const Type &item) const; // 搜索元素
void insert(const Type &item); // 插入新元素
void remove(const Type &x); // 刪除含x的節(jié)點(diǎn)
Type min() const; // 求最小元素
Type max() const; // 求最大元素
void inOrder() const; // 中序遍歷二叉搜索樹(shù)
int size() const; // 計(jì)算二叉搜索樹(shù)的節(jié)點(diǎn)個(gè)數(shù)
int depth() const; // 計(jì)算二叉搜索樹(shù)的高度
private:
BSTNode<Type> *root; // 二叉搜索樹(shù)的根指針
void destroy(BSTNode<Type> *current); // 刪除根為current的子樹(shù)
// 從節(jié)點(diǎn)start開(kāi)始，搜索current的雙親節(jié)點(diǎn)
BSTNode<Type> *parent(BSTNode<Type> *start, BSTNode<Type> *current) const;
void insert(BSTNode<Type> * &start, const Type &item); // 插入
void remove(BSTNode<Type> * &start, const Type &item); // 刪除
BSTNode<Type>* find(const Type &item, BSTNode<Type> *ptr) const; // 搜索
BSTNode<Type> *min(BSTNode<Type> *ptr) const; // 求最小
BSTNode<Type> *max(BSTNode<Type> *ptr) const; // 求最大
void inOrder(BSTNode<Type> *current) const; // 中序遍歷以current為根的二叉搜索樹(shù)
int size(const BSTNode<Type> *current) const; // 計(jì)算以current為根的二叉搜索樹(shù)的節(jié)點(diǎn)個(gè)數(shù)
int depth(const BSTNode<Type> *current) const; // 計(jì)算以current為根的二叉搜索樹(shù)的高度
// 復(fù)制以current為根的樹(shù)
BSTNode<Type>* copy(BSTNode<Type> *current);
bool equal(BSTNode<Type> *a, BSTNode<Type> *b) const; // 判斷樹(shù)a和b是否相等
};
// 復(fù)制構(gòu)造函數(shù)
template<class Type>
BST<Type>::BST(const BST<Type> &right)
{
root = copy(right.root);
}
// 復(fù)制以current為根的樹(shù)
template<class Type>
BSTNode<Type>* BST<Type>::copy(BSTNode<Type> *current)
{
if (!current) // 根為空，返回空指針
return 0;
BSTNode<Type> *temp = new BSTNode<Type>;
temp->data = current->data;
temp->leftChild = copy(current->leftChild);
temp->rightChild = copy(current->rightChild);
return temp;
}
// 重載運(yùn)算符'='
template<class Type>
BST<Type>& BST<Type>::operator=(const BST<Type> &right)
{
// 避免自我賦值和對(duì)已經(jīng)相等的樹(shù)進(jìn)行賦值
if ((this == &right) || equal(root, right.root))
return *this;
destroy(root); // 刪除原來(lái)的樹(shù)
root = copy(right.root); // 賦值
return *this;
}
// 析構(gòu)函數(shù)
template<class Type>
BST<Type>::~BST()
{
if (root)
destroy(root);
root = 0;
}
// 私有函數(shù)：若指針current不為空，則刪除根為current的子樹(shù)
template<class Type> void BST<Type>::destroy(BSTNode<Type> *current)
{
if (current) {
destroy(current->leftChild); // 刪除current的左子樹(shù)
destroy(current->rightChild); // 刪除current的右子樹(shù)
delete current; // 刪除current
}
}
// 返回current的雙親節(jié)點(diǎn)的地址
template<class Type>
BSTNode<Type>* BST<Type>::parent(BSTNode<Type> *current) const
{
if (root == 0 || root == current)
return 0;
else
return parent(root, current);
}
// 所有函數(shù)：從節(jié)點(diǎn)start開(kāi)始，搜索節(jié)點(diǎn)current的雙親節(jié)點(diǎn)
// 若找到，則函數(shù)返回雙親節(jié)點(diǎn)的地址，否則返回0
template<class Type>
BSTNode<Type>* BST<Type>::parent(BSTNode<Type> *start, BSTNode<Type> *current) const
{
if (start == 0)
return 0;
if (start->leftChild == current || start->rightChild == current) // 找到
return start;
BSTNode<Type> *temp;
if (temp = parent(start->leftChild, current)) // 在左子樹(shù)中搜索
return temp;
else
return parent(start->rightChild, current); // 在右子樹(shù)中搜索
}
// 返回節(jié)點(diǎn)current的左子女節(jié)點(diǎn)地址
template<class Type>
BSTNode<Type>* BST<Type>::leftChild(BSTNode<Type> *current) const
{
if (!root)
return 0;
return current->leftChild;
}
// 返回節(jié)點(diǎn)current的右子女節(jié)點(diǎn)地址
template<class Type>
BSTNode<Type>* BST<Type>::rightChild(BSTNode<Type> *current) const
{
if (!root)
return 0;
return current->rightChild;
}
// 在二叉搜索樹(shù)中插入值為item的新節(jié)點(diǎn)
template<class Type>
void BST<Type>::insert(const Type &item)
{
insert(root, item);
}
// 私有函數(shù)：在以根start的二叉搜索樹(shù)中插入所含值為item的節(jié)點(diǎn)
// 若樹(shù)中已經(jīng)有含x的節(jié)點(diǎn)，則不插入
template<class Type>
void BST<Type>::insert(BSTNode<Type> * &start, const Type &item)
{
if (!start) { // 新節(jié)點(diǎn)作為葉節(jié)點(diǎn)插入
start = new BSTNode<Type>(item); // 創(chuàng)建新節(jié)點(diǎn)
assert(start);
}
else if ( item < start->data) // 小于根的關(guān)鍵碼，向左子樹(shù)插入
insert(start->leftChild, item);
else if (item > start->data)
insert(start->rightChild, item); // 大于根的關(guān)鍵碼，向右子樹(shù)插入
}
// 刪除含x的節(jié)點(diǎn)
template<class Type>
void BST<Type>::remove(const Type &x)
{
remove(root, x);
}
// 私有函數(shù)：在以ptr為根的二叉搜索樹(shù)中。若刪除成功，新根通過(guò)ptr返回
template<class Type>
void BST<Type>::remove(BSTNode<Type> *&ptr, const Type &x)
{
BSTNode<Type> *temp;
if (ptr) {
if (x < ptr->data)
remove(ptr->leftChild, x); // 在左子樹(shù)中刪除
else if (x > ptr->data)
remove(ptr->rightChild, x); // 在右子樹(shù)中刪除
else if(ptr->leftChild && ptr->rightChild) { // ptr指示關(guān)鍵碼為x的節(jié)點(diǎn)，它有兩個(gè)子女
temp = min(ptr->rightChild); // 在ptr的右子樹(shù)中搜尋最小節(jié)點(diǎn)
ptr->data = temp->data; // 用該節(jié)點(diǎn)數(shù)據(jù)代替根節(jié)點(diǎn)數(shù)據(jù)
remove(ptr->rightChild, ptr->data); // 在右子樹(shù)中刪除該節(jié)點(diǎn)
}
else { // ptr指示關(guān)鍵碼為x的節(jié)點(diǎn)，它只有一個(gè)或零個(gè)子女
temp = ptr;
if (!ptr->leftChild)
ptr = ptr->rightChild; // 只有右子女
else if (!ptr->rightChild)
ptr = ptr->leftChild; // 只有左子女
delete temp;
}
}
}
// 求最小元素
template<class Type> Type BST<Type>::min() const {
return min(root)->getData();
}
// 尋找以ptr為根的二叉搜索樹(shù)的最小值的地址
template<class Type>
BSTNode<Type>* BST<Type>::min(BSTNode<Type> *ptr) const
{
if (!ptr)
return 0;
BSTNode<Type> *temp = ptr;
while (temp->leftChild)
temp = temp->leftChild;
return temp;
}
// 求最大元素
template<class Type> Type BST<Type>::max() const {
return max(root)->getData();
}
// 尋找以ptr為根的二叉搜索樹(shù)的最大值的地址
template<class Type>
BSTNode<Type>* BST<Type>::max(BSTNode<Type> *ptr) const
{
if (!ptr)
return 0;
BSTNode<Type> *temp = ptr;
while (temp->rightChild)
temp = temp->rightChild;
return temp;
}
// 搜索元素item
template<class Type>
bool BST<Type>::find(const Type &item) const
{
return (find(item, root) != 0);
}
// 私有函數(shù)：在以ptr為根的二叉搜索數(shù)中搜索含item的節(jié)點(diǎn)
template<class Type>
BSTNode<Type>* BST<Type>::find(const Type &item, BSTNode<Type> *ptr) const
{
if (ptr) { // 樹(shù)不空
// 遞歸算法
if (item < ptr->data)
return find(item, ptr->leftChild); // 到左子樹(shù)中搜索
else if (item > ptr->data)
return find(item, ptr->rightChild); // 到右子樹(shù)中搜索
else
return ptr; // 搜索成功
/*
// 迭代算法
BSTNode<Type> *temp = ptr; // 從根開(kāi)始搜索
while (temp) {
if (temp->data == item) // 搜索成功
return temp;
else if (temp->data < item)
temp = temp->rightChild; // 否則，繼續(xù)搜索右子樹(shù)
else
temp = temp->leftChild; // 否則，繼續(xù)搜索左子樹(shù)
}
*/
}
return 0;
}
// 中序遍歷二叉搜索樹(shù)
template<class Type>
void BST<Type>::inOrder() const
{
inOrder(root);
}
// 私有函數(shù)：中序遍歷以current為根的二叉搜索樹(shù)
template<class Type>
void BST<Type>::inOrder(BSTNode<Type> *current) const
{
if(current) {
inOrder(current->leftChild); // 中序遍歷左子樹(shù)
cout << current->data << ' '; // 訪問(wèn)根節(jié)點(diǎn)，用輸出語(yǔ)句暫代
inOrder(current->rightChild); // 中序遍歷右子樹(shù)
}
}
// 計(jì)算二叉搜索樹(shù)的節(jié)點(diǎn)個(gè)數(shù)
template<class Type>
int BST<Type>::size() const
{
return size(root);
}
// 私有函數(shù)：計(jì)算以current為根的二叉搜索樹(shù)的節(jié)點(diǎn)個(gè)數(shù)
template<class Type>
int BST<Type>::size(const BSTNode<Type> *current) const
{
if (!current) // 遞歸結(jié)束條件
return 0;
else
return 1 + size(current->leftChild) + size(current->rightChild);
}
// 計(jì)算二叉搜索樹(shù)的高度
template<class Type>
int BST<Type>::depth() const
{
return depth(root);
}
// 私有函數(shù)：計(jì)算以current為根的二叉搜索樹(shù)的節(jié)點(diǎn)個(gè)數(shù)
template<class Type>
int BST<Type>::depth(const BSTNode<Type> *current) const
{
if (!current) // 遞歸結(jié)束條件
return -1;
else
return 1 + ::max(depth(current->leftChild), depth(current->rightChild));
}
// 判斷當(dāng)前樹(shù)（*this）與樹(shù)t是否相等
template<class Type>
bool BST<Type>::operator==(const BST<Type> &t) const
{
return equal(root, t.root);
}
// 私有函數(shù)：判斷樹(shù)a和b是否相等
template<class Type>
bool BST<Type>::equal(BSTNode<Type> *a, BSTNode<Type> *b) const
{
if (!a && !b)
return true;
if (a && b && (a->data == b->data) &&
equal(a->leftChild, b->leftChild) &&
equal(a->rightChild, b->rightChild))
return true;
else
return false;
}
#endif // BST_H?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -