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

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

2、树的非递归遍历。由键盘输入一叉树先序序列，用扩展线序序列因数接受并创建一叉链表。遍历前先判断二叉树是否为空，若为空，执行空操作；否则依次执行各遍 历函数相应操作。先序遍历算法思想，先访问根节点，然后按先序遍历左子树，再按先序遍 历右子树。中序遍历算法思想，先按中序遍历左子树，再访问根节点，然后按中序访 问右子树。后序遍历算法思想，先按后序遍历左子树，接着按中序遍历右子树，然后 访问根节点。附：源程序：递归算法程序#include <>#include <>#include <>#define maxsize 100#define FALSE 0#define

3、 TRUE 1typedef struct node*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->rch

4、ild);/* 中序递归遍历*/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()bi

5、tree 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 FAL

6、SE 0#define TRUE 1#define maxsize 100*bt=NULL;typedef struct nodeelse*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|!=-1)while(p!=NULL)printf(&quo

7、t;%c",p->data);push(&s,p);p=p->lchild;if(!=-1)p=pop(&s,p);p=p->rchild;中序遍历void inorder1(bitree root,seqstack s) /bitnode *p;=-1;p=root;while(p!=NULL|!=-1)if(p!=NULL)push(&s,p);p=p->lchild;elsep=pop(&s,p);printf("%c",p->data);p=p->rchild;后序遍历void posto

8、rder1(bitree root) /bitnode *p,*q;seqstack s;q=NULL;p=root;=-1;/printf("%c",p->data);while(p!=NULL|!=-1)while(p!=NULL)push(&s,p); p=p->lchild;if(!=-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;=-1;bitree root;createbitree(&root);printf(" 先序遍历序列:n");preorder1(root,s);printf("n");pri