23、二叉排序树(BST, Binary SortTree) 的C++实现

　　二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。

　　(1)二叉排序树定义：二叉排序树或者是空树，或者是满足如下性质的二叉树：

　　①若它的左子树非空，则左子树上所有结点的值均小于根结点的值;

　　②若它的右子树非空，则右子树上所有结点的值均大于根结点的值;

　　③左、右子树本身又各是一棵二叉排序树。

　　上述性质简称二叉排序树性质(BST性质)，故二叉排序树实际上是满足BST性质的二叉树。

　　(2)二叉排序树的特点

　　由BST性质可得：

　　[1]二叉排序树中任一结点x，其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。

　　[2]二叉排序树中，各结点关键字是惟一的。 注意：实际应用中，不能保证被查找的数据集中各元素的关键字互不相同，所以可将二叉排序树定义中BST性质[1]里的"小于"改为"小于等于"，或将BST性质[2]里的"大于"改为"大于等于"，甚至可同时修改这两个性质。

　　[3]按中序遍历该树所得到的中序序列是一个递增有序序列。

　　(3)在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关：

　　①在最坏情况下，二叉排序树是通过把一个有序表的n个结点依次插入而生成的，此时所得的二叉排序树蜕化为棵深度为n的单支树，它的平均查找长度和单链表上的顺序查找相同，亦是(n+1)/2。

　　②在最好情况下，二叉排序树在生成的过程中，树的形态比较匀称，最终得到的是一棵形态与二分查找的判定树相似的二叉排序树，此时它的平均查找长度大约是lgn。

　　③插入、删除和查找算法的时间复杂度均为O(lgn)。

　　(4)二叉排序树和二分查找的比较

　　就平均时间性能而言，二叉排序树上的查找和二分查找差不多。

　　就维护表的有序性而言，二叉排序树无须移动结点，只需修改指针即可完成插入和删除操作，且其平均的执行时间均为O(lgn)，因此更有效。二分查找所涉及的有序表是一个向量，若有插入和删除结点的操作，则维护表的有序性所花的代价是O(n)。当有序表是静态查找表时，宜用向量作为其存储结构，而采用二分查找实现其查找操作;若有序表里动态查找表，则应选择二叉排序树作为其存储结构。

　　//二叉查找树代码

　　//BTreeNode.h二叉树结点抽象类型

　　#ifndefBTREENODE_H

　　#defineBTREENODE_H

　　#include

　　//template class BTree;

　　template class SortBTree;

　　template class BTreeNode

　　{

　　//friend class BTree;

　　friend class SortBTree;

　　public:

　　BTreeNode():lchild(NULL),rchild(NULL){ };

　　BTreeNode(const T&dt,BTreeNode *lch =NULL , BTreeNode *rch = NULL)

　　:data(dt),lchild(lch),rchild(rch){};

　　T get_data()const {return data; };

　　BTreeNode* get_lchild()const{return lchild; };

　　BTreeNode* get_rchild()const{return rchild; };

　　void set_data(const T& d) { data =d;};

　　protected:

　　private:

　　T data;

　　BTreeNode *lchild, *rchild;

　　};

　　#endif

　　
/***************************************************************
*********

　　*SortBTree.h

　　* 根据给定的字符串构造一个排序二叉树

　　* 从排序二叉树中寻找最大值，最小值，不存在时抛出invalid_argument异常

　　* 从排序二叉树中删除某一元素，不存在时抛出invalid_argument 异常

　　* 往排序二叉树中添加一个新元素

　　************************************************
************************/ [NextPage]

　　#ifndefSORTBTREE_H

　　#defineSORTBTREE_H

　　#include"BTreeNode.h"

　　#include

　　#include

　　template

　　classSortBTree

