实验题目：二叉树的操作
实验者信息：班级 13007102，姓名庞文正，学号 1300710226
实验完成的时间 3:00
一、 实验目的。
1,掌握二叉树链表的结构和二叉树的建立过程。
2,掌握队列的先进先出的运算原则在解决实际问题中的应用。
3,进一步掌握指针变量、指针数组、动态变量的含义。
4,掌握递归程序设计的特点和编程方法。
二、 实验内容。
已知以二叉链表作存储结构，试编写按层次遍历二叉树的算法。（所谓层次遍历，是指从二叉树的根结点开始从上到下逐层遍历二叉树，在同一层次中从左到右依次访问各个节点。）调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。
加深对算法的理解。
三、 算法设计与编码。
1. 本实验用到的理论知识。
总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，最好能加上自己的解释。
本算法要采用一个循环队列que，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉的目的。
2. 算法概要设计。
给出实验的数据结构描述，程序模块、功能及调用关系。
#include<>
#include<>
#define m 100
typedef struct node //二叉链表节点结构
int data; /数据域
struct node *lchild,*rchild; /左孩子右孩子链
bitree;
bitree *que[m]; 定义一个指针数组，说明队列中的元素 bitree 指针类型。
int front=0, rear=0; /初始化循环列队
bitree *creat() 建立二叉树的递归算法
bitree *t;
int x;
scanf("%d",&x);
if(x==0) t=null; /以 x=0 表示输入结束
elsereturn t;
void inorder(bitree *t) /中序遍历二叉树的递归算法
if(t!=null)
void enqueue(t) /把 bitree 类型的节点 *t 列入队列
bitree *t;
if(front!=(rear+1)%m) /判断队列是否已满
bitree *delqueue()
if(front=rear) return null; /判断队列不为空。
front=(front+1)%m;
return (que[front]);
void levorder(t) /层次遍历二叉树的算法
bitree *t;
bitree *p;
if(t!=null)
main()
bitree *root;
printf("");
root=creat();
inorder(root);
printf("");
levorder(root);
四、 运行与测试。
1） 在调试程序的过程中遇到什么问题，是如何解决的？
未遇到问题，只是就一个输入框框，感觉不知道错**了！
2） 设计了那些测试数据？测试结果是什么？
3） 程序运行的结果如何？
1、 预习思考题。
调试好上述程序后，试着完成以下拓展内容：
1） 写出二叉树前序遍历和后序遍历的递归算法，并在主函数中调用它，调试好程序并分析其运行结果。
/先序遍历二叉树。
void preorder(bitree root)
//先序遍历二叉树，root为指向二叉树跟结点的指针。
if(root!=null)
visit(root->data);/
访问根结点。
preorder(root->lchild);/先序遍历左子树。
preorder(root->rchild);/先序遍历右子树。
/后序遍历二叉树。
void postorder(bitree root)
if(root!=null)
postorder(root->lchild);
postorder(root->rchild);
visit(root->data);
2） 在二叉树的层次遍历中，如果不采用循环队列，而是采用顺序队列，会出现什么问题？
会产生溢出或资源空间浪费。
3） 写出二叉树三种遍历的非递归算法，并在主函数中调用它，调试好程序并分析其运行结构。
2、 分析讨论题：
试分析一下递归算法和非递归算法的优缺点。
有点：递归算法容易实现，**少速度快。
缺点：难以理解，容易出错。
五、 总结和心得。
实验完成后的总结和思考。
此次试验真心困难，很多不懂，基本是一知半解，甚至部分是copy来的！
树和二叉树数据结构实验报告
实习报告。题目 编写一个实现基于二叉树表示的算术表达式expression操作程序。班级 姓名 学号 完成日期 一 需求分析。算术表达式expression内可以含有变量 a z 常量 0 9 和二元算术符乘幂 实现以下操作 1 readexpr e 以字符序列的形式输入语法正确的前缀表达式并构造表...
数据结构实验报告实验三二叉树的建立与遍历
昆明理工大学信息工程与自动化学院学生实验报告。201 201 学年第一学期 课程名称 数据结构开课实验室年月日。一。实验内容 二叉树的建立与遍历，其中遍历有前序遍历，中序遍历和后序遍历。以及二叉树中序线索化及线索化遍历。二。实验目的 学会二叉树二叉链表非线性存储结构上实现的各种算法。三。主要程序 分...