数据结构 树的变成习题.doc

实验题目(共6题, 第1题)标题：Huffman树时限：1000ms内存限制：10000K总时限：3000ms描述：Huffman树对输入的英文大写字母进行统计概率 然后构建哈夫曼树,输出是按照概率降序排序输出Huffman编码。输入：大写字母个数 n第一个字母 第二个字母 第三个字母 . 第n个字母输出：字母1 出现次数 Huffman编码字母2 出现次数 Huffman编码字母3 出现次数 Huffman编码字母n 出现次数 Huffman编码输入样例：10I I U U U I U N U U输出样例：U 6 1I 3 01N 1 00提示：参见教材144页来源：#include#include#include#defineMAX27#defineMAX_INT99999typedefstructintweight;intparent,lchild,rchild;HTNode,*HuffmanTree;typedefchar*HuffmanCode;typedefstructCharnodecharc;intweight;CharNode,*CharNodePtr;CharNode*b;intChat_get()charc;intj=0;intm;inti;scanf(%d,&m);getchar();b=(CharNodePtr)malloc(sizeof(CharNode)*MAX);intaMAX;for(i=0;iMAX;i+)ai=0;for(i=0;im;i+)scanf(%c,&c);getchar();ac-A+;for(i=0;i26;i+)if(ai!=0)bj.c=char(i+A);bj.weight=ai;j+;returnj;intmin(HuffmanTreet,inti)intj,flag;intk=MAX_INT;for(j=1;j=i;j+)if(tj.weightk&tj.parent=0)k=tj.weight,flag=j;tflag.parent=1;returnflag;voidselect(HuffmanTreet,inti,int&s1,int&s2)s2=min(t,i);s1=min(t,i);voidPrintHuffmanTree(HuffmanTree&HT,HuffmanCode&HC,intn)inti,c,cdlen;char*cd;HC=(HuffmanCode)malloc(n+1)*sizeof(char*);cd=(char*)malloc(n*sizeof(char);c=2*n-1;cdlen=0;for(i=0;i=c;+i)HTi.weight=0;while(c)if(HTc.weight=0)HTc.weight=1;if(HTc.lchild=0&HTc.rchild=0)HCc=(char*)malloc(cdlen+1)*sizeof(char);cdcdlen=0;strcpy(HCc,cd);if(HTc.lchild!=0)c=HTc.lchild;cdcdlen+=1;elseif(HTc.weight=1)HTc.weight=2;if(HTc.rchild!=0)c=HTc.rchild;cdcdlen+=0;elseHTc.weight=0;c=HTc.parent;-cdlen;free(cd);voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)intm,i,s1,s2;HuffmanTreep;if(n=1)exit(0);m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(p=HT+1,i=1;i=n;+i,+p,+w)(*p).weight=*w;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;for(;i=m;+i,+p)(*p).parent=0;for(i=n+1;i=m;+i)select(HT,i-1,s1,s2);HTs1.parent=HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;PrintHuffmanTree(HT,HC,n);voidsort_b(intk)intn;charc;inti,j;for(i=0;i=i;j-)if(bj.weightbj-1.weight)n=bj.weight;bj.weight=bj-1.weight;bj-1.weight=n;c=bj.c;bj.c=bj-1.c;bj-1.c=c;intmain()intk;intj;inti;HuffmanTreeHT;HuffmanCodeHC;k=Chat_get();int*w;w=(int*)malloc(sizeof(int)*k);sort_b(k);for(i=0;ik;i+)wi=bi.weight;HuffmanCoding(HT,HC,w,k);for(i=0,j=1;ik;j+,i+)printf(%c%d%sn,bi.c,bi.weight,HCj);return0; 实验题目(共6题, 第2题)标题：从先序中序重建二叉树输出层序后序时限：5000ms内存限制：20000K总时限：3000ms描述：由树的先序和中序遍历生成树的层序遍历后序遍历给定一个树的先序和中序的遍历结果，构建一棵树，并输出这个棵树的层序遍历和后序遍历结果注：这棵树的结点是由整数描述输入：树结点总数m先序输出序列中序输出序列输出：层序输出序列后续输出序列输入样例：101 2 5 10 3 6 13 7 14 152 10 5 1 6 13 3 14 7 15输出样例：1 2 3 5 6 7 10 13 14 1510 5 2 13 6 14 15 7 3 1提示：先序遍历的第一个输出是根结点来源：#include#include#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10int*pre;int*in;typedefstructBiTNodeintdata;structBiTNode*lchild;structBiTNode*rchild;BiTNode,*BiTree;structSqStackBiTree*base;BiTree*top;intstacksize;typedefstructQNodeBiTreedata;QNode*next;*QueuePtr;structLinkQueueQueuePtrfront,rear;voidLevelOrderTraverse(BiTreeT);voidPostOrderTraverseNonRecursive(BiTreeT);voidInitStack(SqStack&S);voidPop(SqStack&S,BiTree&e);voidPush(SqStack&S,BiTreee);intGetTop(SqStackS,BiTree&e);intStackEmpty(SqStackS);voidDeQueue(LinkQueue&Q,BiTree&e);voidEnQueue(LinkQueue&Q,BiTreee);intQueueEmpty(LinkQueueQ);voidInitQueue(LinkQueue&Q);BiTreerestore(int*pre,int*in,intn);intmain()BiTreeT;intn,i;scanf(%d,&n);pre=(int*)malloc(n*sizeof(int);in=(int*)malloc(n*sizeof(int);for(i=0;in;i+)scanf(%d,pre+i);for(i=0;idata=*pre;for(rpos=in;rposlchild=restore(pre+1,in,k);p-rchild=restore(pre+1+k,rpos+1,n-1-k);returnp;voidLevelOrderTraverse(BiTreeT)LinkQueueq;BiTreea;if(T)InitQueue(q);EnQueue(q,T);while(!QueueEmpty(q)DeQueue(q,a);printf(%d,a-data);if(a-lchild!=NULL)EnQueue(q,a-lchild);if(a-rchild!=NULL)EnQueue(q,a-rchild);voidPostOrderTraverseNonRecursive(BiTreeT)BiTreep;if(T=NULL)return;SqStackS1,S2;InitStack(S1);InitStack(S2);Push(S1,T);while(!StackEmpty(S1)Pop(S1,p);Push(S2,p);if(p-lchild!=NULL)Push(S1,p-lchild);if(p-rchild!=NULL)Push(S1,p-rchild);while(!StackEmpty(S2)Pop(S2,p);printf(%d,p-data);voidInitStack(SqStack&S)if(!(S.base=(BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTree)exit(0);S.top=S.base;S.stacksize=STACK_INIT_SIZE;intStackEmpty(SqStackS)if(S.top=S.base)return1;elsereturn0;intGetTop(SqStackS,BiTree&e)if(S.topS.base)e=*(S.top-1);return1;elsereturn0;voidPush(SqStack&S,BiTreee)if(S.top-S.base=S.stacksize)S.base=(BiTree*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTree);if(!S.base)exit(0);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*(S.top)+=e;voidPop(SqStack&S,BiTree&e)if(S.top=S.base)exit(0);e=*-S.top;voidInitQueue(LinkQueue&Q)if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)exit(0);Q.front-next=NULL;intQueueEmpty(LinkQueueQ)if(Q.front=Q.rear)return1;elsereturn0;voidEnQueue(LinkQueue&Q,BiTreee)QueuePtrp;if(!(p=(QueuePtr)malloc(sizeof(QNode)exit(0);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;voidDeQueue(LinkQueue&Q,BiTree&e)QueuePtrp;if(Q.front=Q.rear)exit(0);p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p); 实验题目(共6题, 第3题)标题：由顺序方式存储的完全二叉树进行重建时限：1000ms内存限制：3000K总时限：3000ms描述：按顺序方式存储的一棵完全二叉树的结点记录，结点个数为n。根据所输入的顺序结构的结点记录建立二叉树，输出树的先序，中序和后序遍历结果。 注：数字“0”表示不存在此结点，没有孩子结点输入：树结点个数n 顺序方式存储的完全二叉树输出：先序遍历输出 中序遍历输出 后序遍历输出输入样例：10 1203400567输出样例：1 2 3 5 6 4 7 5 3 6 2 7 4 1 5 6 3 7 4 2 1 提示：数字“0”的孩子结点全部为“0”来源：#include#includetypedefstruct_TreeNodeintkey;struct_TreeNode*LC;struct_TreeNode*RC;TreeNode;voidCreatFromSqList(TreeNode*&node,int*array,inti,intn)if(nn)exit(0);if(arrayi!=0)node=(TreeNode*)malloc(sizeof(TreeNode);node-key=arrayi;node-LC=NULL;node-RC=NULL;if(2*iLC,array,2*i,n);if(2*i+1)RC,array,2*i+1,n);return;intRepreOrder(TreeNode*T)if(T)printf(%d,T-key);RepreOrder(T-LC);RepreOrder(T-RC);return0;intReInOrder(TreeNode*T)if(T)ReInOrder(T-LC);printf(%d,T-key);ReInOrder(T-RC);return0;intRePostOrder(TreeNode*T)if(T)RePostOrder(T-LC);RePostOrder(T-RC);printf(%d,T-key);return0;intmain()intn,*array;scanf(%d,&n);array=(int*)malloc(sizeof(int)*(n+1);inti;for(i=1;i=n;i+)scanf(%d,&arrayi);TreeNode*root=NULL;CreatFromSqList(root,array,1,n);RepreOrder(root);printf(n);ReInOrder(root);printf(n);RePostOrder(root);printf(n);return0; 实验题目(共6题, 第4题)标题：由二叉树的中序层序重建二叉树时限：1000ms内存限制：10000K总时限：3000ms描述：给定一棵二叉树的中序和层序输出，生成这棵树并按先序和后序输出其中树结构中结点信息为整数输入：树结点个数层序输出序列中序输入序列输出：先序遍历后序遍历输入样例：61 2 3 5 6 72 5 1 6 3 7输出样例：1 2 5 3 6 75 2 6 7 3 1提示：层序输出的第1个为根结点。来源：实验题目(共6题, 第5题)标题：判别平衡二叉树时限：1000ms内存限制：3000K总时限：3000ms描述：给定一棵二叉树的中序和层序输出，判断是否为平衡二叉树的。如果是，输出YES如果不是输出NO，并在下一行输出所有最小不平衡树的根结点其中树结构中结点信息为整数输入：树结点个数中序遍历序列层序遍历序列输出：是否是平衡二叉树的判断结论所有最小不平衡树的根结点输入样例：样例1：31 2 3 2 1 3 样例2：41 2 3 4 1 2 3 4 输出样例：样例1：YES样例2NO2提示：无来源：教材P230-238实验题目(共6题, 第6题)标题：树的括号表示法时限：1000ms内存限制：3000K总时限：3000ms描述：树的括号表示法：先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。例如下图可写成如下形式 (a(b,c,d,e) a / | | b c d e现在给定一个多叉树的括号表示法，要求你创建多叉树，并按层序输出。输入：多叉树的括号表示法：字符串输出：层序输出多叉树输入样例：(a(b,c,d,e)输出样例：abcde提示：树的括号表示法来源：图结构实验题目(共5题, 第1题)标题：图的深度和广度优先遍历时限：2000ms内存限制：5000K总时限：3000ms描述：以邻接矩阵给出一张以整数编号为顶点的图，其中0表示不相连，1表示相连。按深度和广度优先进行遍历，输出全部结果。要求，遍历时优先较小的顶点。如，若顶点0与顶点2，顶点3，顶点4相连，则优先遍历顶点2.输入：顶点个数邻接矩阵输出：DFS深度遍历输出WFS广度遍历输出输入样例：30 1 1 1 0 1 1 1 0 输出样例：DFS0 1 2 1 0 2 2 0 1 WFS0 1 2 1 0 2 2 0 1 提示：顶点整数从0 开始来源：教材实验题目(共5题, 第2题)标题：拓扑排序时限：2000ms内存限制：5000K总时限：3000ms描述：以邻接矩阵给出一张以整数为结点的有向图，其中0表示不是相邻结点，1表示两个结点相连且由当前结点为初始点。利用拓扑排序判断图中是否有环，若有输出YES没有输出NO输入：结点数邻接矩阵输出：YES/NO输入样例：30 1 0 1 0 1 1 0 0 输出样例：YES提示：来源：教材P180-182实验题目(共5题, 第3题)标题：Prim和Kruskal最小生成树时限：2000ms内存限制：15000K总时限：3000ms描述：给出一个矩阵，要求以矩阵方式单步输出生成过程。要求先输出Prim生成过程，再输出Kruskal,每个矩阵输