　　{

　　public:

　　SortBTree(T* p , int n);

　　const T& max()const; // return themaximum

　　const T& min()const; // return theminimum

　　BTreeNode* find_data(const T&data)const; //return the node of data, if data is not exist, throw error

　　//delete the node of data, if data is notexist, throw error

　　void delete_data(const T& data) {delete_data(root,data); };

　　void insert_data(const T& data) { insert_data(root,data);};

　　BTreeNode* get_root()const {returnroot; }; // return the root of tree

　　void display()const { display(root,visit); cout <

　　protected:

　　static void insert_data(BTreeNode *&root, const T& ndata); //这里必须是对指针的引用,切记，切记

　　static BTreeNode*find_data(BTreeNode* r,const T& data);

　　static void delete_node(BTreeNode* &p);

　　static void delete_data(BTreeNode*&r, const T& data);

　　static void display(BTreeNode*p,void visit(BTreeNode* p));

　　private:

　　BTreeNode *root;

　　};

　　//constructionfunction

　　template

　　SortBTree::SortBTree(T*p, int n)

　　{

　　root = new BTreeNode;

　　root = NULL; //注意这行很必要，BTreeNode没有默认设置为NULL的构造函数

　　for(int i = 0; i != n; ++i)

　　{

　　insert_data(root,p[i]);

　　}

　　}

　　//insert a new data

　　template

　　voidSortBTree::insert_data(BTreeNode *&rt,const T& ndata)

　　{

　　if(rt == NULL)

　　{

　　rt = newBTreeNode(ndata,NULL,NULL);

　　//rt->data = ndata; //这三条语句不等于上面那条

　　//rt->lchild = NULL; //用这三条语句是错的

　　//rt->rchild = NULL;

　　}

　　else if(rt->data == ndata) return;

　　else if(rt->data > ndata)insert_data(rt->lchild, ndata);

　　else insert_data(rt->rchild, ndata);

　　}

　　//delete a node from tree(improved)

　　// 如果p没有左子树，则让p的右子树的根代替p即可。

　　// 如果p有左子树，找出左子树中结点值最大的节点temp(最右下角的结点，也是中序遍历最后一个结点， 他没有右子树)

　　// 用temp的结点值替换下p的结点值

　　// 删除temp(因为temp的右子树为空，从而直接用其左子树根代替本身就可达到删除结点的目的)

　　// 注： 一般的方法用temp替换p，但是这样可能导致树很不平衡。 [NextPage]

　　template

　　voidSortBTree::delete_node(BTreeNode * &p)

　　{

　　if(p == NULL) cout << "There isnot this node." <

　　else if(p->lchild == NULL) p =p->rchild;

　　else

　　{

　　BTreeNode* temp = p;

　　//记录左子树中序遍历的最后一个结点(值最大的点)

　　while(temp->rchild != NULL)

　　temp = temp->rchild;

　　//删除这个结点，等价于用这个结点的做子树代替这个结点(因为这个结点没有右子树)

　　BTreeNode* parent;

　　parent = temp;

　　while(parent->rchild != NULL)

　　{

　　parent = temp;

　　temp = temp->rchild;

　　}

　　parent = temp->lchild;

　　p->set_data(temp->data);

　　}

　　}

　　//deletea data

　　template

　　voidSortBTree::delete_data(BTreeNode* &root, const T&data)

　　{

　　if(root == NULL)

　　throw std::invalid_argument("Thisdata is not exsit.");

　　else if(root->data == data)delete_node(root);

　　else if(root->data > data)delete_data(root->lchild,data);

　　else delete_data(root->rchild,data);

　　}

　　//find a specific data

　　template

　　BTreeNode* SortBTree::find_data(BTreeNode*r,const T& data)

　　{

　　if(r == NULL) return r;

　　else if(r->data == data) return r; //注意这两行是不能合并在一起的，不然可能会出现NULL->data呢

　　else if(r->data > data) returnfind_data(r->lchild,data);

　　else return find_data(r->rchild,data);

　　}

　　//find a specific data in tree

　　template

　　BTreeNode*SortBTree::find_data(const T& data)const

　　{

　　if(find_data(root,data) == NULL)

　　throw std::invalid_argument("Thisdata is not exist.");

　　else

　　return find_data(root,data);

　　}

　　//return the maximum value

　　template

　　constT& SortBTree::max()const

　　{

　　if(root == NULL)

　　throw std::invalid_argument("Thisis an empty Tree.");

　　else

　　{

　　BTreeNode *q = root;

　　while(q->rchild != NULL)

　　q = q->rchild;

　　return q->data;

　　}

　　}

　　//returnthe minimum value

　　template

　　constT& SortBTree::min()const

　　{

　　if(root == NULL)

　　throw std::invalid_argument("Thisis an empty Tree.");

　　else

　　{

　　BTreeNode *q = root;

　　while(q->lchild != NULL)

　　q = q->lchild;

　　return q->data;

　　}

　　}

　　//printthe sort tree

　　template

　　voidSortBTree::display(BTreeNode*p, voidvisit(BTreeNode* p))

　　{

　　if(p != NULL)

　　{

　　display(p->lchild,visit);

　　visit(p);

　　display(p->rchild,visit);

　　}

　　}

　　#endif