📄 8_4.cpp
字号:
/*第4题 二叉树操作*/
#include<iostream.h>
#include<fstream.h>
#include<iostream.h>
#include<stdlib.h>
template<class T>
class RBtree
{
public:
enum Color{Red,Black}; //判断二叉树节点整理情况，red没整理black整理
private:
class RBnode
{
T value;
int i;
Color color;
RBnode *p; //指父树
RBnode *left; //指左子树
RBnode *right; //指右子树
RBnode():value(0),color(Red),p(NULL),left(NULL),right(NULL){};
RBnode(const T &val):value(val),color(Red),p(NULL),left(NULL),right(NULL){};
friend class RBtree<T>;
public:
void Print(int level)
{
for(int i=0;i<level;++i) // 打空格
cout<<" ";
cout<<"|"<<value; // 打印value(color)
if (color==Black)
cout<<"(B)";
else
cout<<"(R)";
return;
}
};
int i;
T s;
double a;
RBnode *ROOT; //头节点
RBnode *NIL; //末节点
int alive; // 计算数据数量
public:
RBtree():ROOT(new RBnode()),NIL(ROOT),alive(0){NIL->left=NIL->right=NIL->p=NIL;NIL->color=Black;}
RBtree(const T &val):ROOT(new RBnode(val)),NIL(new RBnode()),alive(1)
{
NIL->color=Black;
NIL->left=NIL->right=NIL->p=NIL;
ROOT->left=ROOT->right=ROOT->p=NIL;
}
~RBtree(){if(ROOT!=NIL) DeleteAll(ROOT);delete NIL;}
void Insert(const T&); //插入数据到二叉数
void Delete(const T&); // 删除数据
void DP() //由大到小排列
{
int i=0;
dp(ROOT);
}
void XP() //由小到大排列
{
int i=0;
xp(ROOT);
}
void dp(RBnode *x) //由大到小排列
{
if(x==NIL) return;
dp(x->right);
cout<<x->value<<" ";
i++;
if(!(i%10)) cout<<endl;
dp(x->left);
}
void xp(RBnode *x) //由大到小排列
{
if(x==NIL) return;
dp(x->left);
cout<<x->value<<" ";
if(!(i%10)) cout<<endl;
dp(x->right);
}
void sum(RBnode *x) //求和
{
if(x==NIL) return;
sum(x->left);
s=s+x->value;
sum(x->right);
}
void average() //求平均数
{
s=0;
sum(ROOT);
a=(double)s/alive;
cout<<a<<endl;
}
RBnode *RBFind(const T &val) // 查找数据
// 找到返回节点否则返回NIL
{
RBnode *tmp=ROOT;
while((tmp!=NIL)&&(tmp->value!=val))
tmp=val<tmp->value ? tmp->left : tmp->right;
return tmp;
}
bool Find(const T &val) // 和上面一样，但找到返回1；没有返回0
{
RBnode *tmp=RBFind(val);
return (tmp!=NIL);
}
RBnode* RBMax(RBnode* start){RBnode *tmp=start;while(tmp->right!=NIL)tmp=tmp->right;return tmp;}
//找最大数
RBnode* RBMin(RBnode* start){RBnode *tmp=start;while(tmp->left!=NIL)tmp=tmp->left;return tmp;}
// 找最小数
RBnode* RBPred(RBnode* start)//找前续
{
RBnode *tmp=start;
if (tmp->left!=NIL)
tmp=RBMax(tmp->left);
else
{
RBnode *ptmp=tmp;
tmp=tmp->p;
while((tmp!=NIL)&&(ptmp!=tmp->right))
{
ptmp=tmp;
tmp=tmp->p;
}
}
return tmp;
}
RBnode* RBSucc(RBnode* start)//找后继
{
RBnode *tmp=start;
if (tmp->right!=NIL)
tmp=RBMin(tmp->right);
else
{
RBnode *ptmp=tmp;
tmp=tmp->p;
while((tmp!=NIL)&&(ptmp!=tmp->left))
{
ptmp=tmp;
tmp=tmp->p;
}
}
return tmp;
}
void Print(); // prints a RBtree
void RotateLeft(RBnode*); // used in inset & delete functions
void RotateRight(RBnode*);
int NodeInsert(RBnode*); // puts a node in the tree
void FixDel(RBnode*); // fixing the Delete proc
T Succ(const T &val) // printing the successor of sertain value
{
RBnode *tmp=RBFind(val);
if (tmp==NIL)
{
cout<<"value not found";
return 0;
}
else
tmp=RBSucc(tmp);
return tmp->value;
}
T Pred(const T &val) // the same for predecessor
{
RBnode *tmp=RBFind(val);
if (tmp==NIL)
{
cout<<"value not found";
return 0;
}
else
tmp=RBPred(tmp);
return tmp->value;
}
T Max(const T &val){RBnode *tmp=RBMax(ROOT);return tmp->value;} //prints max
T Min(const T &val){RBnode *tmp=RBMin(ROOT);return tmp->value;} //prints min
void RBPrint(RBnode*,int); // req func for printing RBtree
void DeleteAll(RBnode*); // deletes all of the RBtree (except the NIL);
};
template<class T>
void RBtree<T>::Insert(const T &val){
RBnode* x=new RBnode(val),*y;
if(NodeInsert(x)==1)
{
cout<<val<<" alread exist in tree"<<endl;
return;
}
while ((x!=ROOT)&&(x->p->color==Red))
{
if (x->p==x->p->p->left) // if x parent is left son
{
y=x->p->p->right; // checking x uncle
if (y->color==Red) // if red case 1
{
x->p->color=Black;
y->color=Black;
x->p->p->color=Red;
x=x->p->p;
}
else
{
if (x==x->p->right) //if x right the case 2
{
x=x->p;
RotateLeft(x);
}
x->p->color=Black; // case 3
x->p->p->color=Red;
RotateRight(x->p->p);
}
}
else
{
y=x->p->p->left; // checking x uncle
if (y->color==Red) // if red case 4
{
x->p->color=Black;
y->color=Black;
x->p->p->color=Red;
x=x->p->p;
}
else
{
if (x==x->p->left) //if x right the case 5
{
x=x->p;
RotateRight(x);
}
x->p->color=Black; // case 6
x->p->p->color=Red;
RotateLeft(x->p->p);
}
}
}
ROOT->color=Black;
return;
}
template<class T>
void RBtree<T>::Delete(const T &val)
{
RBnode *z,*y,*x;
z=RBFind(val);
if(z==NIL)
{
cout<<val<<" not found"<<endl;
return;
}
--alive;
if ((z->left == NIL)||(z->right==NIL)) // delteing from leaves
y=z;
else
y=RBSucc(z);
if (y->left!=NIL)
x=y->left;
else
x=y->right;
x->p=y->p;
if (y->p==NIL)
{
ROOT=x;
x->p=NIL;
}
else
{
if (y==y->p->left)
y->p->left=x;
else
y->p->right=x;
}
if (y!=z) // if we changed the successor with z
z->value=y->value;
if (y->color==Black)
FixDel(x); // if we delted a Black node we have to rearrange the tree
delete y;
if (x==NIL)
x->p=NIL;
return;
}
template<class T>
void RBtree<T>::RotateLeft(RBnode* x)
{
RBnode* y=x->right;
x->right=y->left;
if (y->left!=NIL)
y->left->p=x;
y->p=x->p;
if (x->p==NIL)
ROOT=y;
else if (x==x->p->left)
x->p->left=y;
else
x->p->right=y;
y->left=x;
x->p=y;
return;
}
template<class T>
void RBtree<T>::RotateRight(RBnode* x)
{
RBnode* y=x->left;
x->left=y->right;
if (y->right!=NIL)
y->right->p=x;
y->p=x->p;
if (x->p==NIL)
ROOT=y;
else if (x==x->p->right)
x->p->right=y;
else
x->p->left=y;
y->right=x;
x->p=y;
return;
}
template<class T>
int RBtree<T>::NodeInsert(RBnode *x)
{
RBnode *tmp1=ROOT,*tmp2=tmp1;
if (ROOT==NIL)
{ // in case that x is the 1st node
ROOT=x;
x->left=x->right=x->p=NIL;
++alive;
return 0;
}
while((tmp1!=NIL)&&(tmp1->value!=x->value))
{
tmp2=tmp1;
tmp1=x->value>tmp1->value ? tmp1->right : tmp1->left;
}
if (tmp1==NIL){ // if the item not in tree - add
if (x->value>tmp2->value)
tmp2->right=x;
else
tmp2->left=x;
x->p=tmp2;
x->left=x->right=NIL;
++alive;
return 0;
}
return 1;
}
template<class T>
void RBtree<T>::FixDel(RBnode *x)
{
RBnode *w;
while ((x!=ROOT)&&(x->color==Black))
{
if (x==x->p->left){ // if x is the right son
w=x->p->right;
if (w->color==Red){ // case 1
w->color=Black;
x->p->color=Red;
RotateLeft(x->p);
w=x->p->right;
}
if ((w->left->color==Black)&&(w->right->color==Black))
{
w->color=Red; // case 2
x=x->p;
}else{
if (w->right->color==Black)
{
w->left->color=Black; // case 3
w->color=Red;
RotateRight(w);
w=x->p->right;
}
w->color=x->p->color; // case 4
x->p->color=Black;
w->right->color=Black;
RotateLeft(x->p);
x=ROOT;
}
}
else
{ // if x is the left son
w=x->p->left;
if (w->color==Red) // case 5
{
w->color=Black;
x->p->color=Red;
RotateRight(x->p);
w=x->p->left;
}
if ((w->right->color==Black)&&(w->left->color==Black))
{
w->color=Red; // case 6
x=x->p;
}
else
{
if (w->left->color==Black) // case 7
{
w->right->color=Black;
w->color=Red;
RotateLeft(w);
w=x->p->left;
}
w->color=x->p->color; // case 8
x->p->color=Black;
w->left->color=Black;
RotateRight(x->p);
x=ROOT;
}
}
}
x->color=Black;
return;
}
template<class T>
void RBtree<T>::Print()
{
int depth=-1;
RBnode *x=ROOT;
RBPrint(x,depth);
return;
}
// the printing will be done so that the root will be on the left
// and the tree will expend to the right
template<class T>
void RBtree<T>::RBPrint(RBnode *x,int level)
{
if (x==NIL) return;
++level;
RBPrint(x->right,level);
x->Print(level);
cout<<"---|"<<endl;
RBPrint(x->left,level);
return;
}
template<class T>
void RBtree<T>::DeleteAll(RBnode *x)
{
if(x==NIL) return;
DeleteAll(x->left);
DeleteAll(x->right);
delete x;
};
//Rbtree.h end
void meun()
{
cout<<" 菜单"<<endl;
cout<<"********************************"<<endl;
cout<<" 0 结束"<<endl;
cout<<" 1 插入数据"<<endl;
cout<<" 2 删除数据"<<endl;
cout<<" 3 查找数据"<<endl;
cout<<" 4 找后继数据"<<endl;
cout<<" 5 找前续数据"<<endl;
cout<<" 6 找最小值"<<endl;
cout<<" 7 找最大值"<<endl;
cout<<" 8 输出二叉数"<<endl;
cout<<" 9 输出平均值"<<endl;
cout<<" 10 从大到小输出二叉数"<<endl;
cout<<" 11 从小到大输出二叉数"<<endl;
}
void hy()
{
cout<<"欢迎使用二叉数程序"<<endl;
cout<<"***************************"<<endl;
cout<<"0 退出"<<endl;
cout<<"1 重新输入数据"<<endl;
cout<<"2 使用存档数据"<<endl;
}
void main(void)
{
int l;
int choice,num;
RBtree<int> tr;
hy();
cin>>l;
cout<<endl;
switch(l)
{
case(0):return;
case(1):
cout<<"请输入数据，以-1结束"<<endl;
cin>>num;
while(num!=-1)
{
tr.Insert(num);
cin>>num;
}
break;
case(2):
{
ifstream data("data4.txt", ios::in|ios::nocreate);
if(data.bad())
{
cout<<endl<<"file not found"<<endl;
}
data>>choice;
while(!data.eof())
{
data>>num;
tr.Insert(num);
}
data.close();
break;
}
default:cout<<endl<<"the choice number is out of range"<<endl;
return;
}
tr.Print();
meun();
cin>>choice;
cout<<endl;
while(choice!=0)
{
switch(choice)
{
case(1):
cout<<"输入要插入的数"<<endl;
cin>>num;
cout<<endl;
cout<<"插入 "<<num<<endl;
tr.Insert(num);
tr.Print();
break;
case(2):
cout<<"输入要删除的数"<<endl;
cin>>num;
cout<<"删除 - "<<num<<endl;
tr.Delete(num);
break;
case(3):cout<<"输入要查找的数"<<endl;
cin>>num;
cout<<"查找 "<<num<<endl;
if(tr.Find(num))
cout<<num<<" 存在"<<endl;
else
cout<<num<<" 不存在"<<endl;
break;
case(4):
cout<<"输入要查找后继数的数"<<endl;
cin>>num;
cout<<num<<" 的后继数是"<<endl;
cout<<tr.Succ(num);
cout<<endl;
break;
case(5):
cout<<"输入要查找前续数据的数"<<endl;
cin>>num;
cout<<num<<"的前续数据是"<<endl;
cout<<tr.Pred(num);
cout<<endl;
break;
case(6):cout<<"最小值是: ";
cout<<tr.Min(num);
cout<<endl;
break;
case(7):cout<<"最大值是: ";
cout<<tr.Max(num);
cout<<endl;
break;
case(8):cout<<"打印二叉数"<<endl;
tr.Print();
cout<<endl;
break;
case(9):cout<<"平均数是"<<endl;
tr.average();
cout<<endl;
break;
case(10):cout<<"从大到小是"<<endl;
tr.DP();
cout<<endl;
break;
case(11):cout<<"从小到大是"<<endl;
tr.XP();
cout<<endl;
break;
default:cout<<endl<<"the choice number is out of range"<<endl;
break;
}
meun();
cin>>choice;
}
cout<<"二叉数是"<<endl;
tr.Print();
cout<<"谢谢使用"<<endl;
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -