二叉树的建立及遍历.doc

数据结构 实验五 课程 数据结构 实验名称 二叉树的建立及遍历 第 页专业 班级 学号 姓名 实验日期： 年 月 日 评分 一 、实验目的1学会实现二叉树结点结构和对二叉树的基本操作。2掌握对二叉树每种操作的具体实现，学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。二 、实验要求1认真阅读和掌握和本实验相关的教材内容。2编写完整程序完成下面的实验内容并上机运行。3整理并上交实验报告。 三、实验内容1编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历并计算出二叉树的高度。2 .编写程序生成下面所示的二叉树，并采用先序遍历的非递归算法对此二叉树进行遍历。 四、实验步骤（描述实验步骤及中间的结果或现象。在实验中做了什么事情，怎么做的，发生的现象和中间结果）第一题#include stdafx.h#includeiostream.h#includestdlib.h#includestdio.h#includeusing namespace std;#define NULL 0#define OK 1#define OVERFLOW -1typedef int Status;typedef struct node char data;struct node *lchild;struct node *rchild;*bitree;int k=0;int depth(bitree T)/树的高度 if(!T)return 0; else int m=depth(T-lchild); int n=depth(T-rchild); return (mn?m:n)+1; /先序，中序 建树struct node *create(char *pre,char *ord,int n)struct node * T;int m;T=NULL;if(ndata=*pre;T-lchild=T-rchild=NULL;while(ordm!=*pre)m+;T-lchild=create(pre+1,ord,m);T-rchild=create (pre+m+1,ord+m+1,n-m-1);return T;/中序递归遍历void inorder(struct node *T)if(!T)return;elseinorder(T-lchild );coutdata;inorder(T-rchild );void inpre(struct node *T)if(!T)return;elsecoutdata;inpre(T-lchild );inpre(T-rchild );void postorder(struct node *T)if(!T)return;elsepostorder (T-lchild );postorder (T-rchild );coutdata;/先序非递归遍历void inpre1(struct node *T)struct node *p;struct node *stack20;int top=0;p=T;cout非递归先序 ;while(p|top!=0)while (p)stacktop+=p;coutdata;p=p-lchild;p=stack-top;p=p-rchild ;/中序非递归遍历void inorder1(struct node *T)struct node *p;struct node *stack20;int top=0;p=T;coutlchild ;p=stack-top;coutdata;p=p-rchild ;/主函数int main()bitree T;char pre30,ord30;int n,m;gets(pre);gets(ord); n=strlen(pre);T=create(pre,ord,n);inpre(T);coutendl;postorder (T); coutendl;inorder(T); coutendl;inpre1(T);coutendl;inorder1(T); coutendl;m=depth(T);cout二叉树高度为：mendl;return 0;第二题：#include stdafx.h#includeiostream.h#includestdlib.h#includestdio.h#includeusing namespace std;#define NULL 0#define OK 1#define OVERFLOW -1typedef int Status;typedef struct node char data;struct node *lchild;struct node *rchild;*bitree;Status Create(bitree &T) /按先序次序输入二叉树中结点的值，!表示空树char e;cout输入树的元素：e; if(e=!) T=NULL;elseif(!(T=(node *)malloc(sizeof(node)exit (OVERFLOW);T-data=e;Create(T-lchild);Create(T-rchild);return OK;/先序非递归遍历void inpre(struct node *T)struct node *p;struct node *stack20;int top=0;p=T;cout非递归先序 ;while(p|top!=0)while (p)stacktop+=p;coutdata;p=p-lchild;p=stack-top;p=p-rchild ;/主函数int main()bitree T; Create(T);cout输出的元素为：endl;inpre(T);return 0;五 实验结果第一题：输入先序为 -+a*b%cd/ef输入后序为 a+b*c%d-e/f得出结果：输入先序为abcd输入后序为bacd得出结果：第二题： 六 实验总结1 为什么头文件只用#include using namespace std;不行，要把所写到的程序中所包含的头文件头写进去。于是就在想，反正以后不管这些头文件有没用到头写进去，省得一大堆麻烦。2 用先序建树的时候虽然只要输入一个字符串，但是要判断空树的情况。比较麻烦。我个人觉得用先序与中序联合建树比较简单。因为这样只要输入先序与中序就可以建树了。3 对于三种遍历的过程，要是用递归写的就根据书上所给出的遍历步骤做稍微的调整就好了。至于非递归的三种遍历，中序最为简单，用一个栈就可以完成了，思路是边进栈边收索左孩子，直到左孩子为空的时候才开始进行出栈输出再收索右孩子的操作。而非递归的先序遍历基本可以和中序一样，建立一个队列，在进栈的时候队列也进同样的元素，但是不与栈一起出栈。而是在最后进栈出栈结束的时候，对队列进行出队列操作即可。4 二叉树对于进行表达式的前缀，中缀和后缀的表示有明显的优势，既方便，又容易理解。其先序，中序和后序分别对应这表达式的前缀，中缀和后缀。5 在建树与进行树的遍历的时候一定要理解其建树与遍历的整个过程。不然就会连为什么这样做都不知道。在遍历树的时候最常用到的就是栈的结构了（非递归）。七：思考与提高1如何计算二叉链表存储的二叉树中度数为1的结点数？ 答：int countleaf(bitree t,int count)if(!(t-lchild) &(t-rchild) count+;by chance 碰巧；凑巧else if (t-lchild)&!(t-rchild)count+;countleaf(t-lchild);countleaf(t-rchild);lack vi. & vt. 缺乏；没有return count;range n. 种类；范围state vt. 陈述；说明musical adj. 音乐的；喜爱音乐的 2已知有棵以二叉链表存储的二叉树，root指向根结点，p指向二叉树中任一结点，如何求从根结点到p所指结点之间的路径?答：voi