《二叉树的建立及遍历》由会员分享，可在线阅读，更多相关《二叉树的建立及遍历（9页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验五课程 数据结构 实验名称二叉树的建立及遍历 第 页专业 班级 学号姓名实验日期：年 月 日评分一、实验目的1. 学会实现二叉树结点结构和对二叉树的基本操作。2. 掌握对二叉树每种操作的具体实现，学会利用递归方法编写对二叉树 这种递归数据结构进行处理的算法。二、实验要求1. 认真阅读和掌握和本实验相关的教材内容。2. 编写完整程序完成下面的实验内容并上机运行。3. 整理并上交实验报告。三、实验内容1.编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采 用三种递归遍历算法（前序、中序、后序）对这棵二叉树进行遍历并计算出二叉树 的高度。2 .编写程序生成下面所示的二叉树，并采
2、用先序遍历的非递归算法对此二 叉树进行遍历。四、实验步骤（描述实验步骤及中间的结果或现象。在实验中做了什么事情，怎么做的，发生的现象和中 间结果）第一题#include stdafx.h#includeiostream.h#includestdlib.h#includestdioh#includeusing namespace std;#define NULL 0#define OK 1#define OVERFLOW -1typedef int Status;typedef struct nodechar data;struct node *lchild;struct node *rchil
3、d;*bitree;int k=0;int depth(bitree T)/树的高度if(!T)return 0;elseint 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=
4、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 );postord
5、er (T-rchild ); coutdata;/先序非递归遍历void inpre1(struct node *T)struct node *p;struct node *stack20; int top=0;P=T;cout非递归先序;while(plltop!=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
6、 ;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;inprel(T);coutendl;inorderl(T);coutendl;m=depth(T);cout二 叉树高度为：mendl;return 0;第二题：#include stdafx.h#in
7、cludeiostream.h#includestdlib.h#includestdio.h#includeusing namespace std;#define NULL 0#define OK 1#define OVERFLOW -1typedef int Status;typedef struct nodechar data;struct node *lchild;struct node *rchild;*bitree;Status Create(bitree &T) /按先序次序输入二叉树中结点的值，！表示空树 char e;cout输入树的元素：e;if(e=!) T=NULL;el
8、seif(!(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
9、T;Create(T);cout输出的元素为：ebueCpp-*a*b?：cd/efa+bczd-e/f-+ab?icd/efabcdzw+ef/-a+b*czd-e/F三三递归先J，-+a*bzcd/eF=三递归中序a+bc!d-eZF二叉树鬲度丸5Piess any key to continue输入先序为abcd输入后序为bacd得出结果:第二题:e C:PrograK FilesBicrosot Visual Studi腕入树的元素:的入树的元素；备入树的元素；,帆入树的元素：f恤入树的元素，焉入树的元素，断入树的元素，输入树的元素：t愉入树的元素：.府入树的元素：.M入树的元素：龄入
10、树的元素；.府入树的元素；鼠出的元悉为：曰三递归先序 IZaiBSPEg any key to continue_g C:XProgra* FilesMicrosoft Visual Studiof -Ct. -Ct. J7_. PH 6 PH PH .PH .PH .-Trr .mhh .-ttt .ITT .ITT .TTT !np 树34WWFWWW 入rr入入入入入入入入入入入E ! - E-E-E-L-L-E-r-r-L-L-L采为土 儿寿 的元先 富归 入出递u- e kcontinue六实验总结1为什么头文件只用#include using namespace std不行，要把所
11、 写到的程序中所包含的头文件头写进去。于是就在想，反正以后不管这些头文 件有没用到头写进去，省得一大堆麻烦。2用先序建树的时候虽然只要输入一个字符串，但是要判断空树的情况。比较麻 烦。我个人觉得用先序与中序联合建树比较简单。因为这样只要输入先序与中序 就可以建树了。3对于三种遍历的过程，要是用递归写的就根据书上所给出的遍历步骤做稍微的 调整就好了。至于非递归的三种遍历，中序最为简单，用一个栈就可以完成了， 思路是边进栈边收索左孩子，直到左孩子为空的时候才开始进行出栈输出再收索 右孩子的操作。而非递归的先序遍历基本可以和中序一样，建立一个队列，在进 栈的时候队列也进同样的元素，但是不与栈一起出栈
12、。而是在最后进栈出栈结束 的时候，对队列进行出队列操作即可。4二叉树对于进行表达式的前缀，中缀和后缀的表示有明显的优势，既方便，又 容易理解。其先序，中序和后序分别对应这表达式的前缀，中缀和后缀。5在建树与进行树的遍历的时候一定要理解其建树与遍历的整个过程。不然就会 连为什么这样做都不知道。在遍历树的时候最常用到的就是栈的结构了(非递 归)。七：思考与提高1.如何计算二叉链表存储的二叉树中度数为1的结点数？答：int countleaf(bitree t,int count)(if(!(t-lchild) &(t-rchild)count+;else if (t-lchild)&!(t-rchild)count+;countleaf(t-lchild);countleaf(t-rchild);return count;2.已知有一棵以二叉链表存储的二叉树，root指向根结点，p指向二叉树 中任一结点，如何求从根结点到p所指结点之间的路径？ 答：void foundp(bitree t)(if(t=p)(Push(s, t-data);Pop(s, t-data);foundp(t-lchild);foundp(t-rchid);
