二叉查找樹解析及其C++實現

介紹
二叉查找樹，又稱二叉搜索樹、有序二叉樹、排序二叉樹。
它是特殊的二叉樹，對於二叉樹，假設x為二叉樹中的任意一個結點，x結點包含關鍵字key，結點x的key值記為key[ x ]。如果y是x的左子樹中的一個結點，則key[ y ] <= key[ x ]；如果y是x的右子樹中的一個結點，則key[ y ] >= key[ x ]；那麼，這棵樹就是二叉查找樹，如下圖所示：

二叉查找樹具有以下性質：

1）若任意結點的左子樹非空，則左子樹上所有結點的值均小於它的根節點的值
2）若任意結點的右子樹非空，則右子樹上所有結點的值均大於它的根節點的值
3）任意結點的左、右子樹葉分別為二叉查找樹
4）沒有鍵值相等的結點

算法實現
結點和二叉查找樹的定義

template<class T>
class BSTNode
{
public:
T key; // 關鍵字（鍵值）
BSTNode *left; // 左孩子
BSTNode *right; // 右孩子
BSTNode *parent; // 父結點

BSTNode(T value, BSTNode *p, BSTNode *l, BSTNode *r):
key(value),parent(p),left(l),right(r) {}
};

template<class T>
class BSTree
{
private:
BSTNode<T> *root; // 根結點

public:
BSTree(){};
~BSTree(){};

// 前序遍歷
void preOrder();
// 中序遍歷
void inOrder();
// 後序遍歷
void postOrder();

// （遞歸實現）查找二叉樹中鍵值為key的結點
BSTNode<T>* search(T key);
// （非遞歸實現） 查找二叉樹中鍵值為key的結點
BSTNode<T>* iterativeSearch(T key);

// 查找最小結點（返回鍵值）
T minimum();
// 查找最大結點（返回鍵值）
T maximum();

// 找結點（x）的後繼結點。即查找二叉樹中鍵值大於該結點的最小結點
BSTNode<T>* successor(BSTNode<T> *x);
// 找結點（x）的前驅結點。即查找二叉樹中鍵值小於該結點的最大結點
BSTNode<T>* predecessor(BSTNode<T> *x);

// 將鍵值為key的結點插入到二叉樹中
void insert(T key);

// 刪除鍵值為key的結點
void remove(T key);

// 銷毀二叉樹
void destroy();

// 打印二叉樹
void print();

private:
// 重載函數，提供內部接口
// 前序遍歷
void preOrder(BSTNode<T> *tree) const;
// 中序遍歷
void inOrder(BSTNode<T> *tree) const;
// 後序遍歷
void postOrder(BSTNode<T> *tree) const;

// （遞歸實現）查找二叉樹中鍵值為key的結點
BSTNode<T>* search(BSTNode<T> *x, T key) const;
// （非遞歸實現） 查找二叉樹中鍵值為key的結點
BSTNode<T>* iterativeSearch(BSTNode<T> *x, T key) const;

// 查找最小結點（返回鍵值）
BSTNode<T>* minimum(BSTNode<T> *tree);
// 查找最大結點（返回鍵值）
BSTNode<T>* maximum(BSTNode<T> *tree);

// 將結點z插入到二叉樹tree中
void insert(BSTNode<T>* &tree, BSTNode<T> *z);

// 刪除二叉樹中的結點z，並返回該結點
BSTNode<T>* remove(BSTNode<T>* &tree, BSTNode<T> *z);

// 銷毀二叉樹
void destroy(BSTNode<T>* &tree);

// 打印二叉樹
void print(BSTNode<T>* &tree, T key, int direction);
};

遍歷

前序遍歷

template<class T>
void BSTree<T>::preOrder(BSTNode<T> *tree) const
{
if(tree!=NULL)
{
cout<<tree->key<<" ";
preOrder(tree->left);
preOrder(tree->right);
}
}

template<class T>
void BSTree<T>::preOrder()
{
preOrder(root);
}

中序遍歷

template<class T>
void BSTree<T>::inOrder(BSTNode<T> *tree) const
{
if(tree!=NULL)
{
inOrder(tree->left);
cout<<tree->key<<" ";
inOrder(tree->right);
}
}

