北信-实验三-二叉树.doc

实 　验 报 告
课程名称 ﻩ 数据结构 ﻩ 　
实验项目 二叉树的建立与遍历 　
实验仪器　 　 ＰC 　 　 　
系 　 　 别： 　 　　计算机科学与技术
班级\学号： 　计科0902/200
姓 　 名：　 　 　　 高锋 　 　 　
日 期： 　　
成 绩:　 　 　 　 　
指导老师 : 　 　 　张　仰　森　 　　 　
一、目的和要求：　
1、熟练掌握二叉树的定义、性质和存储结构；
2、熟练掌握二叉树的三种遍历和线索化以及遍历算法的各种描述形式；
3、学会编写实现树的各种操作的算法。
二、实验题目：　ﻫ二叉树的建立与遍历：掌握建立二叉树的方法，实现先序、中序、后序三种遍历（递归和非递归）算法;
三、源程序（递归和非递归遍历）
#inｃlude〈>
#includｅ〈>
＃ｄefｉnｅ　TRＵE 1
#definｅ ＦＡLＳE 0
//树节点结构体
tｙpedｅf strucｔ TNode{
cｈar　data；
ｓｔrｕct　ＴＮode ＊lｃ，＊rｃ；
｝*Trｅe；
/／栈结构体
typedef ｓｔrucｔ Ｓｔａcｋ{
Tree ＊tｏp，＊base;　 //元素为树节点指针的指针！
ｉnt stａｃksize;
｝stack；
／/栈的初始化
vｏid InitＳｔack（stａck ＆s)
｛
/／ ｐrintｆ（”iｎit\ｎ"）;
　　 =(Tｒee　＊）maｌloc(ｓizeｏｆ（ＴNode)*１００）;//初始化100个空间
if（！s。bａse）
　　 　 　｛
　　 　 　ｐｒinｔf("error!＼ｎ"）；
　　　　 　 retuｒn；
　 }
　 =；
　 =0;
｝
//压栈操作
ｖoid push（staｃk ＆ｓ,Ｔreｅ t)
{
　 　＊s．toｐ =　ｔ；
//　　 printｆ（”pｕsｈ %c\n"，(＊s．ｔoｐ）—>ｄata）;
　 ++； //栈顶指针+1
　 s．ｓtａcksize++;
｝
／/出栈操作
Tｒee ｐop（staｃk &s）
{
// 　 Ｔrｅe ＊p;
ｉf(＝=ｓ．bａｓe） //判断是否为空栈
ﻩ {
ﻩ 　 printf（"stａcｋ emｐty　erｒｏｒ!\n＂)；
　 　ｒｅｔｕrn NULL;
ﻩﻩ｝
s．sｔａcksiｚe－-;
／/ ｐ=s．top-１；
/／ 　 　printf（"pｏp %c＼n",（*p)－＞dａta)；
reｔurｎ ＊（-－ｓ。tｏp）; /／返回栈顶元素：树节点指针
｝
//获得栈顶元素
Ｔree geｔTｏp(stａck　＆s）
{
iｆ（