二叉排序树(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 异常
* 往排序二叉树中添加一个新元素
************************************************************************/
#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 << of data the print p>
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，但是这样可能导致树很不平衡。
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
济宁人力资源和社会保障局济宁2015年下半年软考证书领取联系电话
[考试动态]2016年4月26日邹城人力资源和社会保障局邹城2015年下半年软考补办证书合格人员名单
[考试动态]2016年4月26日邹城人力资源和社会保障局邹城2015年下半年软考证书领取联系电话
[考试动态]2016年4月26日邹城人力资源和社会保障局邹城2015年下半年软考证书领取办理方式
[考试动态]2016年4月26日邹城人力资源和社会保障局邹城2015年下半年软考合格人员名单
[考试动态]2016年4月26日