实验报告课程名称数据结构实验名称二叉树的遍历日期2023/05/30学生学号B11050226姓名枯天蝎班级B110502实验目的：掌握二叉树的结构特性，掌握用指针类型描述、遍历二叉树的运算实验条件：电脑一台 Vc++6.0实验内容与算法思想：内容：P213 实习题 1建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序、和后序），打印输出遍历结果基本规定如下：从键盘接受输入线序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行遍历（先序、中序、后序），然后将遍历结果打印输出规定采用递归和非递归两种方法实现算法思想：定义二叉树结构体类型时，也定义了一个顺序栈结构体类型，用以辅助完毕二叉树的非递归遍历由键盘输入二叉树先序序列，用扩展线序序列函数接受并创建二叉链表遍历前先判断二叉树是否为空，若为空，执行空操作；否则依次执行各遍历函数相应操作先序遍历算法思想，先访问根节点，然后按先序遍历左子树，再按先序遍历右子树中序遍历算法思想，先按中序遍历左子树，再访问根节点，然后按中序访问右子树后序遍历算法思想，先按后序遍历左子树，接着按中序遍历右子树，然后访问根节点运营结果：递归算法： 非递归算法：实验总结（结论或问题分析）：通过实验，加深了对C语言特别是函数调用部分的结识和掌握。
没有找到在实验运营结果上明确区分递归算法实现的遍历和非递归算法实现的遍历的方法实验成绩任课教师署名张红霞附：源程序：递归算法程序#include #include #include #define maxsize 100#define FALSE 0#define TRUE 1typedef struct node //二叉树结构体类型定义{ char data; struct node *lchild; struct node *rchild;}bitnode,*bitree;/*扩展先序序列创建二叉链表*/void cteatebitree(bitree *bt){ char ch; ch=getchar(); if(ch=='.')*bt=NULL; else { *bt=(bitree)malloc(sizeof(bitnode)); (*bt)->data=ch; cteatebitree(&((*bt)->lchild)); cteatebitree(&((*bt)->rchild)); }}/*先序递归遍历*/void preorder(bitree root){ if(root!=NULL) { printf("%c ",root->data); preorder(root->lchild); preorder(root->rchild); }}/*中序递归遍历*/void inorder(bitree root){ if(root!=NULL) { preorder(root->lchild); printf("%c ",root->data); preorder(root->rchild); }}/*后序递归遍历*/void postorder(bitree root){ if(root!=NULL) { preorder(root->lchild); preorder(root->rchild); printf("%c ",root->data); }}void main(){ bitree bt; cteatebitree(&bt); printf("先序递归遍历序列：\n"); preorder(bt); printf("\n"); printf("中序递归遍历序列：\n"); inorder(bt); printf("\n"); printf("后序递归遍历序列：\n"); postorder(bt); printf("\n");}非递归算法程序#include #include #include #define FALSE 0#define TRUE 1#define maxsize 100typedef struct node //二叉树结构体定义{ char data; struct node *lchild; struct node *rchild;}bitnode,*bitree;typedef struct //顺序栈结构体定义{ bitree elem[maxsize]; int top;}seqstack;int push(seqstack *s,bitree x) //入栈{ if(s->top==maxsize-1) return(FALSE); s->top++; s->elem[s->top]=x; return(TRUE);}bitree pop(seqstack *s,bitree x) //出栈{ if(s->top==-1) return NULL; else { x=s->elem[s->top]; s->top--; return x; }}int gettop(seqstack *s,bitree *x) //读取栈顶元素{ if(s->top==-1) return FALSE; else { *x=s->elem[s->top]; return TRUE; }}void createbitree(bitree *bt) //扩展先序序列创建二叉链表{ char ch; ch=getchar(); if(ch=='.')*bt=NULL; else { *bt=(bitree)malloc(sizeof(bitnode)); (*bt)->data=ch; createbitree(&((*bt)->lchild)); createbitree(&((*bt)->rchild)); }}void preorder1(bitree root,seqstack s) //先序遍历{ bitnode *p; p=root; while(p!=NULL||!(s.top==-1)) { while(p!=NULL) { printf("%c",p->data); push(&s,p); p=p->lchild; } if(!(s.top==-1)) { p=pop(&s,p); p=p->rchild; } }}void inorder1(bitree root,seqstack s) //中序遍历{ bitnode *p; s.top=-1; p=root; while(p!=NULL||!(s.top==-1)) { if(p!=NULL) { push(&s,p); p=p->lchild; } else { p=pop(&s,p); printf("%c",p->data); p=p->rchild; } }}void postorder1(bitree root) //后序遍历{ bitnode *p,*q; seqstack s; q=NULL; p=root; s.top=-1; //printf("%c",p->data); while(p!=NULL||!(s.top==-1)) {while(p!=NULL) { push(&s,p); p=p->lchild; } if(!(s.top==-1)) { gettop(&s,&p); if((p->rchild==NULL)||(p->rchild==q)) { printf("%c",p->data); q=p; p=pop(&s,p); p=NULL; } else p=p->rchild; }}}void main(){ printf("先序序列创建二叉树\n"); seqstack s; s.top=-1; bitree root; createbitree(&root); printf("先序遍历序列:\n"); preorder1(root,s); printf("\n"); printf("中序遍历序列:\n"); inorder1(root,s); printf("\n"); printf("后序遍历序列:\n"); postorder1(root); printf("\n");}。