二叉树的建立及遍历94239

《二叉树的建立及遍历94239》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构实验五课程数据结构实验名称二叉树的建立及遍历第页专业班级学号姓名实验日期：年月日评分一、实验目的1．学会实现二叉树结点结构和对二叉树的基本操作。2．掌握对二叉树每种操作的具体实现，学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。二、实验要求1．认真阅读和掌握和本实验相关的教材内容。2．编写完整程序完成下面的实验内容并上机运行。3．整理并上交实验报告。三、实验内容1．编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历并计算出二叉树的高度。2.编写程序生成下面所示的二叉树，并采用先序遍历的非递归算法对此二叉树进

2、行遍历。四、实验步骤（描述实验步骤及中间的结果或现象。在实验中做了什么事情，怎么做的，发生的现象和中间结果）第一题#include"stdafx.h"#include"iostream.h"#include"stdlib.h"#include"stdio.h"#includeusingnamespacestd;#defineNULL0#defineOK1#defineOVERFLOW-1typedefintStatus;typedefstructnode{chardata;structnode*lchild;structnode*rchild;}*bitree;intk=0;in

3、tdepth(bitreeT)//树的高度{if(!T)return0;else{intm=depth(T->lchild);intn=depth(T->rchild);return(m>n?m:n)+1;}}//先序，中序建树structnode*create(char*pre,char*ord,intn){structnode*T;intm;T=NULL;if(n<=0){returnNULL;}else{m=0;T=new(structnode);T->data=*pre;T->lchild=T->rchild=NULL;while(ord[m]!=*pre)m++;T->lchild=

4、create(pre+1,ord,m);T->rchild=create(pre+m+1,ord+m+1,n-m-1);returnT;}}//中序递归遍历voidinorder(structnode*T){if(!T)return;else{inorder(T->lchild);cout<data;inorder(T->rchild);}}voidinpre(structnode*T){if(!T)return;else{cout<data;inpre(T->lchild);inpre(T->rchild);}}voidpostorder(structnode*T){if(!

5、T)return;else{postorder(T->lchild);postorder(T->rchild);cout<data;}}//先序非递归遍历voidinpre1(structnode*T){structnode*p;structnode*stack[20];inttop=0;p=T;cout<<"非递归先序";while(p

6、

7、top!=0){while(p){stack[top++]=p;cout<data;p=p->lchild;}p=stack[--top];p=p->rchild;}}//中序非递归遍历voidinorder1(structnode*T){

8、structnode*p;structnode*stack[20];inttop=0;p=T;cout<<"非递归中序";while(p

9、

10、top!=0){while(p){stack[top++]=p;p=p->lchild;}p=stack[--top];cout<data;p=p->rchild;}}//主函数intmain(){bitreeT;charpre[30],ord[30];intn,m;gets(pre);gets(ord);n=strlen(pre);T=create(pre,ord,n);inpre(T);cout<

11、