template<class T>
void BSTree<T>::inOrder()
{
inOrder(root);
}

後序遍歷

template<class T>
void BSTree<T>::postOrder(BSTNode<T> *tree) const
{
if(tree!=NULL)
{
postOrder(tree->left);
postOrder(tree->right);
cout<<tree->key<<" ";
}
}

template<class T>
void BSTree<T>::postOrder()
{
postOrder(root);
}

查找

遞歸方式進行查找

template<class T>
BSTNode<T>* BSTree<T>::search(BSTNode<T>* x, T key) const
{
if(x==NULL || x->key==key)
return x;
if(key<x->key)
search(x->left, key);
else
search(x->right, key);
}

template<class T>
BSTNode<T>* BSTree<T>::search(T key)
{
search(root, key);
}

非遞歸方式進行查找

template<class T>
BSTNode<T>* BSTree<T>::interativeSearch(BSTNode<T>* x, T key) const
{
while(x!=NULL && x->key!=key)
{
if(key<x->key)
x = x->left;
else
x = x->right;
}
return x;
}

template<class T>
BSTNode<T>* BSTree<T>::interativeSearch(T key)
{
interativeSearch(root, key);
}

最大值和最小值

查找最大值

template<class T>
BSTNode<T>* BSTree<T>::maximum(BSTNode<T> *tree)
{
if(tree==NULL)
return NULL;
while(tree->right!=NULL)
tree = tree->right;
return tree;
}

template<class T>
T BSTree<T>::maximum()
{
BSTNode<T> *p = maximum(root);
if(p!=NULL)
return p->key;
return (T)NULL;
}

查找最小值

template<class T>
BSTNode<T>* BSTree<T>::minimum(BSTNode<T> *tree)
{
if(tree==NULL)
return NULL;
while(tree->left!=NULL)
tree = tree->left;
return tree;
}

template<class T>
T BSTree<T>::minimum()
{
BSTNode<T> *p = minimum(root);
if(p!=NULL)
return p->key;
return (T)NULL;
}

前驅和後繼

查找前驅

template<class T>
BSTNode<T>* BSTree<T>::predecessor(BSTNode<T> *x)
{
// 如果x存在左孩子，則"x的前驅結點"為 "以其左孩子為根的子樹的最大結點"。
if(x->left!=NULL)
return maximum(x->left);
// 如果x沒有左孩子。則x有以下兩種可能：
// (1) x是"一個右孩子"，則"x的前驅結點"為 "它的父結點"。
// (2) x是"一個左孩子"，則查找"x的最低的父結點，並且該父結點要具有右孩子"，找到的這個"最低的父結點"就是"x的前驅結點"。
BSTNode<T> *p = x->parent;
while(p!=NULL && x==p->left)
{
x = p;
p = p->parent;
}
return p;
}

查找後繼

template<class T>
BSTNode<T>* BSTree<T>::successor(BSTNode<T> *x)
{
// 如果x存在右孩子，則"x的後繼結點"為 "以其右孩子為根的子樹的最小結點"。
if(x->right!=NULL)
return minimum(x->right);
// 如果x沒有右孩子。則x有以下兩種可能：
// (1) x是"一個左孩子"，則"x的後繼結點"為 "它的父結點"。
// (2) x是"一個右孩子"，則查找"x的最低的父結點，並且該父結點要具有左孩子"，找到的這個"最低的父結點"就是"x的後繼結點"。
BSTNode<T> *p = x->parent;
while(p!=NULL && x==p->right)
{
x = p;
p = p->parent;
}
return p;
}

插入

template<class T>
void BSTree<T>::insert(BSTNode<T>* &tree, BSTNode<T> *z)
{
BSTNode<T> *y = NULL;
BSTNode<T> *x = tree;

// 查找z的插入位置
while(x!=NULL)
{
y = x;
if(z->key < x->key)
x = x->left;
else // else if(z->key > x->key)
x = x->right;
// 若禁止插入相同鍵值
// else
// {
// free(z)；// 釋放之前分配的結點
// return;
// }
}
z->parent = y;
if(y==NULL)
tree = z;
else if(z->key<y->key)
y->left = z;
else
y->right = z;
}

