第一篇:实验报告:二叉树
实验报告 二叉树
一 实验目的
1、进一步掌握指针变量,动态变量的含义;
2、掌握二叉树的结构特性以及各种存储结构的特点及适用范围。
3、掌握用指针类型描述、访问和处理二叉树的运算。
4、熟悉各种存储结构的特征以及如何应用树结构解决具体问题。
二 实验原理
树形结构是一种应用十分广泛和重要的非线性数据结构,是一种以分支关系定义的层次结构。在这种结构中,每个数据元素至多只有一个前驱,但可以有多个后继;数据元素之间的关系是一对多的层次关系。树形结构主要用于描述客观世界中具有层次结构的数据关系,它在客观世界中大量存在。遍历二叉树的实质是将非线性结构转为线性结构。
三 使用仪器,材料 计算机 2 Wndows xp 3 VC6.0
四实验步骤
【问题描述】建立一个二叉树,请分别按前序,中序和后序遍历该二叉树。【基本要求】从键盘接受输入(按前序顺序),以二叉链表作为存储结构,建立二叉树(以前序来建立),并采用递归算法对其进行前序,中序和后序遍历,将结果输出。
【实现提示】按前序次序输入二叉树中结点的值(一个整数),0表示空树,叶子结点的特征是其左右孩子指针为空。
五实验过程原始记录 基本数据结构描述; 2 函数间的调用关系; 用类C语言描述各个子函数的算法; 附录:源程序。
六 试验结果分析
将实验结果分析、实验中遇到的问题和解决问题的方法以及关于本实验项目的心得体会,写在实验报告上。
第二篇:数据结构二叉树操作验证实验报告
班级:计算机11-2 学号:40 姓名:朱报龙
成绩:_________
实验七 二叉树操作验证
一、实验目的
⑴ 掌握二叉树的逻辑结构;
⑵ 掌握二叉树的二叉链表存储结构;
⑶ 掌握基于二叉链表存储的二叉树的遍历操作的实现。
二、实验内容
⑴ 建立一棵含有n个结点的二叉树,采用二叉链表存储;
⑵ 前序(或中序、后序)遍历该二叉树。
三、设计与编码
#include
void inorder(void visit(BTreeNode
void postorder(void visit(BTreeNode
static void fun(BTreeNode data;}//访问结点 protected: BTreeNode //***********************建树******************************* template template //***********************遍历******************************* template {cout <<“递归先序遍历二叉树:”;s.preorder(s.fun);cout < 答:经常忘记对头结点的定义,以至于程序出错,经定义头结点,使程序正常运行。 b)程序运行的结果如何? 四、实验小结 多练习,多上机,耐心调试程序,找出错误,多总结。 实验报告 课程名:数据结构(C语言版)实验名:二叉树的遍历 姓名: 班级: 学号: 时间:2014.11.03 一 实验目的与要求 1.掌握二叉树的存储方法 2.掌握二叉树的三种遍历方法 3.实现二叉树的三种遍历方法中的一种 二 实验内容 • 接受用户输入一株二叉树 • 输出这株二叉树的前根, 中根, 后根遍历中任意一种的顺序 三 实验结果与分析 //*********************************************************** //头文件 #include #define OK 1 #define ERROR 0 #define OVERFLOW 0 //*********************************************************** typedef struct BiTNode { //二叉树二叉链表存储结构 char data;struct BiTNode *lChild,*rChild;}BiTNode,*BiTree;//*********************************************************** int CreateBiTree(BiTree &T){ //按先序次序输入二叉中树结点的值,空格表示空树 //构造二叉链表表示的二叉树T char ch;fflush(stdin);scanf(“%c”,&ch);if(ch==' ')T=NULL;else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))return(OVERFLOW);T->data=ch;CreateBiTree(T->lChild);CreateBiTree(T->rChild);} return(OK);} //********************************************************* void PreOrderTraverse(BiTree T){ //采用二叉链表存储结构,先序遍历二叉树的递归算法 if(T){ printf(“%c”,T->data);PreOrderTraverse(T->lChild);PreOrderTraverse(T->rChild);} } /***********************************************************/ void InOrderTraverse(BiTree T){ //采用二叉链表存储结构,中序遍历二叉树的递归算法 if(T){ InOrderTraverse(T->lChild);printf(“%c”,T->data);InOrderTraverse(T->rChild);} } //*********************************************************** void PostOrderTraverse(BiTree T){ //采用二叉链表存储结构,后序遍历二叉树的递归算法 if(T){ PostOrderTraverse(T->lChild);PostOrderTraverse(T->rChild);printf(“%c”,T->data);} } //*********************************************************** void main(){ //主函数分别实现建立并输出先、中、后序遍历二叉树 printf(“please input your tree follow the PreOrder:n”);BiTNode *Tree;CreateBiTree(Tree);printf(“n先序遍历二叉树:”);PreOrderTraverse(Tree);printf(“n中序遍历二叉树:”);InOrderTraverse(Tree);printf(“n后序遍历二叉树:”);PostOrderTraverse(Tree);} 图1:二叉树的遍历运行结果 班级:380911班 学号:57000211 姓名:徐敏 实验报告 一,实验目的: ·掌握二叉树的链式存储结构; ·掌握构造二叉树的方法; ·加深对二叉树的中序遍历的理解; 二,实验方法: ·用递归调用算法中序遍历二叉树。三,实验步骤: ·通过链式存储建立一颗二叉树。 ·设计一个算法实现中序遍历二叉树。四,具体实验步骤: #include typedef struct _BTNODE{ char c;struct _BTNODE *lchild;struct _BTNODE *rchild;}BTNODE,*PBTNODE; void PrintBTree(PBTNODE p,int depth);void ConstructBTree(PBTNODE p);void InorderTraverse(PBTNODE p); void main(){ PBTNODE p;p=(PBTNODE)calloc(1,sizeof(BTNODE));printf(“Input the data:”);ConstructBTree(p);PrintBTree(p,0);printf(“Now InorderTraverse:”);InorderTraverse(p);printf(“nPress any key to continue...”);getchar();} void PrintBTree(PBTNODE p,int depth){ 班级:380911班 学号:57000211 姓名:徐敏 int i;if(p==NULL){ return;}else{ for(i=0;i printf(“--”);} printf(“>”); printf(“%cn”,p->c); PrintBTree(p->lchild,depth+1); PrintBTree(p->rchild,depth+1);} } void ConstructBTree(PBTNODE p){ int side;char c;side=LEFT;while(TRUE){ scanf(“%c”,&c); if(c=='n'){ //printf(“EOFn”); return; } // printf(“%dn”,c); switch(c){ case '|': break; case')': return; case',': side=RIGHT; break; case'(': if(side==LEFT){ if(p->lchild==NULL){ p->lchild=(PBTNODE)calloc(1,sizeof(BTNODE)); } ConstructBTree(p->lchild); }else{ if(p->rchild==NULL){ p->rchild=(PBTNODE)calloc(1,sizeof(BTNODE)); } 班级:380911班 学号:57000211 姓名:徐敏 ConstructBTree(p->rchild); } break; default: if(side==LEFT){ p->lchild=(PBTNODE)calloc(1,sizeof(BTNODE)); p->lchild->c=c; }else{ p->rchild=(PBTNODE)calloc(1,sizeof(BTNODE)); p->rchild->c=c; } } } } void InorderTraverse(PBTNODE p){ if(p==NULL){ return;}else{ InorderTraverse(p->lchild); printf(“[%c] ”,p->c); InorderTraverse(p->rchild);} return;} 五,实验过程: ·输出:Input the date; ·输入:1(2(3,4),5(6,7)); ·输出:Now InorderTraverse:【3】【2】【4】【1】【6】【5】【7】;六,上机实验体会: ·体会到熟练掌握各种程序算法的重要性; ·通过上机练习,充分理解了链式建立二叉树的算法; ·形象的了解二叉树的结构,能够熟练的进行先序,中序,后序遍历二叉树。 《数据结构》 第六次实验报告 学生姓名 学生班级 学生学号 指导老师 重庆邮电大学计算机学院 计算机专业实验中心 一、实验内容 1)采用二叉树链表作为存储结构,完成二叉树的建立,先序、中序和后序以及按层次遍历的操作,求所有叶子及结点总数的操作。2)输出树的深度,最大元,最小元。 二、需求分析 遍历二叉树首先有三种方法,即先序遍历,中序遍历和后序遍历。递归方法比较简单,首先获得结点指针如果指针不为空,且有左子,从左子递归到下一层,如果没有左子,从右子递归到下一层,如果指针为空,则结束一层递归调用。直到递归全部结束。下面重点来讲述非递归方法: 首先介绍先序遍历: 先序遍历的顺序是根 左 右,也就是说先访问根结点然后访问其左子再然后访问其右子。具体算法实现如下:如果结点的指针不为空,结点指针入栈,输出相应结点的数据,同时指针指向其左子,如果结点的指针为空,表示左子树访问结束,栈顶结点指针出栈,指针指向其右子,对其右子树进行访问,如此循环,直至结点指针和栈均为空时,遍历结束。 再次介绍中序遍历: 中序遍历的顺序是左 根 右,中序遍历和先序遍历思想差不多,只是打印顺序稍有变化。具体实现算法如下:如果结点指针不为空,结点入栈,指针指向其左子,如果指针为空,表示左子树访问完成,则栈顶结点指针出栈,并输出相应结点的数据,同时指针指向其右子,对其右子树进行访问。如此循环直至结点指针和栈均为空,遍历结束。最后介绍后序遍历: 后序遍历的顺序是左 右 根,后序遍历是比较难的一种,首先需要建立两个栈,一个用来存放结点的指针,另一个存放标志位,也是首先访问根结点,如果结点的指针不为空,根结点入栈,与之对应的标志位也随之入标志位栈,并赋值0,表示该结点的右子还没有访问,指针指向该结点的左子,如果结点指针为空,表示左子访问完成,父结点出栈,与之对应的标志位也随之出栈,如果相应的标志位值为0,表示右子树还没有访问,指针指向其右子,父结点再次入栈,与之对应的标志位也入栈,但要给标志位赋值为1,表示右子访问过。如果相应的标志位值为1,表示右子树已经访问完成,此时要输出相应结点的数据,同时将结点指针赋值为空,如此循环直至结点指针和栈均为空,遍历结束。 三、详细设计 源代码: #include typedef struct Tnode //定义结点 { char data;//存储结点数据 struct Tnode *left;//定义结点左子指针 struct Tnode *right;//定义右子指针 }Tnode,*Pnode;//声明Tnode类型的变量和指针 typedef struct Stack//定义栈 { Pnode pnode[MAX];//存放数据 int p;//栈顶指针 }Stack,*Pstack;//定义Stack类型的变量和指针 void Push(Pstack pstack,Pnode pnode)//入栈 { } Pnode Pop(Pstack pstack)//出栈 { } Pnode Top(Pstack pstack)//看栈顶元素 { } int Isempty(Pstack pstack)//栈判空 { } int Isfull(Pstack pstack)//栈满 { } void Initstack(Pstack pstack)//初始化栈 if(pstack->p==FULL)else return 0;return 1;if(pstack->p==EMPTY)else return 0;;return 1;return pstack->pnode[pstack->p];return pstack->pnode[pstack->p--];pstack->p ++;pstack->pnode[pstack->p] = pnode;//赋值 { } void Inittnode(Pnode root,Pnode left,Pnode right,char data)//初始化结点 { } void PreorderR(Pnode proot)//递归先序遍历算法 { } void InorderR(Pnode proot)//递归中序遍历算法 { } void PostorderR(Pnode proot)//递归后序遍历算法 { } void PreorderI(Pnode proot,Pstack pstack)//非递归先序遍历算法 { Initstack(pstack);//初始化栈 while(proot||!Isempty(pstack))//如果栈空并且结点指针空,则结束循环 { if(proot){ printf(“%2c”,proot->data);if(proot){ } PostorderR(proot->left);PostorderR(proot->right);printf(“%2c”,proot->data);if(proot){ } InorderR(proot->left);printf(“%2c”,proot->data);InorderR(proot->right);if(proot){ } printf(“%2c”,proot->data);PreorderR(proot->left);PreorderR(proot->right);root->left=left;root->right = right;root->data = data;pstack->p=EMPTY; } } } else { } if(Isfull(pstack))//如果栈满不能执行入栈操作 { } Push(pstack,proot);//入栈 proot=proot->left;//指针指向左子 printf(“栈满,不能执行入栈操作!”);return;if(Isempty(pstack))//栈空时不能出栈 { } proot = Pop(pstack);//执行出栈操作 proot=proot->right;//指针指向右子 printf(“栈空,不能执行出栈操作!”);return;void InorderI(Pnode proot,Pstack pstack)//非递归中序遍历算法 { Initstack(pstack);//初始化栈 while(proot||!Isempty(pstack))//循环结束条件 { if(proot){ } else { if(Isempty(pstack)){ } proot = Pop(pstack);//出栈 printf(“%2c”,proot->data);//打印数据 printf(“栈空,不能执行出栈操作!”);return;if(Isfull(pstack)){ } Push(pstack,proot);//执行入栈操作 proot = proot->left;//指针指向左子 printf(“栈满,不能执行入栈操作!”);return; } } } proot=proot->right;//指针指向右子 void PostorderI(Pnode proot,Pstack pstack)//非递归后续遍历算法 { } void main(){ int flags[MAX];//定义标志位栈 int p =-1;//初始化标志位栈 int flag;//存放标志位 Initstack(pstack);//初始化栈 while(proot||!Isempty(pstack))//循环结束条件 { } if(proot){ } else { } proot = Pop(pstack);//指针出栈 flag = flags[p--];//相应标志位出栈 if(flag==0)//如果标志位为0表示右子还未访问过 { } else { } printf(“%2c”,proot->data);//打印数据 proot = NULL;//将结点指针置空 flag =1;//将标志位置1,右子已访问 flags[++p] = flag;//标志位入栈 Push(pstack,proot);//结点入栈 if(Isfull(pstack)){ } flags[++p] = 0;//标志位置0,并入栈 Push(pstack,proot);//结点入栈 proot=proot->left;//指针指向左子 printf(“栈满,不能执行入栈操作!”);return; proot = proot->right;//指针指向右子 Tnode A,B,C,D,E,F,G;//声明结点变量 Stack stack;//声明栈 Inittnode(&A,&B,&C,'A');//初始化结点 Inittnode(&B,NULL,&D,'B');Inittnode(&C,&E,&F,'C');Inittnode(&D,NULL,NULL,'D');Inittnode(&E,NULL,NULL,'E');Inittnode(&F,&G,NULL,'F');Inittnode(&G,NULL,NULL,'G');printf(“你定义的树的结构是:n”);printf(“A(B(D)C(E F(G)))n”);printf(“=====================下面是遍历结果====================n”);printf(“=====================递归先序遍历:====================n”);PreorderR(&A);printf(“n”);printf(“=====================非递归先序遍历:==================n”);PreorderI(&A,&stack);printf(“n”);printf(“=====================递归中序遍历:====================n”);InorderR(&A);printf(“n”);printf(“=====================非递归中序遍历:==================n”);InorderI(&A,&stack);printf(“n”);PostorderR(&A);printf(“n”);PostorderI(&A,&stack); printf(“n”); /*一下是调用相应的函数输出遍历结果*/ } printf(“=====================递归后序遍历:====================n”); printf(“=====================非递归后序遍历:==================n”); 五、遇到的问题及解决办法 这部分我主要遇到如下两个问题,其内容和解决方法如下所列: 执行程序时程序停止运行,其效果如图: 解决方法:看到程序停止运行,推测可能的原因:遇到死循环、参数设置不合理或者结构体没有造好。首先对结构体进行了检查,各个成员声明正常无误,在对程序进行调试,程序正常跳出循环,因此最可能是自定义函数的参数设置的不合理,因此对调用的自定义函数进行相应的改动,将参数由具体类型改为指针类型后,程序正常运行。 程序不停的输出同一个结点的数据,其效果入图: 解决方法:分析运行结果可知,第一不停的输出证明遇到了死循环,第二输出的是同一个结点的数据,表示指针没有按预期进行指向,首先对程序进行调试,发现程序没有添加循环结束条件,添加循环结束条件后,只能输出树的部分结点的数据,对标志位进行修改后,程序运行正常,也能正确输出遍历结果。 六、心得体会 通过这次作业真的受益匪浅,感触良多: 首先,要提高编程能力,必须多动手,多实践,而不是仅仅局限在书本上,更不能眼高手低。眼高手低,懒得动手,这就犯了编程人员的大忌。大一我们开始接触C语言,这是我们接触到的第一种编程语言,但是当时徒有对编程的兴趣,却没有付诸行动,动手少,结果考试险过,通过这次作业,我再次看了C语言课本,边看边写代码,理解快,印象深刻,思维也活跃许多,状态也好,真正的意识到,编程能力需要靠实践来提升。当自己写出意想的程序后,真的有些成就感。再者,在吴老师的指导和要求下,我们改掉了很多的编程坏习惯的同时也养成了良好的编程习惯,另一方面我们态度端正了很多,认真完成好每一项任务,这样无形中提高了对自己的要求,同时也增强了我们的动手能力和编程能力。 七、附录 运行结果截图。第三篇:数据结构-二叉树的遍历实验报告
第四篇:数据结构实验报告——中序遍历二叉树
第五篇:数据结构实验报告-二叉树的实现与遍历