p=p->lchild; //沿左孩子前进 }if(top!=NULL){
deep=top->flag; no++;
pop(&top,&p); //树结点出栈 printf(\" %c\ p=p->rchild; //沿右孩子 } } }
这是中序遍历的层次打印树结点，采用链接栈的迭代方法，而非从根结点的层次序遍历。
4.递归方法的二叉树遍历操作
void PreOrder(tree *b1){ //递归前序遍历函数 if(b1!=NULL){
printf(\" %c\ PreOrder(b1->lchild); PreOrder(b1->rchild); } }
void MidOrder(tree *b2){ //递归中序遍历函数 if(b2!=NULL){
MidOrder(b2->lchild); printf(\" %c\
MidOrder(b2->rchild); } }
void LastOrder(tree *b3){ //递归后序遍历函数 if(b3!=NULL){
LastOrder(b3->lchild); LastOrder(b3->rchild); printf(\" %c\ } }
这三个函数实现了二叉树的递归遍历方法。前序思想是先根、后左孩子、再右孩子，中序遍历思想是先左孩子、后根、再右孩子，后序是先左孩子、后右孩子、再根。
5.交换左右子树，成为一棵新树
tree *ChangTree(tree *t){ //交换左右子树，递归方法 if(t){
tree *temp;
ChangTree(t->lchild); ChangTree(t->rchild); temp=t->lchild;
t->lchild=t->rchild; t->rchild=temp; }
return t; }
6．非递归方法的二叉树遍历操作
void unPreOrder(tree *t) { //非递归的前序遍历函数 stack *top; tree *p=t; top=NULL;
while (p!=NULL || top!=NULL) //非空树，或栈非空 {
while (p!=NULL) {
printf(\" %c\输出根结点 push(&top,p); //树结点入栈 p=p->lchild; //沿左子树前进 }
if (top!=NULL) {
pop(&top,&p); //树结点出栈 p=p->rchild; //沿右子树前进 } } }
void unMidOrder(tree *t){ // 二叉树非递归中序遍历函数 stack *top; tree *p=t; top=NULL;
while (p!=NULL || top!=NULL) //非空树，或栈非空 {
while (p!=NULL) {
push(&top,p); //树结点入栈 p=p->lchild; //沿右子树前进 }
if (top!=NULL) {
pop(&top,&p); //树结点出栈
printf(\" %c\输出根结点 p=p->rchild; //沿右子树前进 } } }
这两个函数直接调用了链接栈的方法，而不必另外为栈开辟存储空间，有效节省了资源，并且更为简便地实现了非递归的遍历方法。
void unPostOrder(tree *t) { //非递归后序遍历函数，*t指向二叉树的根结点 tree *p[100];
unsigned tag[100]; unsigned top=0;
p[0]=t; tag[0]=0; do {
while(p[top]!=NULL) {
}
p[++top]=p[top]->lchild; tag[top]=0; }
while(tag[top-1]==1)
printf(\" %c\ if (top>0) {
p[top]=p[top-1]->rchild; tag[top-1]=1; tag[top]=0; }
} while(top!=0);
此函数为非递归的后序遍历方法，限于初入门的编程者的水平，这个函数另辟存储空间来建立栈，虽然浪费空间，但也更容易实现非递归的后序遍历。
7.主函数
void main(){ tree *t; tree *h;
printf(\"********************二叉树的基本操作***********************\\n\"); printf(\"\\n请以先序序列输入相应二叉树的结点,以@作为二叉树的空结点:\\n\"); t=Creatbitree();
printf(\"\\n***递归遍历操作部分***\\n\");
printf(\"\\n用先序遍历方法，先序序列为:\\n\"); PreOrder(t);
printf(\"\\n用中序遍历方法，中序序列为:\\n\"); MidOrder(t);
printf(\"\\n用后序遍历方法，后序序列为:\\n\"); LastOrder(t);
printf(\"\\n\\n***非递归遍历操作部分***\\n\"); printf(\"\\n非递归先序遍历，先序序列为:\\n\"); unPreOrder(t); printf(\"\\n\");
printf(\"\\n非递归中序遍历，中序序列为:\\n\"); unMidOrder(t);
printf(\"\\n非递归后序遍历，后序序列为:\\n\"); unPostOrder(t) ; printf(\"\\n\");
printf(\"\\n非递归的层次遍历方法:\\n\"); Output(t);
printf(\"\\n交换左右子树后的中序层次打印:\\n\"); h=ChangTree(t); Output(t);
printf(\"\\n\");
}
七.运行结果：
简要分析：二叉树的递归操作主要是运用二叉链表结构，二叉树的非递归方法主要运用栈存储结构。
八.实验总结
数据结构是计算机程序设计的重要理论技术基础，在理论学习和基础实验的基础上，通过实践设计一定量的程序，掌握应用计算机解决实际问题的基本方法，是理解和运用数据结构及算法，提高编程能力的有效途径，并为学习软件专业课程积累理论基础和实践基础。程序的设计和开发过程，不仅要求我们牢固地掌握各种基础知识，更考查了对基础知识的综合运用能力。这次我的实验课题是二叉树的基本算法综合分析。算法是数据结构的核心，是我们学习软件开发必须掌握的基本知识。
简单课程设计最重要的是基础知识的运用，以及综合分析问题的能力。二叉树的递归算法主要是将二叉树存储到链表结构中，二叉树的非递归算法则主要应用了栈的存储结构。遍历是二叉树各种操作的基础，先序、中序、后序是二叉树遍历的三种基本遍历方法。而这些都是数据结构的基础内容，是我们必须理解和牢记的基础知识。将这些基础算法综合起来，更能清晰地认识和理解各种算法的作用。当然，要学会编程不会仅局限于课本知识，而是根据课本知识进行有效的拓展，并且不得不学会在众多的参考资料中搜索有用的自己所需的知识，并迫使自己去学习掌握它们，从中不断提高自己。例如，课本上只给出了二叉树的递归中序遍历方法，由此可容易推出递归的前序和中序遍历方法，再根据课外资料的学习，我学会了将二叉链表转换为链接栈存储结构的方法。
二叉树的基本操作是多种多样的，由于时间的短促和作者水平有限，因不能做太大规模的设计。虽然程序规模不大，我依然为此付出了努力，仍免不了各种错误的出现。编程过程需要很大的毅力和耐心，而且要有良好的思维和扎实的专业基础知识，所以我需要不断的学习，发现自身不足之处并改正它，逐步提高自身能力，不断取得进步。对于数据结构的学习，我一直感到很吃力，但想过放弃。通过实践，让我们认识到知识的运用性，并加深对基础知识的理解，从中了解自己需要学习的东西并学会自学。在此我要感谢我的老师对我们专心致志的辅导，让我学会了许多分析和解决问题的方法，让我受益匪浅。作为一名计算机专业的学生，今后我将加倍努力学习专业知识，为自己从事的职业打下坚实基础。
参考文献：
1.《C语言程序设计》（第三版）谭浩强 清华大学出版社出版 2.《数据结构（C语言版）》赵坚、姜梅主编 中国水利水电出版社 3.《数据结构（C语言版）》 严蔚敏 吴伟民 清华大学出版社 4.《数据结构与算法》 熊岳山 刘越 电子工业出版社
