广州大学学生实验报告
开课学院及实验室:计算机科学与工程实验 416B 室 2011 年 5 月 17
日
学院
计算机科学与
教育软件学院
年级、专
业、班
计算机大类 092 班 姓名 苏日昌 学号
0923010111
实验课程名称 数据结构 成绩
实验项目名称
实验二 树和二叉树的实现
指导
老师
一、实验目的
1、熟练掌握二叉树的二叉链表表示方法及二叉树遍历算法
2、根据哈夫曼算法创建哈夫曼树
二、使用仪器、器材
微机一台
操作系统:WinXP
编程软件:C++
三、实验内容及原理
1、设计一个程序,根据二叉树的先根序列和中根序列创建一棵用左右指针表示的二叉树
例如:先根序列为 ABDGCEF#, 中根序列为 DGBAECF# (#表示结束)。然后用程序构造一棵二叉
树。注意程序的通用性(也就是说上述只是一个例子,你的程序要接受两个序列(先根和中根序列),
然后构造相应的二叉树)。
2. 设计一个程序,把中缀表达式转换成一棵二叉树,然后通过后序遍历计算表达式的值
例如:中缀表达式为(a+b)*(c+d)# (#表示结束),将之转换成一棵二叉树,然后通过后序遍历计算表
达式的值,其中 abcd 都是确定的值。注意程序的通用性(也就是说上述只是一个例子,你的程序要接
受一个序列,然后构造相应的二叉树,最后通过后序遍历计算出值(注意不是根据中缀表达式计算出
值,而是通过后序遍历所构造出的二叉树计算出值))。
四、实验过程原始数据记录
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "BiTree.h"
#include "Stack.h"
int createtree1(TElemType *preorder,TElemType *inorder)
{
BiTree T;
InitBiTree(T);
int j=0,k=0,a=0;
TElemType *ch=new TElemType;
TElemType *p;
TElemType *i;
p=preorder;
i=inorder;
if(p[k]!=NULL)
{
while(p[k]!='#')
{
int s=0;
while(ch[s]!=NULL&&i[a]!=ch[s])
{
s++;
}
if(i[a]==ch[s])
{
ch[j++]=3;
a++;
}
else
{
if(i[a]!=p[k])
{
ch[j++]=p[k];
k++;
}
else
{
ch[j++]=p[k];
ch[j++]=3;
k++;
a++;
}
}
}
ch[j]=3;
printf("%s",ch);
CreateBiTree(T,ch);
printf("按后序序列输出:");
PostOrderTraverse(T,visit);
评论0