数据结构实验五报告.docx

数据结构实验五报告

第一篇：数据结构实验五报告实验五报告课程名称：数据结构实验名称：二叉树的创建与遍历实验日期2011/11/16一、实验目的：通过上机实验进一步掌握栈、队列、二叉树的存储结构及基本操作的实现方法。二、实验内容与要求：基于二叉链表存储结构实现二叉树的基本运算，要求：⑴能建立非空二叉树；⑵实现二叉树的先、中、后序递归遍历算法；⑶实现二叉树的非递归的先（或中、或后）序遍历算法及层序遍历算法；⑷记录运行结果并对递归算法和非递归算法的效率加以分析。三、算法设计结构体的定义：typedefstructBiTNote{structNode{};类的定义：classCStack{//栈private:};classLinkQueue{//队列public:BiTreebase;BiTreetop;intstacksize;//当前空间分配量staticconstintSTACK_INIT_SIZE=100;staticconstintSTACKINCREMENT=10;CStack();voidPush(BiTreeT);//入栈voidPop(BiTree&T);//出栈boolStackEmpty();//判断是否是空栈friendclassCBiTree;Node(BiTree&d):num(d),next(NULL){}BiTreenum;Node*next;chardata;structBiTNote*lchild,*rchild;}BiTNote,*BiTree;public:};LinkQueue();boolQueueEmpty();voidEnQueue(BiTree&T);voidDeQueue(BiTree&T);friendclassCBiTree;intlength;//队列元素的个数Node*front;//队列的头指针Node*rear;//队列的尾指针private:classCBiTree{public:};CStack::CStack():stacksize(STACK_INIT_SIZE){//构造函数，初始化}voidCStack::Push(BiTreeT){...}//入栈voidCStack::Pop(BiTree&T){...}//出栈boolCStack::StackEmpty(){}inti=0;//全局变量intCBiTree::CreatBiTree(BiTree&T){}//构造二叉树//LinkQueue类函数的实现LinkQueue::LinkQueue(){}boolLinkQueue::QueueEmpty(){}voidLinkQueue::EnQueue(BiTree&T){}voidLinkQueue::DeQueue(BiTree&T){}intCBiTree::PreOrderTraverse1(BiTreeT,int(*Visit)(char)){...}//前序遍历（递归）intCBiTree::InOrderTraverse(BiTreeT,int(*Visit)(char)){...}//中序遍历（递归）intCBiTree::PostOrderTraverse(BiTreeT,int(*Visit)(char)){...}//后序遍历（递归）intCBiTree::PreOrderTraverse2(BiTreeT,int(*Visit)(char)){//前序遍历（非递归）BiTreep=T;while(p!=NULL||!s.StackEmpty()){BiTreep=(BiTree)malloc(STACK_INIT_SIZE*sizeof(BiTNote));base=p;top=base;intCreatBiTree(BiTree&T);//建立二叉树intPreOrderTraverse1(BiTreeT,int(*Visit)(chare));//前序遍历（递归）intPreOrderTraverse2(BiTreeT,int(*Visit)(chare));//前序遍历（非递归）intInOrderTraverse(BiTreeT,int(*Visit)(chare));//中序遍历（递归）intPostOrderTraverse(BiTreeT,int(*Visit)(chare));//后序遍历（递归）intLevelOrderTraverse(BiTreeT,int(*Visit)(chare));//层序遍历（非递归）CStacks;LinkQueuelink;private:}}while(p!=NULL){}if(!s.StackEmpty()){}s.Pop(p);p=p->rchild;Visit(p->d