二叉树的建立及遍历

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

2、遍历的非递归算法对此二叉树进行遍历。 四、实验步骤（描述实验步骤及中间的结果或现象。在实验中做了什么事情，怎么做的，发生的现象和中间结果）第一题#include "stdafx.h"#include"iostream.h"#include"stdlib.h"#include"stdio.h"#include<stack>using namespace std;#define NULL 0#define OK 1#define OVERFLOW -1typedef int Status;typedef s

3、truct 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 (m>n?m:n)+1; /先序，中序 建树struct node *create(char *pre,char *ord,int n)struct node * T;int m;T=NULL;if(n<=0)retur

4、n NULL;else m=0;T=new(struct node);T->data=*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 );cout<<T->data;inorder(T->

5、rchild );void inpre(struct node *T)if(!T)return;elsecout<<T->data;inpre(T->lchild );inpre(T->rchild );void postorder(struct node *T)if(!T)return;elsepostorder (T->lchild );postorder (T->rchild );cout<<T->data;/先序非递归遍历void inpre1(struct node *T)struct node *p;struct node

6、 *stack20;int top=0;p=T;cout<<"非递归先序 "while(p|top!=0)while (p)stacktop+=p;cout<<p->data;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;cout<<"非递归中序 "while(p|top!=0)while (p)sta

7、cktop+=p;p=p->lchild ;p=stack-top;cout<<p->data;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);cout<<endl;postorder (T); cout<<endl;inorder(T); cout<<endl;inpre1(T);cout<<endl;inorder

8、1(T); cout<<endl;m=depth(T);cout<<"二叉树高度为："<<m<<endl;return 0;第二题：#include "stdafx.h"#include"iostream.h"#include"stdlib.h"#include"stdio.h"#include<stack>using namespace std;#define NULL 0#define OK 1#define OVERFLOW -1

9、typedef int Status;typedef struct node char data;struct node *lchild;struct node *rchild;*bitree;Status Create(bitree &T) /按先序次序输入二叉树中结点的值，!表示空树char e;cout<<"输入树的元素："<<endl; cin>>e; if(e='!') T=NULL;elseif(!(T=(node *)malloc(sizeof(node)exit (OVERFLOW);T->d

10、ata=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;cout<<p->data;p=p->lchild;p=stack-top;p=p->rchild ;/主函数int main()bitree T; Cr

11、eate(T);cout<<"输出的元素为："<<endl;inpre(T);return 0;五 实验结果第一题：输入先序为 -+a*b%cd/ef输入后序为 a+b*c%d-e/f得出结果：输入先序为abcd输入后序为bacd得出结果：第二题： 六 实验总结1 为什么头文件只用#include <iostream> using namespace std;不行，要把所写到的程序中所包含的头文件头写进去。于是就在想，反正以后不管这些头文件有没用到头写进去，省得一大堆麻烦。2 用先序建树的时候虽然只要输入一个字符串，但是要判断空树的情况。

12、比较麻烦。我个人觉得用先序与中序联合建树比较简单。因为这样只要输入先序与中序就可以建树了。3 对于三种遍历的过程，要是用递归写的就根据书上所给出的遍历步骤做稍微的调整就好了。至于非递归的三种遍历，中序最为简单，用一个栈就可以完成了，思路是边进栈边收索左孩子，直到左孩子为空的时候才开始进行出栈输出再收索右孩子的操作。而非递归的先序遍历基本可以和中序一样，建立一个队列，在进栈的时候队列也进同样的元素，但是不与栈一起出栈。而是在最后进栈出栈结束的时候，对队列进行出队列操作即可。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);countl