本文主要是介绍数据结构实验：SDUT2482二叉排序树+3374平衡二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
SDUT3374
平衡二叉树的思路和代码参考清华版《数据结构》，但是对于其中的LR型以及RL型的调整不太明白。虽然书上没有给出右平衡调整的代码但是可以根据左平衡的对称性写出来。
#include<cstdio>
#include<cstring>
#define LH +1
#define RH -1
#define EH 0
using namespace std;
const int maxn=25;
int n,a;
bool taller;
typedef struct BSTNode{int data,bf;struct BSTNode *lch,*rch;
}BSTNode,*BSTree;void R(BSTree &T){BSTree lc=T->lch;T->lch=lc->rch;lc->rch=T;T=lc;
}void L(BSTree &T){BSTree rc=T->rch;T->rch=rc->lch;rc->lch=T;T=rc;
}void LB(BSTree &T){BSTree lc=T->lch;switch(lc->bf){case LH:T->bf=lc->bf=EH;R(T);break;case RH:BSTree rd=lc->rch;switch(rd->bf){case LH:T->bf=RH;lc->bf=EH;break;case EH:T->bf=lc->bf=EH;break;case RH:T->bf=EH;lc->bf=LH;break;}rd->bf=EH;L(T->lch);R(T);}
}void RB(BSTree &T){BSTree rc=T->rch;switch(rc->bf){case RH:T->bf=rc->bf=EH;L(T);break;case LH:BSTree ld=rc->lch;switch(ld->bf){case LH:T->bf=LH;rc->bf=EH;break;case EH:T->bf=rc->bf=EH;break;case RH:T->bf=EH;rc->bf=RH;break;}ld->bf=EH;R(T->rch);L(T);}
}int Insert(BSTree &T,int e,bool &taller){if(!T){T=new BSTNode;T->data=e;T->lch=NULL;T->rch=NULL;T->bf=EH;taller=true;}else{if(T->data==e){taller=false;return 0;}if(e<T->data){if(!Insert(T->lch,e,taller))return 0;if(taller){switch(T->bf){case LH:LB(T);taller=false;break;case EH:T->bf=LH;taller=true;break;case RH:T->bf=EH;taller=false;break;}}}else{if(!Insert(T->rch,e,taller))return 0;if(taller){switch(T->bf){case LH:T->bf=EH;taller=false;break;case EH:T->bf=RH;taller=true;break;case RH:RB(T);taller=false;break;}}}}return 1;
}int main(){while(scanf("%d",&n)!=EOF){BSTree bt=new BSTNode;bt=NULL;taller=false;for(int i=0;i<n;i++){scanf("%d",&a);Insert(bt,a,taller);}printf("%d\n",bt->data);}return 0;
}/***************************************************
User name: Rocky
Result: Accepted
Take time: 0ms
Take Memory: 160KB
Submit time: 2017-11-25 23:58:12
****************************************************/
SDTU2482
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int maxn=50;
int n;
char a[maxn],b[maxn],a1[maxn],b1[maxn];typedef struct BSTNode{int data;struct BSTNode *lch,*rch;
}BSTNode,*BSTree;int Binsert(BSTree &T,int data){if(!T){BSTree b=new BSTNode;b->data=data;b->lch=NULL;b->rch=NULL;T=b;}else if(data<T->data){Binsert(T->lch,data);}else if(data>T->data){Binsert(T->rch,data);}
}int first(BSTree T,char *a,int i){if(T){first(T->lch,a,i+1);a[i]=T->data;first(T->rch,a,strlen(a)-1);}
}void help(char *s,char *s2){BSTree bt=new BSTNode;bt=NULL;int length=strlen(s);for(int i=0;i<length;i++){Binsert(bt,s[i]);}first(bt,s2,0);
}bool judge(char *a,char *b,int length,int i){while(i<length){if(a[i]==b[i])i++;elsereturn false;}return true;
}int main(){while(scanf("%d",&n)!=EOF){if(n==0)break;scanf("%s",a);int length=strlen(a);help(a,a1);for(int i=0;i<n;i++){scanf("%s",b);help(b,b1);/*for(int i=0;i<length;i++)printf("%c",b1[i]);*/if(judge(a1,b1,length,0))printf("YES\n");elseprintf("NO\n");}}return 0;
}/***************************************************
User name: Rocky
Result: Accepted
Take time: 0ms
Take Memory: 164KB
Submit time: 2017-11-25 20:23:20
****************************************************/
这篇关于数据结构实验：SDUT2482二叉排序树+3374平衡二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
