实验四二叉树.doc

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

1、*******************************实验题目：二叉树的操作（实验四）实验者信息：实验完成的时间:******************************1、实验目的（1）掌握二叉树链表的结构和二叉树的建立过程。（2）掌握队列的先进先出的运算原则在解决实际问题中的应用。（3）进一步掌握指针变量、指针数组、动态变量的含义。（4）掌握递归程序设计的特点和编程方法。2、实验要求（1）熟练掌握二叉链表的存储结构。（2）熟练掌握循环队列的基本操作。（3）理解所给出的算法，掌握循环队列

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

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

4、=0,rear=0;/*初始化循环队列*/bitree*creat()/*建立二叉树的递归算法*/{bitree*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;}voidinorde

5、r(bitree*t)/*中序遍历二叉树的递归算法*/{if(t!=Null){inorder(t->lchild);printf("%4d",t->data);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)/*判断队列不为空

6、*/returnNull;front=(front+1)%M;return(que[front]);}voidlevorder(t)/*层次遍历二叉树的算法*/bitree*t;{bitree*p;if(t!=Null){enqueue(t);/*根结点入队*/while(front!=rear)/*当当前队列不为空时*/{p=delqueue();/*输出对头元素，并把其左右孩子入队。此过程一直递归，直到队列为空*/printf("%4d",p->data);if(p->lchild!=Null)e

7、nqueue(p->lchild);if(p->rchild!=Null)enqueue(p->rchild);}}}main()/*主函数*/{bitree*root;printf("");root=creat();inorder(root);printf("");levorder(root);printf("");}运行结果：1、预习思考题调试好上述程序后，试着完成以下拓展内容：（1）写出二叉树前序遍历和后序遍历的递归算法，并在主函数中调用它，调试好程序并分析其运行结果。voidpre

8、order(bitree*t)/*前序遍历二叉树的递归算法*/{if(t!=NULL){printf("%4d",t->data);preorder(t->lchild);preorder(t->rchild);}}voidpostorder(bitree*t)/*前序遍历二叉树的递归算法*/{if(t!=NULL){postorder(t->lchild);postorder(t->rchild);printf("%4d",t->data);}}（3）