template<class T>
void BSTree<T>::insert(T key)
{
BSTNode<T> *z = NULL;

// 如果新建結點失敗，則返回
if((z=new BSTNode<T>(key,NULL,NULL,NULL))==NULL)
return;

insert(root,z);
}

刪除

template<class T>
BSTNode<T>* BSTree<T>::remove(BSTNode<T>* &tree, BSTNode<T> *z)
{
BSTNode<T> *x = NULL;
BSTNode<T> *y = NULL;

if(z->left==NULL || z->right==NULL)
y = z;
else
y = successor(z);

if(y->left!=NULL)
x = y->left;
else
x = y->right;

if(x!=NULL)
x->parent = y->parent;

if(y->parent==NULL)
tree = x;
else if(y==y->parent->left)
y->parent->left = x;
else
y->parent->right = x;

if(y!=z)
z->key = y->key;
return y;
}

template<class T>
void BSTree<T>::remove(T key)
{
BSTNode<T> *z, *node;

if((z=search(root,key))!=NULL)
if((node=remove(root,z))!=NULL)
delete node;
}

打印

template<class T>
void BSTree<T>::print(BSTNode<T> *tree, T key, int direction)
{
if(tree!=NULL)
{
if(direction==0)
cout<<setw(2)<<tree->key<<"is root"<<endl;
else
cout<<setw(2)<<tree->key<<"is"<<setw(2)<<key<<"'s"<<setw(12)<<(direction==1 ? "right child":"left child")<<endl;
print(tree->left,tree->key,-1);
print(tree->right,tree->key,1);
}
}

template<class T>
void BSTree<T>::print()
{
if(root!=NULL)
print(root,root->key,0);
}

銷毀

template<class T>
void BSTree<T>::destroy(BSTNode<T> *&tree)
{
if(tree==NULL)
return ;
if(tree->left!=NULL)
return destroy(tree->left);
if(tree->right!=NULL)
return destroy(tree->right);

delete tree;
tree=NULL;
}

template<class T>
void BSTree<T>::destroy()
{
destroy(root);
}

二叉查找樹完整實現：BSTree.h

#ifndef BINARY_SEARCH_TREE
#define BINARY_SEARCH_TREE

#include<iomanip>
#include<iostream>
using namespace std;

template<class T>
class BSTNode
{
public:
T key; // 關鍵字（鍵值）
BSTNode *left; // 左孩子
BSTNode *right; // 右孩子
BSTNode *parent; // 父結點

BSTNode(T value, BSTNode *p, BSTNode *l, BSTNode *r):
key(value),parent(p),left(l),right(r) {}
};

template<class T>
class BSTree
{
private:
BSTNode<T> *root; // 根結點

public:
BSTree() {};
~BSTree() {};

// 前序遍歷
void preOrder();
// 中序遍歷
void inOrder();
// 後序遍歷
void postOrder();

// （遞歸實現）查找二叉樹中鍵值為key的結點
BSTNode<T>* search(T key);
// （非遞歸實現） 查找二叉樹中鍵值為key的結點
BSTNode<T>* iterativeSearch(T key);

// 查找最小結點（返回鍵值）
T minimum();
// 查找最大結點（返回鍵值）
T maximum();

// 找結點（x）的後繼結點。即查找二叉樹中鍵值大於該結點的最小結點
BSTNode<T>* successor(BSTNode<T> *x);
// 找結點（x）的前驅結點。即查找二叉樹中鍵值小於該結點的最大結點
BSTNode<T>* predecessor(BSTNode<T> *x);

// 將鍵值為key的結點插入到二叉樹中
void insert(T key);

// 刪除鍵值為key的結點
void remove(T key);

// 銷毀二叉樹
void destroy();

// 打印二叉樹
void print();

private:
// 重載函數，提供內部接口
// 前序遍歷
void preOrder(BSTNode<T> *tree) const;
// 中序遍歷
void inOrder(BSTNode<T> *tree) const;
// 後序遍歷
void postOrder(BSTNode<T> *tree) const;

// （遞歸實現）查找二叉樹中鍵值為key的結點
BSTNode<T>* search(BSTNode<T> *x, T key) const;
// （非遞歸實現） 查找二叉樹中鍵值為key的結點
BSTNode<T>* iterativeSearch(BSTNode<T> *x, T key) const;

// 查找最小結點（返回鍵值）
BSTNode<T>* minimum(BSTNode<T> *tree);
// 查找最大結點（返回鍵值）
BSTNode<T>* maximum(BSTNode<T> *tree);

// 將結點z插入到二叉樹tree中
void insert(BSTNode<T>* &tree, BSTNode<T> *z);

// 刪除二叉樹中的結點z，並返回該結點
BSTNode<T>* remove(BSTNode<T>* &tree, BSTNode<T> *z);

// 銷毀二叉樹
void destroy(BSTNode<T>* &tree);

// 打印二叉樹
void print(BSTNode<T>* &tree, T key, int direction);
};

