实验四二叉树

《实验四二叉树》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、5^^1^rTwrTwrTwrTwrTwrT*rT*rT*rT*rT*rT*»T>rT*rTwrT*rTwrT*rTwrT*实验题目：二叉树的操作(实验四)实验者信息：实验完成的时间：^2zk1*k1*<1^5^rTwrTw,J，rTw,J，rTw,J，rTw,J，rTw,J，rTwrT*rT*rT*rT*rT*rTwrT*rTwrT*rTwrT*rTwrT*1、实验目的(1)掌握二叉树链表的结构和二叉树的建立过程。(2)掌握队列的先进先出的运算原则在解决实际问题中的应川。(3)进一步掌握指针变量、指针数组、动态变量的含义。(4)掌握递归程序设计的特点和编程方法。2、实验要求(

2、1)熟练掌握二叉链表的存储结构。(2)熟练掌握循环队列的基本操作。(3)理解所给出的算法，掌握循环队列在实际中的应用。(4)加深对递归算法的理解。(5)将上机程序调试通过，并能独立完成一至两个拓展题目。3、实验内容已知以二叉链表作存储结构，试编写按层次遍历二叉树的算法。(所谓层次遍历，是指从二叉树的根结点开始从上到T逐层遍历二叉树，在同一层次中从左到右依次访问各个节点。)调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。加深对算法的理解。4、实验方法本算法要采川一个循环队列que，先将二叉树根结点入队列，然后退队列，输出该结点;若它有左子树，便将左子树根结

3、点入队列：若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉的目的。#include#include#defineM100#defineNull0typedefstructnode/*二叉链表结点结构*/{intdata;/*数据域巧structnode*lchild，*rchild;/*左、右孩子域*/}bitree;bitree*que[Ml;/*定义一个指针数组，说明队列屮的元素类型为bitree指针类型*/intfront=0，rear=0;/*初始化循环队列*/bitree*

4、creat()/*建立二叉树的递归算法*/{bitree*t;intx;scanf(H%dH,&x);if(x==0)t=Null;/*以x=0表示输入错束*/else{t=malloc(sizeof(bitree));/*动态生成结点t，分别给结点t的数1R•域、左右孩子域赋值,给左右孩子域赋值时用到了递归的思想。*/t-〉data=x;t->lchild=creat();t->rchild=creat();}returnt;}voidinorder(bitree*t)/*中序遍历二叉树的递归算法*/{if(t!=Null){inorder(t->lchild);printf

5、(,,%4d,t->data);inorder(t->rchild);voidenqueue⑴/*把bitree类型的结点*t入队列*/bitree*t;{if(front!=(rear+l)%M)/*判断队列是否己满*/{rear=(rear+l)%M;que[rear]=t;}}bitree*delqueue(){if(front==rear)/*判断队列不为空*/returnNull;front=(front+1)%M;return(queffrontT);}voidlevorder(t)/*层次遍历二叉树的算法bitree*t;{bitree*p;if(t!=Null

6、){enqueue(t);/*根结点入队*/while(front!=rear)/*当当前队列不为空时*/{pzdelqueueO;/*输出对头元素，并把其左右孩子入队。此过程一直递归，直到队列为空*/printf("%4d",p->data);if(p->lchild!=Null)enqueue(p->lchild);if(p-〉rchild!二Null)enqueue(p->rchild);)}}main()/*主函数{bitree*root;printf("");root=creat();inorder(root);printf(”n);levorder(root

7、);printf(nn);}运行结果：■3.E:编程®l39Debug39.exe"12300003211123Pressanykeytocontinue5、预习思考题调试好上述程序后，试着完成以下拓展内容：(1)写出二叉树前序遍历和后序遍历的递归算法，并在主函数中调用它，调试好程序并分析其运行结果。voidpreorder(bitree*t)/*前序遍历二叉树的递归算法*/{if(t!=NULL){printf(〃％4d〃，t->data);preorder(t->lchild