首页 >
BS搜索树的插入,删除,搜索等基本操作
BS搜索树的插入,删除,搜索等基本操作
2018-03-21 23页 doc 50KB 15阅读
is_496339
暂无简介
举报
BS搜索树的插入,删除,搜索等基本操作BS搜索树的插入,删除,搜索等基本操作
template
class stack
{public:
int top;
int maxtop;
T *sck;
public:
stack(int maxstacksize=10) {maxtop=maxstacksize-1;
sck=new T[maxstacksize];
top=-1;
}
virtual ~stack(){
delete [] sck;}
bool isempty() const {return top==-1;}
bool...
BS搜索树的插入,删除,搜索等基本操作
template
class stack
{public:
int top;
int maxtop;
T *sck;
public:
stack(int maxstacksize=10) {maxtop=maxstacksize-1;
sck=new T[maxstacksize];
top=-1;
}
virtual ~stack(){
delete [] sck;}
bool isempty() const {return top==-1;}
bool isfull() const {return top==maxtop;}
T Top() const {//if(isempty()) throw OutOfBounds();
return sck[top];
}
stack& add(const T& x)
{//if(isfull()) throw NoMem();
sck[++top]=x;
return *this;
}
stack& Delete(T& x){
//if(isempty()) throw OutOfBounds();
x=sck[top--];
return *this;
}
void makeempty(){top=-1;} void ouput(){
for(int i=0;i<=top;i++)
cout<
class BSTree : public binarytree {
public:
BSTree(){root=0;}
bool Search(const K& k, E& e) const{
binarytreenode *p = root,*pp=0;
while (p)
if (k < p->data) p = p->leftchild;
else if (k > p->data) p = p->rightchild;
else {
e = p->data;
return true;}
return false;}
BSTree& Insert(const E& e){
binarytreenode *p = root,
*pp = 0;
while (p) {
pp = p;
if (e < p->data) p = p->leftchild;
else if (e > p->data) p = p->rightchild;
//else throw BadInput();
}
binarytreenode *r = new binarytreenode (e);
if (root) {
if (e < pp->data) pp->leftchild = r;
else pp->rightchild = r;}
else
root = r;
return *this;}
BSTree& Delete(const K& k, E& e){
binarytreenode *p = root,
*pp = 0;
while (p && p->data != k){
pp = p;
if (k < p->data) p = p->leftchild;
else p = p->rightchild;
}
//if (!p) throw BadInput();
e = p->data;
if (p->leftchild && p->rightchild) {
binarytreenode *s = p->leftchild,
*ps = p;
while (s->rightchild) {
ps = s;
s = s->rightchild;}
p->data = s->data;
p = s;
pp = ps;}
binarytreenode *c;
if (p->leftchild) c = p->leftchild;
else c = p->rightchild;
if (p == root) root = c;
else {
if (p == pp->leftchild)
pp->leftchild = c;
else pp->rightchild = c;}
delete p;
return *this;}
void Ascend() {inorder(root);}
binarytreenode *root;
};
#ifndef MINHEAP_H
#define MINHEAP_H
#include
using namespace std;
template
class MinHeap {
public:
int CurrentSize, MaxSize;
T *heap; // ÔªËØÊý×é
MinHeap(int MinHeapSize = 10){
MaxSize=MinHeapSize;
heap=new T[MaxSize+1];
CurrentSize=0;}
~MinHeap() {delete [] heap;}
int Size() con T Min() {if (CurrentSize == 0) throw
OutOfBounds();
return heap[1];}
MinHeap& Insert(const T& x){if (CurrentSize==MaxSize)
throw NoMem();
int i=++CurrentSize;
while (i!=1 && x& DeleteMax(T& x){if (CurrentSize==0)
throw OutOfBounds();
x=heap[1];
T y=heap[CurrentSize--];
int i=1,
ci=2;
while (ci<=CurrentSize) {
if(ciheap[ci+1]) ci++;
//ÄÜ?Ñy?ÅÈëheap[i]Âð??
if (y<=heap[ci]) break;
heap[i]=heap[ci];
i=ci;
ci*=2;
}
heap[i]=y;
return *this;}
void Initialize(T a[], int size, int ArraySize){
delete [] heap;
heap=a;
CurrentSize=size;
MaxSize=ArraySize;
for(int i=CurrentSize/2;i>=1;i--) {T y=heap[i];
int c=2*i;
while(c<=CurrentSize){
if(cheap[c+1]) c++;
if(y<=heap[c]) break;
heap[c/2]=heap[c];
c*=2;}
heap[c/2]=y;
}
}
void output(){
for(int i=1;i<=CurrentSize;i++)
cout<
class Huffman
{ public:
binarytree HuffmanTree(T a[],int p[],int n)
{
Huffman *w=new Huffman [n+1];
binarytree z,zero;
for(int i=1;i<=n;i++)
{
z.maketree(p[i],zero,zero);
w[i].weight=a[i];
w[i].tree=z;
}
MinHeap > H(1);
H.Initialize(w,n,n);
Huffman x,y;
for(int i=1;i tree;
T weight;
};
#endif // HUFFMAN_H #ifndef LINKEDQUEUE_H #define LINKEDQUEUE_H
#include using namespace std; class OutOfBounds {
public:
OutOfBounds() {cout << "OutOfBounds Error!" << endl;}
};
class NoMem
{
public:
NoMem() {cout << "NoMem Error!" << endl;}
};
template class Node
{
public:
T m_tData;
Node *m_tNext; };
template class LinkedQueue {
public:
LinkedQueue(){m_nFront = m_nLast = NULL;}
virtual ~LinkedQueue(){Node *p;
while (m_nFront)
{
p = m_nFront->m_tNext; delete m_nFront;
m_nFront = p;
}}
bool IsEmpty() const {return m_nFront == NULL;}
bool IsFull() const {try{ Node *p = new Node; delete p;
return false;
}
catch(...)
{
return true;
}}
int Size() const{int nSize = 0; Node *p = m_nLast; while (p)
{
nSize++;
p = p->m_tNext;
}
return nSize;
}
T First() const{if (IsEmpty()) {throw OutOfBounds();} return m_nFront->m_tData;} T Last() const{if (IsEmpty()) {throw OutOfBounds();} return m_nLast->m_tData;} LinkedQueue& Add(const T& x){if (IsFull())
{
throw NoMem();
Node *p = new Node; p->m_tData = x;
p->m_tNext = NULL;
if (m_nFront == NULL) {
m_nLast = m_nFront = p; }
else
{
m_nLast->m_tNext = p; m_nLast = p;
}
return *this;}
LinkedQueue& Delete(T& x){if (m_nFront == NULL)
{
throw NoMem();
}
else
{
x = m_nFront->m_tData; m_nFront = m_nFront->m_tNext; }
return *this;}
template friend ostream& operator<<(ostream&,const
LinkedQueue&);
private:
Node *m_nFront; Node *m_nLast;
};
#endif // LINKEDQUEUE_H #ifndef MAXHEAP_H
#define MAXHEAP_H
#include
using namespace std; #include "LinkedQueue.h" #include "swap.h"
#include "binarytree.h"
template
class MaxHeap
{
public:
MaxHeap(){root = 0;}
~MaxHeap(){delete root;}
T Max(){if (!root) throw OutOfBounds(); return root.data;}
void Meld(binarytreenode * &x, binarytreenode *y)
{if (!y) return; //yΪ?Õ
if (!x)
{//xΪ?Õ
x = y;
return;
}
if (x->data < y->data)
Swap(x, y);
Meld(x->rightchild, y);
if (!x->leftchild)
{
x->leftchild = x->rightchild;
x->rightchild = 0;
}
}
MaxHeap& Insert(T x){
//ÔÚ×î?ó?ÑÖÐ?åÈëÔªËØx?????µ?Ø?åÈëÔªËغóµÄ×î?ó?Ñ
binarytreenode *temp = new binarytreenode(x);
Meld(root, temp);
return *this;
}
MaxHeap& DeleteMax(T& x){
if (!root) throw OutOfBounds();
x = root->data;
binarytreenode *heap1 = root->leftchild;
binarytreenode *heap2 = root->rightchild;
delete root;
root = heap1;
Meld(root, heap2);
return *this;
}
void Initialize(T a[], int n)
{
LinkedQueue*> Q;
delete root;
for (int i = 0; i < n; i++)
{
binarytreenode *q = new binarytreenode(a[i]);
Q.Add(q);
}
binarytreenode *b, *c;
for (int i = 1; i <= n - 1; i++)
{Q.Delete(b).Delete(c);
Meld(b, c);
Q.Add(b);
}
if (n)
Q.Delete(root);
}
void Preorder(binarytreenode *t) {if(t){cout<data;
Preorder(t->leftchild);
Preorder(t->rightchild);}
}
void HeapSort(T a[], int n){
MaxHeap H;
H.Initialize(a, n);
T x;
for (int i = n-1; i >= 0; i--)
{
H.DeleteMax(x);
a[i] = x;
}
}
binarytreenode *root;
};
#endif // MAXHEAP_H
include
using namespace std;
#include "binarytreenode.h"
#include "LinkedQueue.h"
#include "MinHeap.h"
#include "stack.h"
template
class binarytree
{friend void visit(binarytreenode *t); public: void breaktree(T& element,binarytree&
left,binarytree& right){//(!root) throw BadInput();
element=root->data;
left.root=root->leftchild;
right.root=root->rightchild;
delete root;
root=0;}
binarytree(){root=0;count=0;}
virtual ~binarytree(){}
bool isempty() const{return ((root) ? false:true);}
bool Root(T& x) const{if(root) {x=root->data;
return true;}
else return false;}
void maketree(const T& element,binarytree& left,binarytree&
right){root=new binarytreenode(element,left.root,right.root);
l void preorder(binarytreenode *t) {if(t){visit(t);
preorder(t->leftchild);
preorder(t->rightchild);}}
void inorder(binarytreenode *t)
{if(t){
inorder(t->leftchild);
visit(t);
inorder(t->rightchild);}}
void postorder(binarytreenode *t) {if(t){
postorder(t->leftchild);
postorder(t->rightchild);
visit(t);}}
void levelorder(){LinkedQueue*> Q;
binarytreenode *t;
t=root;
while (t){
visit(t);
if(t->leftchild) Q.Add(t->leftchild);
if(t->rightchild) Q.Add(t->rightchild);
if(Q.IsEmpty()) {return;}
else Q.Delete(t);}}
int size(binarytreenode *subtree){
if(subtree==NULL) return 0;
else return
1+size(subtree->leftchild)+size(subtree->rightchild);}
int height(binarytreenode *subtree){
if(subtree==NULL) return 0;
else{int i=height(subtree->leftchild);
int j=height(subtree->rightchild);
return (i* creatbinarytree(T *vlr,T *lvr,int n)
{if(n==0) return NULL;
int k=0;
while(vlr[0]!=lvr[k]) k++;
binarytreenode *t=new binarytreenode(vlr[0]);
t->leftchild=creatbinarytree(vlr+1,lvr,k);
t->rightchild=creatbinarytree(vlr+k+1,lvr+k+1,n-k-1);
return t;
}
void AllPath(binarytreenode *t,stack & s , bool flag ) {
T y;
if (t) {
if (t->data!=0) {s.ouput();cout<<" ";}
else {{s.add(0); AllPath( t->leftchild, s,0 );}
{ s.add(1); AllPath( t->rightchild, s,1); }}
s.Delete(y);}}
binarytreenode *root;
int count;
};
#endif // BINARYTREE_H
ifndef BINARYTREENODE_H
#define BINARYTREENODE_H
template
class binarytreenode
{
public:
binarytreenode(){leftchild=rightchild=0;}
binarytreenode(const T& e){data=e;
leftchild=rightchild=0;}
binarytreenode(const T& e,binarytreenode *l,binarytreenode *r)
{data=e;
leftchild=l;
rightchild=r;}
T data;
binarytreenode *leftchild;
binarytreenode *rightchild; };
#endif // BINARYTREENODE_H
#include
using namespace std;
#include "include/MaxHeap.h" #include "include/binarytree.h" #include "include/Huffman.h" #include "include/binarytreenode.h" #include "include/BSTree.h"
template
void visit(binarytreenode *p) {
cout<data;
}
int main()
{
cout<<"×î?ó?ѵÄ??ÄÜʵÏÖ?º"< y;int count2;
cout<<"ÇëÊäÈëÒª????µÄ×î?ó?ÑÖÐÔªËØ?öÊý?º";
cin>>count2;
int *r=new int[count2];
cout<<"ÇëÊäÈë?ÑÖÐÔªËØ?º";
for(int q=0;q>r[q];
}
y.Initialize(r,count2);
cout<<"Ç?ÐòÊä?ö×î?ó?ÑÖÐÔªËØ?º";
y.Preorder(y.root);
cout<>temp;
y.Insert(temp);
cout<<"?åÈëºó?ѵÄÇ?ÐòÊä?öΪ?º";
y.Preorder(y.root);
cout< c;
int count0;cout<<"ÇëÊäÈëÒª?àÂëµÄÔªËØ?öÊý?º";
cin>>count0;
int *b=new int [count0+1];
b[1]=0;
cout<<"ÇëÊäÈëÔªËØ?º";
for(int k=1;k<=count0;k++)
{
cin>>b[k];
}
int *e=new int [count0+1];
cout<<"ÇëÊäÈë?àÂëÔªËصÄ?Ø?üÖµ(?öÏÖµÄƵÂÊ)?º";
for(int j=1;j<=count0;j++)
{
cin>>e[j];
}
binarytree d;
d=c.HuffmanTree(e,b,count0); cout<<"Æä?ÔÓ?µÄHuffmanÊ?µÄÇ?ÐòÊä?öΪ?º";
d.preorder(d.root);
cout< f(10);
cout<<"Æä?ÔÓ??àÂëΪ?º"< bstree;
cout<<"?þ?æËÑË?Ê?µÄʵÏÖÈçÏÂ?º"<> count1;
cout << "ÇëÊäÈëÒª??ÔìµÄ?þ?æËÑË?Ê?µÄÔªËØ:";
int shu;
for (int i = 0; i < count1; i++)
{
cin >> shu;
bstree.Insert(shu);
}
cout<<"????ºÃµÄ?þ?æËÑË?Ê?µÄÖÐÐò?éÀúÊÇ:";
bstree.Ascend();
cout<> count3;
cout<< "ÇëÊäÈë?ÑÅÅÐòµÄÔªËØ:";
int *dui = new int[count3];
for (int i = 0; i < count3; i++)
{
cin >> dui[i];
}
MaxHeap heap;
heap.HeapSort(dui, count3);
cout << "?øÐÐ?ÑÅÅÐòºóµÄ?º"<
/
本文档为【BS搜索树的插入,删除,搜索等基本操作】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
相关资料
- 圆融通达之道
- 美容顾问指南-玫琳凯
- PPP巨灾保险的理论评述
- 销售人员薪酬方案
- Malvern Zetasizer Nano ZS900 纳米粒径电位分析仪操作
- 课题开题报告的格式与撰写_徐万山
- 生产工艺运作流程控制程序
- 最新立体仓库详解PPT(共 60张)精品课件
- GRI全球可持续发-GlobalReportingInitiative
- 高斯小学奥数六年级上册含答案第15讲数论综合提高一
- 医德医风检查工作流程图
- 期市截拳道：程序化交易策略与实战
- 综合管廊安全管理实施方案与综合管沟(盖板涵)施工方案汇编
- 电梯负荷运行试验记录表
- 影视论文参考文献
- 夏日如风
- 电子产品维修服务合同模板下载
- 建造“水上乐园”_三年级写景作文300字
- 老年友善医疗机构创建标准
- 晚清太监琐记（In the late Qing Dynasty eunuch day）
热门搜索
- 机动车驾驶人身体条件证明
- 京广路街道办事处值班表(精)
- 2021年版乔治阿玛尼企业文化基础手册
- 计件工资的分析
- 092《异苑》[南朝宋]刘敬叔
- 福建《人民防空地下室设计规范》(GB 50038-2005)若干技术要求
- 山西农业大学开题报告(1)
- 残酷な天使のテーゼ----中文译音(手打)
- 公务员职级晋升审批表
- 《国色天香》分集剧情介绍(1-33集)
- 尺桡骨中段骨折切开复位内固定手术同意方案
- 数字化订制钢板及自体髂骨移植修复胸骨缺损的探讨
- 质量管理体系内审不符合项及其判定原则
- 反光道钉安装规范
- 机动车驾驶人身体条件证明
- 京广路街道办事处值班表(精)
- 2021年版乔治阿玛尼企业文化基础手册
- 计件工资的分析
- 092《异苑》[南朝宋]刘敬叔
- 福建《人民防空地下室设计规范》(GB 50038-2005)若干技术要求
- 山西农业大学开题报告(1)
- 残酷な天使のテーゼ----中文译音(手打)
- 公务员职级晋升审批表
- 《国色天香》分集剧情介绍(1-33集)
- 尺桡骨中段骨折切开复位内固定手术同意方案
- 数字化订制钢板及自体髂骨移植修复胸骨缺损的探讨
- 质量管理体系内审不符合项及其判定原则
- 反光道钉安装规范
你可能还喜欢
- 金融市场学(第三版)课后答案_郑振龙_张亦春
- 高考完型62篇（附详解及反思）
- Solaris10常用命令-例子
- 高程测量记录表
- 2021年“五星”党支部创建测评表
- request letter
- 221项目部伙食补贴办法
- 五年级下册英语课件-Unit9 What do you want to do｜湘鲁版 (共31张PPT)
- 《两兄弟》林语堂阅读答案
- 《SEW变频器基本操作说明》教案模板
- ISO9001文件修订计划-附件一
- 耐人寻味的歇后语
- 【株洲文心毛笔字】无笔不转 —— 读《书法有法》
- 关于给予王文博、韩佳男、苗 沛等三位同学文体活动优胜奖的决定
- 耿淡如与中国的西方史学史研究_文学理论论文
- 团建活动的通知
- 人教版五年级下册数学知识点整理
- 人教版五年级下册数学知识点整理
- 人教版五年级下册数学知识点整理
- 人教版五年级下册数学知识点整理
浙公网安备 33021202002483