template<class T>
void BSTree<T>::preOrder(BSTNode<T> *tree) const
{
if(tree!=NULL)
{
cout<<tree->key<<" ";
preOrder(tree->left);
preOrder(tree->right);
}
}

template<class T>
void BSTree<T>::preOrder()
{
preOrder(root);
}

template<class T>
void BSTree<T>::inOrder(BSTNode<T> *tree) const
{
if(tree!=NULL)
{
inOrder(tree->left);
cout<<tree->key<<" ";
inOrder(tree->right);
}
}

template<class T>
void BSTree<T>::inOrder()
{
inOrder(root);
}

template<class T>
void BSTree<T>::postOrder(BSTNode<T> *tree) const
{
if(tree!=NULL)
{
postOrder(tree->left);
postOrder(tree->right);
cout<<tree->key<<" ";
}
}

template<class T>
void BSTree<T>::postOrder()
{
postOrder(root);
}

template<class T>
BSTNode<T>* BSTree<T>::search(BSTNode<T>* x, T key) const
{
if(x==NULL || x->key==key)
return x;
if(key<x->key)
return search(x->left, key);
else
return search(x->right, key);
}

template<class T>
BSTNode<T>* BSTree<T>::search(T key)
{
search(root, key);
}

template<class T>
BSTNode<T>* BSTree<T>::iterativeSearch(BSTNode<T>* x, T key) const
{
while(x!=NULL && x->key!=key)
{
if(key<x->key)
x = x->left;
else
x = x->right;
}
return x;
}

template<class T>
BSTNode<T>* BSTree<T>::iterativeSearch(T key)
{
iterativeSearch(root, key);
}

template<class T>
BSTNode<T>* BSTree<T>::maximum(BSTNode<T> *tree)
{
if(tree==NULL)
return NULL;
while(tree->right!=NULL)
tree = tree->right;
return tree;
}

template<class T>
T BSTree<T>::maximum()
{
BSTNode<T> *p = maximum(root);
if(p!=NULL)
return p->key;
return (T)NULL;
}

template<class T>
BSTNode<T>* BSTree<T>::minimum(BSTNode<T> *tree)
{
if(tree==NULL)
return NULL;
while(tree->left!=NULL)
tree = tree->left;
return tree;
}

template<class T>
T BSTree<T>::minimum()
{
BSTNode<T> *p = minimum(root);
if(p!=NULL)
return p->key;
return (T)NULL;
}

template<class T>
BSTNode<T>* BSTree<T>::predecessor(BSTNode<T> *x)
{
// 如果x存在左孩子，則"x的前驅結點"為 "以其左孩子為根的子樹的最大結點"。
if(x->left!=NULL)
return maximum(x->left);
// 如果x沒有左孩子。則x有以下兩種可能：
// (1) x是"一個右孩子"，則"x的前驅結點"為 "它的父結點"。
// (2) x是"一個左孩子"，則查找"x的最低的父結點，並且該父結點要具有右孩子"，找到的這個"最低的父結點"就是"x的前驅結點"。
BSTNode<T> *p = x->parent;
while(p!=NULL && x==p->left)
{
x = p;
p = p->parent;
}
return p;
}

