遍历二叉树(递归+非递归)实验报告

1、;实验报告课程名称数据结构实验名称二叉树的遍历日期2013/05/30学生学号B11050226姓名枯天蝎班级B110502实验目的：掌握二叉树的结构特征，掌握用指针类型描述、遍历二叉树的运算。实验条件：电脑一台 Vc+6.0实验内容与算法思想：内容：P213 实习题 1建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序、和后序），打印输出遍历结果。基本要求如下：从键盘接受输入线序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行遍历（先序、中序、后序），然后将遍历结果打印输出。要求采用递归和非递归两种方法实现。算法思想：定义二叉树结构体类型时，也定义了一个顺序栈结

2、构体类型，用以辅助完成二叉树的非递归遍历。由键盘输入二叉树先序序列，用扩展线序序列函数接受并创建二叉链表。遍历前先判断二叉树是否为空，若为空，执行空操作；否则依次执行各遍历函数相应操作。先序遍历算法思想，先访问根节点，然后按先序遍历左子树，再按先序遍历右子树。中序遍历算法思想，先按中序遍历左子树，再访问根节点，然后按中序访问右子树。后序遍历算法思想，先按后序遍历左子树，接着按中序遍历右子树，然后访问根节点。运行结果：递归算法： 非递归算法：实验总结（结论或问题分析）：通过实验，加深了对C语言尤其是函数调用部分的认识和掌握。没有找到在实验运行结果上明确区分递归算法实现的遍历和非递归算法实现的遍历

3、的方法。实验成绩任课教师签名张红霞附：源程序：递归算法程序#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

4、)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-dat

5、a);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);pri

6、ntf(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 elemmaxsize;int top;seqstack;int push(seqstack *s,bitree x) /入栈if(s-top=maxsize-1)ret

7、urn(FALSE);s-top+;s-elems-top=x;return(TRUE);bitree pop(seqstack *s,bitree x) /出栈if(s-top=-1) return NULL;elsex=s-elems-top;s-top-;return x;int gettop(seqstack *s,bitree *x) /读取栈顶元素if(s-top=-1) return FALSE;else*x=s-elems-top;return TRUE;void createbitree(bitree *bt) /扩展先序序列创建二叉链表char ch;ch=getchar(

8、);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-

9、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;elsep=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;cr