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

《遍历二叉树(递归+非递归)实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、历和非递归算法实现的遍历的方法。实验成绩任课教师签名张红霞附：源程序：递归算法程序#include#include#include#definemaxsize100#defineFALSE0#defineTRUE1typedefstructnode//二叉树结构体类型定义{chardata;structnode*lchild;structnode*rchild;}bitnode,*bitree;范文./*扩展先序序列创建二叉链表*/voidcteatebitree(bitree*bt){charch;ch=getchar()

4、;if(ch=='.')*bt=NULL;else{*bt=(bitree)malloc(sizeof(bitnode));(*bt)->data=ch;cteatebitree(&((*bt)->lchild));cteatebitree(&((*bt)->rchild));}}/*先序递归遍历*/voidpreorder(bitreeroot){if(root!=NULL){printf("%c",root->data);preorder(root->lchild);preorder(root->rchild);}}/*中序递归遍历*/voidinorder(bitreeroo

5、t){if(root!=NULL){范文.preorder(root->lchild);printf("%c",root->data);preorder(root->rchild);}}/*后序递归遍历*/voidpostorder(bitreeroot){if(root!=NULL){preorder(root->lchild);preorder(root->rchild);printf("%c",root->data);}}voidmain(){bitreebt;cteatebitree(&bt);printf("先序递归遍历序列：");preorder(bt);print

6、f("");printf("中序递归遍历序列：");inorder(bt);printf("");printf("后序递归遍历序列：");postorder(bt);printf("");范文.}非递归算法程序#include#include#include#defineFALSE0#defineTRUE1#definemaxsize100typedefstructnode//二叉树结构体定义{chardata;structnode*lchild;structnode*rchild;}bitnode,*b

7、itree;typedefstruct//顺序栈结构体定义{bitreeelem[maxsize];inttop;}seqstack;intpush(seqstack*s,bitreex)//入栈{if(s->top==maxsize-1)return(FALSE);s->top++;s->elem[s->top]=x;return(TRUE);}范文.bitreepop(seqstack*s,bitreex)//出栈{if(s->top==-1)returnNULL