template<class T>
BSTNode<T>* BSTree<T>::successor(BSTNode<T> *x)
{
// 如果x存在右孩子，則"x的後繼結點"為 "以其右孩子為根的子樹的最小結點"。
if(x->right!=NULL)
return minimum(x->right);
// 如果x沒有右孩子。則x有以下兩種可能：
// (1) x是"一個左孩子"，則"x的後繼結點"為 "它的父結點"。
// (2) x是"一個右孩子"，則查找"x的最低的父結點，並且該父結點要具有左孩子"，找到的這個"最低的父結點"就是"x的後繼結點"。
BSTNode<T> *p = x->parent;
while(p!=NULL && x==p->right)
{
x = p;
p = p->parent;
}
return p;
}

template<class T>
void BSTree<T>::insert(BSTNode<T>* &tree, BSTNode<T> *z)
{
BSTNode<T> *y = NULL;
BSTNode<T> *x = tree;

// 查找z的插入位置
while(x!=NULL)
{
y = x;
if(z->key < x->key)
x = x->left;
else // else if(z->key > x->key)
x = x->right;
// 若禁止插入相同鍵值
// else
// {
// free(z)；// 釋放之前分配的結點
// return;
// }
}
z->parent = y;
if(y==NULL)
tree = z;
else if(z->key<y->key)
y->left = z;
else
y->right = z;
}

template<class T>
void BSTree<T>::insert(T key)
{
BSTNode<T> *z = NULL;

// 如果新建結點失敗，則返回
if((z=new BSTNode<T>(key,NULL,NULL,NULL))==NULL)
return;

insert(root,z);
}

template<class T>
BSTNode<T>* BSTree<T>::remove(BSTNode<T>* &tree, BSTNode<T> *z)
{
BSTNode<T> *x = NULL;
BSTNode<T> *y = NULL;

if(z->left==NULL || z->right==NULL)
y = z;
else
y = successor(z);

if(y->left!=NULL)
x = y->left;
else
x = y->right;

if(x!=NULL)
x->parent = y->parent;

if(y->parent==NULL)
tree = x;
else if(y==y->parent->left)
y->parent->left = x;
else
y->parent->right = x;

if(y!=z)
z->key = y->key;
return y;
}

template<class T>
void BSTree<T>::remove(T key)
{
BSTNode<T> *z, *node;

if((z=search(root,key))!=NULL)
if((node=remove(root,z))!=NULL)
delete node;
}

template<class T>
void BSTree<T>::print(BSTNode<T> *&tree, T key, int direction)
{
if(tree!=NULL)
{
if(direction==0)
cout<<setw(2)<<tree->key<<"is root"<<endl;
else
cout<<setw(2)<<tree->key<<"is"<<setw(2)<<key<<"'s"<<setw(12)<<(direction==1 ? "right child":"left child")<<endl;
print(tree->left,tree->key,-1);
print(tree->right,tree->key,1);
}
}

template<class T>
void BSTree<T>::print()
{
if(root!=NULL)
print(root,root->key,0);
}

template<class T>
void BSTree<T>::destroy(BSTNode<T> *&tree)
{
if(tree==NULL)
return ;
if(tree->left!=NULL)
return destroy(tree->left);
if(tree->right!=NULL)
return destroy(tree->right);

delete tree;
tree=NULL;
}

template<class T>
void BSTree<T>::destroy()
{
destroy(root);
}

#endif

測試代碼：BSTreeTest.cpp

#include<iostream>
#include "BSTree.h"
using namespace std;

static int arr[] = {1,5,4,3,2,6};

int main()
{
int i,len;
BSTree<int> *tree = new BSTree<int>();

cout<<"依次添加：";
len = sizeof(arr)/sizeof(arr[0]);
for(i=0;i<len;++i)
{
cout<<arr[i]<<" ";
tree->insert(arr[i]);
}

cout<<"\n前序遍歷：";
tree->preOrder();
cout<<"\n中序遍歷：";
tree->inOrder();
cout<<"\n後序遍歷：";
tree->postOrder();
cout<<endl;

cout<<"最小值："<<tree->minimum()<<endl;
cout<<"最大值："<<tree->maximum()<<endl;
cout<<"樹的詳細信息："<<endl;
tree->print();

cout<<" \n刪除根節點："<<arr[3];
tree->remove(arr[3]);

cout<<"\n中序遍歷：";
tree->inOrder();
cout<<endl;

// 銷毀二叉樹
tree->destroy();

return 0;
}