数据结构实验-二叉树的操作.doc

《数据结构实验-二叉树的操作.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、*******************************实验题目：二叉树的操作实验者信息：班级13007102，姓名庞文正，学号1300710226实验完成的时间3:00******************************一、实验目的1,掌握二叉树链表的结构和二叉树的建立过程。2,掌握队列的先进先出的运算原则在解决实际问题中的应用。3,进一步掌握指针变量、指针数组、动态变量的含义。4,掌握递归程序设计的特点和编程方法。二、实验内容已知以二叉链表作存储结构，试编写按层次遍历二叉树的算法。（所谓层次遍历，是指从二叉树的根结

2、点开始从上到下逐层遍历二叉树，在同一层次中从左到右依次访问各个节点。）调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。加深对算法的理解。三、算法设计与编码1.本实验用到的理论知识总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，最好能加上自己的解释。本算法要采用一个循环队列que，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉的

3、目的。2.算法概要设计给出实验的数据结构描述，程序模块、功能及调用关系#include#include#defineM100typedefstructnode//二叉链表节点结构{intdata;//数据域structnode*lchild,*rchild;//左孩子右孩子链}bitree;bitree*que[M];//定义一个指针数组，说明队列中的元素bitree指针类型intfront=0,rear=0;//初始化循环列队bitree*creat()//建立二叉树的递归算法{bitree*

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

5、a);inorder(t->rchild);}}voidenqueue(t)//把bitree类型的节点*t列入队列bitree*t;{if(front!=(rear+1)%M)//判断队列是否已满{rear=(rear+1)%M;que[rear]=t;}}bitree*delqueue(){if(front=rear)returnNULL;//判断队列不为空front=(front+1)%M;return(que[front]);}voidlevorder(t)//层次遍历二叉树的算法bitree*t;{bitree*p;if(

6、t!=NULL){enqueue(t);//根节点入队while(front!=rear)//当前队列不为空时{p=delqueue();//输出对头元素，并把其左右孩子入队列。此过程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);prin

7、tf("");levorder(root);}一、运行与测试（1）在调试程序的过程中遇到什么问题，是如何解决的？未遇到问题，只是就一个输入框框，感觉不知道错哪里了！（2）设计了那些测试数据？测试结果是什么？（1）程序运行的结果如何？1、预习思考题调试好上述程序后，试着完成以下拓展内容：（1）写出二叉树前序遍历和后序遍历的递归算法，并在主函数中调用它，调试好程序并分析其运行结果。//先序遍历二叉树voidPreOrder(BiTreeroot){//先序遍历二叉树，root为指向二叉树跟结点的指针if(root!=NULL){Vi

8、sit(root->data);//访问根结点PreOrder(root->LChild);//先序遍历左子树PreOrder(root->RChild);//先序遍历右子树}}//后序遍历二叉树voidPostOrder(BiTre