带索引的二叉搜索树.docx
《带索引的二叉搜索树.docx》由会员分享，可在线阅读，更多相关《带索引的二叉搜索树.docx（36页珍藏版）》请在冰点文库上搜索。
带索引的二叉搜索树
带索引的二叉搜索树
//file:
indexedBSTree.h
#pragmaonce
#include"BSTree.h"
template
classIndexedBSTree:
publicBSTree
{
public:
voidCreate（）;
boolSearch（constK&k,E&e）const;
boolIndexSearch（intk,E&e）const;
IndexedBSTree&Insert（constE&e）;
IndexedBSTree&Delete（constK&k,E&e）;
IndexedBSTree&IndexDelete（intk,E&e）;
voidAscend（）;
voidIndexOutput（）;
private:
staticvoidOutputLeftSize（BinaryTreeNode*t）;
};
template
voidIndexedBSTree:
:
Create（）
{//产生一个空的带索引的二叉搜索树
root=0;
}
template
boolIndexedBSTree:
:
Search（constK&k,E&e）const
{//将关键值为k的元素返回到e中；如果操作失败返回false，否则返回true
returnBSTree:
:
Search（k,e）;
}
template
boolIndexedBSTree:
:
IndexSearch（intk,E&e）const
{//将第k个元素返回到e中
if（!
root）
returnfalse;
BinaryTreeNode*p=root;
while（p）
{
if（kLeftSize）
p=p->LeftChild;
elseif（k>p->LeftSize）
{
k-=p->LeftSize;
p=p->RightChild;
}
else
{
e=p->data;
returntrue;
}
}
returnfalse;
}
template
IndexedBSTree&IndexedBSTree:
:
Insert（constE&e）
{
BSTree:
:
Insert（e）;
BinaryTreeNode*t=root;
while（t）
{
if（edata）
{
t->LeftSize++;
t=t->LeftChild;
}
elseif（e>t->data）
t=t->RightChild;
else
{
t->LeftSize=1;
return*this;
}
}
}
template
IndexedBSTree&IndexedBSTree:
:
Delete（constK&k,E&e）
{//删除关键值为k的元素并且将其返回到e中
//将p指向关键值为k的节点
BinaryTreeNode*p=root,//搜索指针
*pp=0;//p的父节点指针
while（p&&p->data!
=k）
{//移动到p的孩子
pp=p;
if（kdata）
{
p=p->LeftChild;
}
else
p=p->RightChild;
}
if（!
p）
throwBadInput（）;//没有关键值为k的元素
e=p->data;//保存欲删除的元素
BinaryTreeNode*t=root;//搜索指针
while（t&&t->data!
=k）
{//移动到p的孩子
if（kdata）
{
t->LeftSize--;
t=t->LeftChild;
}
else
t=t->RightChild;
}
//对树进行重构
//处理p有两个孩子的情形
if（p->LeftChild&&p->RightChild）
{//两个孩子
//转换成有0或1个孩子的情形
//在p的左子树中寻找最大元素
BinaryTreeNode*s=p->LeftChild,*ps=p;//s的父节点
while（s->RightChild）
{//移动到较大的元素
ps=s;
s=s->RightChild;
}
p->LeftSize=p->LeftSize-1;//修改所删除元素的索引值
//将最大元素从s移动到p
p->data=s->data;
p=s;
pp=ps;
}
//p最多有一个孩子
//在c中保存孩子指针
BinaryTreeNode*c;
if（p->LeftChild）
c=p->LeftChild;
else
c=p->RightChild;
//删除p
if（p==root）
root=c;
else
{//p是pp的左孩子还是pp的右孩子？
if（p==pp->LeftChild）
{
pp->LeftChild=c;
}
else
pp->RightChild=c;
}
deletep;
return*this;
}
template
IndexedBSTree&IndexedBSTree:
:
IndexDelete（intk,E&e）
{//删除第k个元素并将其返回到e中
BinaryTreeNode*p=root,
*pp=0;//指向第k个元素的父节点
//寻找删除点
while（p&&k!
=p->LeftSize）
{
pp=p;
if（kLeftSize）
{
p=p->LeftChild;
}
elseif（k>p->LeftSize）
{
k-=p->LeftSize;
p=p->RightChild;
}
}
if（!
p）
throwBadInput（）;//没有关键值为k的元素
e=p->data;//保存欲删除的元素
//调整LeftSize值
BinaryTreeNode*t=root;//搜索指针
while（p&&k!
=t->LeftSize）
{//移动到t的孩子
if（kLeftSize）
{
t=t->LeftChild;
}
elseif（k>p->LeftSize）
{
k-=t->LeftSize;
t=t->RightChild;
}
}
//对树进行重构
//处理p有两个孩子的情形
if（p->LeftChild&&p->RightChild）
{//两个孩子
//转换成有0或1个孩子的情形
//在p的左子树中寻找最大元素
BinaryTreeNode*s=p->LeftChild,*ps=p;//s的父节点
while（s->RightChild）
{//移动到较大的元素
ps=s;
s=s->RightChild;
}
p->LeftSize=p->LeftSize-1;//修改所删除元素的索引值
//将最大元素从s移动到p
p->data=s->data;
p=s;
pp=ps;
}
//p最多有一个孩子
//在c中保存孩子指针
BinaryTreeNode*c;
if（p->LeftChild）
c=p->LeftChild;
else
c=p->RightChild;
//删除p
if（p==root）
root=c;
else
{//p是pp的左孩子还是pp的右孩子？
if（p==pp->LeftChild）
{
pp->LeftChild=c;
}
else
pp->RightChild=c;
}
deletep;
return*this;
}
template
voidIndexedBSTree:
:
Ascend（）
{//按照关键值的升序排列输出所有元素
InOutput（）;
}
template
voidIndexedBSTree:
:
IndexOutput（）
{//中序遍历，输出节点元素的索引值
InOrder（OutputLeftSize,root）;
cout<}
template
voidIndexedBSTree:
:
OutputLeftSize（BinaryTreeNode*t）
{//输出节点元素的索引值
cout<LeftSize<<'';
}
//file:
BSTree.h
#pragmaonce
#include"binaryTree.h"
template
classBSTree:
publicBinaryTree
{
public:
boolSearch（constK&k,E&e）const;
BSTree&Insert（constE&e）;
BSTree&Delete（constK&k,E&e）;
voidAscend（）{InOutput（）;}
voidtraversalBSTree（inta[]）;
voidtraversalBSTree0（BinaryTreeNode*t,int&pos,inta[]）;
BSTree&DeleteMax（E&x）;
};
template
boolBSTree:
:
Search（constK&k,E&e）const
{//搜索与k匹配的元素
//指针p从树根开始进行查找
if（!
root）
returnfalse;
BinaryTreeNode*p=root;
while（p）//检查p->data
{
if（kdata）
p=p->LeftChild;
elseif（k>p->data）
p=p->RightChild;
else
{
e=p->data;
returntrue;
}
}
returnfalse;
}
template
BSTree&BSTree:
:
Insert（constE&e）
{//如果不出现重复，则插入e
BinaryTreeNode*p=root,//搜索指针
*pp=0;
//寻找插入点
while（p）
{//检查p->data
pp=p;
//将p移向孩子节点
if（edata）
p=p->LeftChild;
elseif（e>p->data）
p=p->RightChild;
else
throwBadInput（）;//出现重复
}
//为e建立一个节点，并将该节点连接至pp
BinaryTreeNode*r=newBinaryTreeNode（e）;
if（root）
{//树非空
if（edata）
pp->LeftChild=r;
else
pp->RightChild=r;
}
else//插入到空树
root=r;
return*this;
}
template
BSTree&BSTree:
:
Delete（constK&k,E&e）
{//删除关键值为k的元素，并将其放入e
//将p指向关键值为k的节点
BinaryTreeNode*p=root,//搜索指针
*pp=0;//p的父节点指针
while（p&&p->data!
=k）
{//移动到p的孩子
pp=p;
if（kdata）
p=p->LeftChild;
else
p=p->RightChild;
}
if（!
p）
throwBadInput（）;//没有关键值为k的元素
e=p->data;//保存欲删除的元素
//对树进行重构
//处理p有两个孩子的情形
if（p->LeftChild&&p->RightChild）
{//两个孩子
//转换成有0或1个孩子的情形
//在p的左子树中寻找最大元素
BinaryTreeNode*s=p->LeftChild,*ps=p;//s的父节点
while（s->RightChild）
{//移动到较大的元素
ps=s;
s=s->RightChild;
}
//将最大元素从s移动到p
p->data=s->data;
p=s;
pp=ps;
}
//p最多有一个孩子
//在c中保存孩子指针
BinaryTreeNode*c;
if（p->LeftChild）
c=p->LeftChild;
else
c=p->RightChild;
//删除p
if（p==root）
root=c;
else
{//p是pp的左孩子还是pp的右孩子？
if（p==pp->LeftChild）
pp->LeftChild=c;
else
pp->RightChild=c;
}
deletep;
return*this;
}
template
voidBSTree:
:
traversalBSTree（inta[]）
{
intpos=0;
traversalBSTree0（root,pos,a）;
}
template
voidBSTree:
:
traversalBSTree0（BinaryTreeNode*t,int&pos,inta[]）
{
if（!
t）
return;
traversalBSTree0（t->LeftChild,pos,a）;
a[pos++]=t->data;
traversalBSTree0（t->RightChild,pos,a）;
}
template
BSTree&BSTree:
:
DeleteMax（E&x）
{
if（!
root）
throwOutOfBounds（）;
BinaryTreeNode*p=root,
*pp=0;
while（p->RightChild）
{
pp=p;
p=p->RightChild;
}
x=p->data;
if（p==root）
root=p->LeftChild;
else
pp->RightChild=p->LeftChild;
deletep;
return*this;
}
//file:
binaryTree.h
#ifndef_BINARYTREE_H_
#define_BINARYTREE_H_
#include"BinaryTreeNode.h"
#include"linkedQueue.h"
#include"exception.h"
int_count=0;
template
classBinaryTree
{
template
friendclassIndexedBSTree;
template
friendclassBSTree;
public:
BinaryTree（）{root=0;}
~BinaryTree（）{}
boolIsEmpty（）const{return（（root）?
false:
true）;}
boolRoot（T&x）const;
voidSetRoot（BinaryTreeNode*t）{root=t;}
BinaryTreeNode*GetRoot（）{returnroot;}
voidMakeTree（constT&element,BinaryTree&left,BinaryTree&right）;
voidBreakTree（T&element,BinaryTree&left,BinaryTree&right）;
voidPreOrder（void（*Visit）（BinaryTreeNode*u））
{PreOrder（Visit,root）;}
voidInOrder（void（*Visit）（BinaryTreeNode*u））
{InOrder（Visit,root）;}
voidPostOrder（void（*Visit）（BinaryTreeNode*u））
{PostOrder（Visit,root）;}
voidLevelOrder（void（*Visit）（BinaryTreeNode*u））;
voidPreOutput（）
{PreOrder（Output,root）;cout<voidInOutput（）
{InOrder（Output,root）;cout<voidPostOutput（）
{PostOrder（Output,root）;cout<voidLevelOutput（）
{LevelOrder（Output）;cout<voidDelete（）
{PostOrder（Free,root）;root=0;}
intHeight（）const
{returnHeight（root）;}
intSize（）;
BinaryTreeNode*search（Telement）{returnsearch（element,root）;}
BinaryTreeNode*copy（BinaryTreeNode*t）;
intNumLeaves（）
{returnCountLeaf（root）;}
voidSwap（）
{Swap0（root）;}
boolCompare（BinaryTree&X）
{returnCompare1（root,X.root）;}
boolIsHBLT（）
{returnIsHBLT（root）;}
private:
BinaryTreeNode*root;//根节点指针
voidPreOrder（void（*Visit）（BinaryTreeNode*u）,BinaryTreeNode*t）;
voidInOrder（void（*Visit）（BinaryTreeNode*u）,BinaryTreeNode*t）;
voidPostOrder（void（*Visit）（BinaryTreeNode*u）,BinaryTreeNode*t）;
staticvoidOutput（BinaryTreeNode*t）;
staticvoidFree（BinaryTreeNode*t）{deletet;}
intHeight（BinaryTreeNode*t）const;
staticvoidAdd1（BinaryTreeNode*t）{_count++;}
//intCount（BinaryTreeNode*t）const;
BinaryTreeNode*search（T&element,BinaryTreeNode*t）;
intCountLeaf（BinaryTreeNode*t）;
voidSwap0（BinaryTreeNode*t）;
boolCompare1（BinaryTreeNode*p,BinaryTreeNode*t）;
boolIsHBLT（BinaryTreeNode*t）;
};
t
升级会员 