vlambda博客
学习文章列表

#include <iostream>#include <cstdio>#include <malloc.h>#include <stack>#include <queue>#include <math.h>#include <string>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2using namespace std;typedef string ElemType;//string为字符串排序（支持中文），int为数值排序typedef struct BSTNode{ ElemType data; int height;//结点的高度 struct BSTNode *lchild,*rchild;//左右孩子指针} BSTNode,*BSTree;
int NodeHeight(BSTree T){ if(T==NULL) return -1; else return T->height;}
int max(int a,int b){ return a>b?a:b;}
void UpdateHeight(BSTree T){ if(T==NULL) return; T->height=max(NodeHeight(T->lchild),NodeHeight(T->rchild))+1;}/*平衡二叉树模块*/BSTree LRotateBBST(BSTree T)//向右旋转{ BSTree L=T->lchild; T->lchild=L->rchild; L->rchild=T; T->height=max(NodeHeight(T->lchild),NodeHeight(T->rchild))+1; L->height=max(NodeHeight(L->lchild),T->height)+1; return L;}
BSTree RRotateBBST(BSTree T)//向左旋转{ BSTree R=T->rchild; T->rchild=R->lchild; R->lchild=T; T->height=max(NodeHeight(T->lchild),NodeHeight(T->rchild))+1; R->height=max(NodeHeight(R->rchild),T->height)+1; return R;}
BSTree LRRotateBBST(BSTree T)//LR型调整{ T->lchild=RRotateBBST(T->lchild); return LRotateBBST(T);}
BSTree RLRotateBBST(BSTree T)//RL型调整{ T->rchild=LRotateBBST(T->rchild); return RRotateBBST(T);}/*插入模块*/BSTree InsertBST(BSTree &T,ElemType e)//&表引用{ bool res=true; if(!T)//树中没有结点 { BSTree S; S=new BSTNode; S->data=e; S->height=0; S->lchild=S->rchild=NULL; T=S; } else if(e<=T->data)//此处默认相等时插在左边 { res=InsertBST(T->lchild,e); if(res&&NodeHeight(T->lchild)-NodeHeight(T->rchild)==2)//平衡因子大于1 if(e<=T->lchild->data) T=LRotateBBST(T);//LL else T=LRRotateBBST(T);//LR } else if(e>T->data) { res=InsertBST(T->rchild,e); if(res&&NodeHeight(T->rchild)-NodeHeight(T->lchild)==2)//平衡因子小于-1 if(e>T->rchild->data) T=RRotateBBST(T);//RR else T=RLRotateBBST(T);//RL } if(res) UpdateHeight(T); return T;}
void CreateBST(BSTree &T,int n){ T=NULL; ElemType e; for(int i=0;i<n;i++) { cin>>e; InsertBST(T,e); }}/*遍历模块*/void PreOrderTraverse(BSTree T){ if(T) { cout<<T->data<<' '; PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); }}
void InOrderTraverse(BSTree T){ if(T) { InOrderTraverse(T->lchild); cout<<T->data<<' '; InOrderTraverse(T->rchild); }}
void PostOrderTraverse(BSTree T){ if(T) { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); cout<<T->data<<' '; }}
void PreOrderIteration(BSTree T){ stack<BSTree>S; BSTree p=T; while(p||!S.empty()) { if(p) { cout<<p->data<<' '; S.push(p); p=p->lchild; } else { p=S.top(); S.pop(); p=p->rchild; } }}
void InOrderIteration(BSTree T){ stack<BSTree>S; BSTree p=T; while(p||!S.empty()) { if(p) { S.push(p); p=p->lchild; } else { p=S.top(); cout<<p->data<<' '; S.pop(); p=p->rchild; } }}
void PostOrderIteration(BSTree T){ stack<BSTree>S; BSTree p=T; BSTree q=NULL; while(p||!S.empty()) { if(p) { S.push(p); p=p->lchild; } else { p=S.top(); if(p->rchild&&p->rchild!=q) { p=p->rchild; } else { S.pop(); cout<<p->data<<' '; q=p; p=NULL; } } }}
void LevelOrderTraverse(BSTree T)//层序遍历{ queue<BSTree>Q; if(T) Q.push(T); while(!Q.empty()) { cout<<Q.front()->data<<' ';//输出队头元素 if(Q.front()->lchild) Q.push(Q.front()->lchild); if(Q.front()->rchild) Q.push(Q.front()->rchild);//有左孩子进左孩子有右孩子进右孩子 Q.pop(); }}
void TraversebyZhi(BSTree T)//之字形遍历{ //queue<BSTree>Q; stack<BSTree>s[2]; int cur=0,next=1; if(T) s[cur].push(T); while(!s[0].empty()||!s[1].empty()) { BSTree t=s[cur].top(); s[cur].pop(); //printf("%s ",t->data);//输出栈顶元素，d cout<<t->data<<' '; if(cur==0) { if(t->lchild) s[next].push(t->lchild); if(t->rchild) s[next].push(t->rchild); } else { if(t->rchild) s[next].push(t->rchild); if(t->lchild) s[next].push(t->lchild); } if(s[cur].empty()) { //cout<<endl; cur=1-cur; next=1-next;//每次清空栈后0号栈、1号栈倒换 } }}/*搜索模块*/BSTree SearchBST(BSTree T,ElemType e)//返回值为BSTree类型{ if(!T||e==T->data) return T; else if(e<T->data) return SearchBST(T->lchild,e); else if(e>T->data) return SearchBST(T->rchild,e);}
int SearchLengthBST(BSTree T,ElemType e){ if(!T) return 0; else if(e==T->data) return 1; else if(e<T->data) return SearchLengthBST(T->lchild,e)+1; else return SearchLengthBST(T->rchild,e)+1;}
void DeleteBST1(BSTree &T,BSTree p){ if(T->rchild==NULL)//用左子树的最右边顶上， { BSTree q=T; p->data=T->data; T=T->lchild; delete q; } else { DeleteBST1(T->rchild,p); if(NodeHeight(T->lchild)-NodeHeight(T->rchild)==2) T=LRotateBBST(T); } UpdateHeight(T);}/*删除模块*/BSTree DeleteBST(BSTree &T,ElemType e)//相同时删除离根最远的元素，此为递归方法{ if(!T) return NULL; bool res=true;//res作为保险 if(e==T->data) { if(T->lchild==NULL) T=T->rchild; else if(T->rchild==NULL) T=T->lchild; else DeleteBST1(T->lchild,T); } else if(e<T->data) { res=DeleteBST(T->lchild,e);//每次删除出现不平衡自动调整 if(res&&NodeHeight(T->lchild)-NodeHeight(T->rchild)==2) { if(e<T->lchild->data)//在左子树的左边删除造成不平衡 T=LRotateBBST(T); else T=LRRotateBBST(T); } else if(res&&NodeHeight(T->rchild)-NodeHeight(T->lchild)==2) { if(e>T->rchild->data)//在右子树的右边删除造成不平衡 T=RRotateBBST(T); else T=RLRotateBBST(T); } } else { res=DeleteBST(T->rchild,e); if(res&&NodeHeight(T->lchild)-NodeHeight(T->rchild)==2) { if(e<T->lchild->data) T=LRotateBBST(T); else T=LRRotateBBST(T); } else if(res&&NodeHeight(T->rchild)-NodeHeight(T->lchild)==2) { if(e>T->rchild->data) T=RRotateBBST(T); else T=RLRotateBBST(T); } } if(res) UpdateHeight(T); return T;}/*交换子树模块*/BSTree SwapLeaf(BSTree &T){ if(T) { if(T->lchild||T->rchild) { BSTree p1,p2; p1=SwapLeaf(T->lchild);//递归交换各结点左子树右子树，每个左子树右子树均被取反 p2=SwapLeaf(T->rchild); T->lchild=p2; T->rchild=p1; } } return T;}/*统计模块*/int LevelLeafNodes(BSTree T,int k)//统计每一层的叶子结点数量{ if(T==NULL) return 0; //queue<BiTree>QW; BSTree q[1005]; int front=0; int rear=0; q[rear++]=T; //QW.push(T); int curlevelnodes=0; int curlevel=0;//初始化第0层 BSTree c=new BSTNode; c=NULL; //while(!QW.empty()) while(rear>front) { ++curlevel; //curlevelnodes=QW.size()//该层的总结点数 curlevelnodes=(rear-front)%1000000007; if(k==curlevel) break;//层数相同结束 int curnode=0; while(curnode<curlevelnodes) { ++curnode; //c=QW.front(); c=q[front]; //QW.pop(); front++; if(c->lchild!=NULL) //QW.push(c->lchild); q[rear++]=c->lchild; if(c->rchild!=NULL) //QW.push(c->rchild); q[rear++]=c->rchild; } } //while(!QW.empty()) /*while(rear>front) { //QW.pop(); front++;//至此返回所有结点 }*/ if(curlevel==k) { int curleaf=0; int leafnodes=0; while(curleaf<curlevelnodes) { ++curleaf; c=q[front]; front++; if(c->lchild==NULL&&c->rchild==NULL) { leafnodes++; } } return leafnodes;//至此返回叶子结点 } else return 0;}
int LevelAllNodes(BSTree T,int k)//统计每一层的结点总数{ if(T==NULL) return 0; queue<BSTree>QW; //BSTree q[1005]; //int front=0; //int rear=0; //q[rear++]=T; QW.push(T); int curlevelnodes=0; int curlevel=0;//初始化第0层 BSTree c=new BSTNode; c=NULL; while(!QW.empty()) //while(rear>front) { ++curlevel; curlevelnodes=QW.size();//该层的总结点数 //curlevelnodes=(rear-front)%1005; if(k==curlevel) break;//层数相同结束 int curnode=0; while(curnode<curlevelnodes) { ++curnode; c=QW.front(); //c=q[front]; QW.pop(); //front++; if(c->lchild!=NULL) QW.push(c->lchild); //q[rear++]=c->lchild; if(c->rchild!=NULL) QW.push(c->rchild); //q[rear++]=c->rchild; } } while(!QW.empty()) //while(rear>front) { QW.pop(); //front++;//至此返回所有结点 } return curlevelnodes;}
int DepthBST(BSTree T)//统计树的深度{ if(!T) return 0; else { int m=DepthBST(T->lchild); int n=DepthBST(T->rchild); return (m>n)?(m+1):(n+1); }}
int LeafofBST(BSTree T)//统计叶子总数量{ if(!T) return 0; else { if(T->lchild||T->rchild)//左右孩子下的叶子结点之和 return LeafofBST(T->lchild)+LeafofBST(T->rchild); if(T->lchild==NULL&&T->rchild==NULL) return 1; }}
int Degree2Nodes(BSTree T)//统计度为2结点总数{ if(!T) return 0; else { if(T->lchild&&T->rchild) return Degree2Nodes(T->lchild)+Degree2Nodes(T->rchild)+1; }}
int Degree1Nodes(BSTree T)//统计度为1结点总数{ if(!T) return 0; else { if((T->lchild&&T->rchild==NULL)||(T->lchild==NULL&&T->rchild)) return Degree1Nodes(T->lchild)+Degree1Nodes(T->rchild)+1; } return Degree1Nodes(T->lchild)+Degree1Nodes(T->rchild);}
int WidthofBST(BSTree T)//二叉树的最大宽度{ if(T==NULL) return 0; queue<BSTree>QW; QW.push(T); int width=1; int curlevelwidth=1; BSTree c=new BSTNode; c=NULL; while(!QW.empty()) { while(curlevelwidth!=0) { c=QW.front(); QW.pop(); if(c->lchild!=NULL) QW.push(c->lchild); if(c->rchild!=NULL) QW.push(c->rchild); curlevelwidth--; } curlevelwidth=QW.size(); width=curlevelwidth>width?curlevelwidth:width; } return width;}
double AverageSearchLength(BSTree T,int n)//平均搜索长度{ if(!T) return 0; double asl=0; int i; for(i=1;i<=DepthBST(T);i++) { asl+=i*LevelAllNodes(T,i); } return asl/n;}
int main()//此模块可自行更改{ int n,s4,n2,/*s1,s2,s3,s4,s5,s6,*/op,op2,op3,op4; ElemType s1,s2,s3,s5,s6,s7; bool isswap; system("color 0f"); printf("*****************************************二叉排序树的各种操作***************************************************\n"); printf("*********************************************by lzc316227*******************************************************\n"); printf("**********************************************Ver 1.3.3*********************************************************\n"); printf("初始结点个数：\n"); cin>>n; BSTree T; printf("请输入初始结点：\n"); CreateBST(T,n); while(1) { printf("请选择功能：\n"); printf("1.二叉排序树的遍历\n"); printf("2.二叉排序树的插入\n"); printf("3.二叉排序树的查找\n"); printf("4.二叉排序树的删除\n"); printf("5.二叉排序树的值修改\n"); printf("6.交换二叉排序树的左右子树\n"); printf("7.求二叉排序树的深度\n"); printf("8.求二叉排序树的最大宽度\n"); printf("9.求二叉排序树的特定性质结点\n"); printf("0.退出\n"); cin>>op; switch(op) { case 1: system("color f0"); printf("请选择遍历方式：\n"); printf("1.先序递归\n"); printf("2.先序非递归\n"); printf("3.中序递归\n"); printf("4.中序非递归\n"); printf("5.后序递归\n"); printf("6.后序非递归\n"); printf("7.层序遍历\n"); printf("8.之字形遍历\n"); cin>>op2; switch(op2) { case 1: PreOrderTraverse(T); cout<<endl; break; case 2: PreOrderIteration(T); cout<<endl; break; case 3: InOrderTraverse(T); cout<<endl; break; case 4: InOrderIteration(T); cout<<endl; break; case 5: PostOrderTraverse(T); cout<<endl; break; case 6: PostOrderIteration(T); cout<<endl; break; case 7: LevelOrderTraverse(T); cout<<endl; break; case 8: TraversebyZhi(T); cout<<endl; break; default: printf("功能暂未开放\n"); break; } break; case 2: system("color e0"); if(isswap==true) { printf("子树被交换下此功能被锁定\n"); break; } printf("1.插入单个元素\n"); printf("2.批量插入元素\n"); cin>>op4; switch(op4) { case 1: cin>>s1; T=InsertBST(T,s1); n++; cout<<"插入结点"<<s1<<"成功"<<endl; break; case 2: cin>>n2; for(int i=1;i<=n2;i++) { cin>>s7; InsertBST(T,s7); } n+=n2; cout<<"插入"<<n2<<"个结点成功"<<endl; break; default: printf("功能暂未开放\n"); break; } break; case 3: system("color e1"); cin>>s2; if(SearchBST(T,s2)) cout<<"查找成功，查找长度为"<<SearchLengthBST(T,s2)<<endl; else cout<<"查找失败"<<endl; break; case 4: system("color d7"); if(isswap==true) { printf("子树被交换下此功能被锁定\n"); break; } cin>>s3; if(!SearchBST(T,s3)) cout<<"删除结点"<<s3<<"失败"<<endl; else { T=DeleteBST(T,s3); n--; cout<<"删除结点"<<s3<<"成功"<<endl; } break; case 5: system("color fc"); if(isswap==true) { printf("子树被交换下此功能被锁定\n"); break; } printf("请输入需要修改的值：\n"); cin>>s5; if(!SearchBST(T,s5)) cout<<"修改结点失败"<<endl; else { T=DeleteBST(T,s5); printf("请输入修改后的值：\n"); cin>>s6; T=InsertBST(T,s6); cout<<"修改结点成功"<<endl; } break; case 6: system("color b5"); SwapLeaf(T); isswap=(isswap==false?true:false); cout<<"交换左右子树成功"<<endl; break;//未来红黑树可能把此模块修改为换色，1.3.3仍为交换左右子树 case 7: system("color a5"); cout<<DepthBST(T)<<endl; break; case 8: system("color a4"); cout<<WidthofBST(T)<<endl; break; case 9: system("color 9f"); printf("请选择统计结点方式：\n"); printf("1.所有叶子的数量\n"); printf("2.指定层次的叶子数量\n"); printf("3.统计度为2的结点数量\n"); printf("4.统计度为1的结点数量\n"); printf("5.统计所有层的结点数量\n"); printf("6.计算平均搜索长度\n"); cin>>op3; switch(op3) { case 1: cout<<LeafofBST(T)<<endl; break; case 2: cin>>s4; cout<<LevelLeafNodes(T,s4)<<endl; break; case 3: cout<<Degree2Nodes(T)<<endl; break; case 4: cout<<Degree1Nodes(T)<<endl; break; case 5: for(int i=1;i<=DepthBST(T);i++) cout<<LevelAllNodes(T,i)<<' '; cout<<endl; break; case 6: printf("%.6f\n",AverageSearchLength(T,n)); break; default: printf("功能暂未开放\n"); break; } break; case 0: exit(0); break; default: printf("功能暂未开放\n"); break; } } return 0;}