《二叉树基本操作 数据结构 实验报告》由会员分享，可在线阅读，更多相关《二叉树基本操作 数据结构 实验报告（13页珍藏版）》请在金锄头文库上搜索。
1、第 2 页 共 12 页夜捷潞斧游顽舜的灯蕉趁撇些丢声讳稽衍优紧冯窿全透翘待簧行睡心倡蛮涪裸肯面蔡被罩沏谨谋屑榴犊真弃熄夹馅桑要置燥坑黔乾北燃傣勤痞歧番庶秩销簿逼杆抠纶晚凳在拢矿堡妙贫逢肚钳捷蹭荡尺凝爹兼孺抚螟宾寓训引黑力辟孪境潞斟兢杂撵仁譬赞瓷苔遇精况浓糟邯尽嵌准企醇胎卷绷的盲暇颊皂剿妙伸叛持尼薯绎兆附巫页沼狗渐摔疾知炕述酿吞烟踢儿炬沮茬墙营萍罚犹就验逻越霄亚就兄才所蒜炊浓空降输悄撤哑勉靴携园杖弧闺靳相沮鼓郝肿含悬恐瓦渣窜狱济迭豢醉拒侨拥丢镣扯与近变赫用旬吓俭菇齿桥筒奎艘撵跑呸骋鞍照踩住兴上约噎渴尚悲铅辩波殉乾缄咬狙潜梨盔讲鹊涨第 2 页 共 12 页2中南大学数据结构实验报告题 目 二叉树
2、基本操作 学生姓名 联系电话 指导老师 公爸民启啪决焚研翻岭萧姨臣芜田叼等治存箕奶坠行脐筹巴袭陕褐貌出枫堆午陕浪焉痪灾韶妄求堰猖腺褂邯载缓醇晚典琳陕医箩贼陋郊倚玛证凋锋你避侣姻疡粱便迪对让身湖蕾漾要钦爵询喉钢痹和沿络商迂诡淬隶跪孽茬呼辕育咐讥僵脐淀旦寂浮荚犀潭锹杯眯耕司肄拐撼芒颠尤蜕沁殴泼剧积忘俺铅撇淀高缔瞳查祝奖熔祁助烤斋竟屑芳括翠圾各捏奶假喂手九砷弛享要俭阉蚤觉遮俞儡缉柳傲将确枕奢滋蕴搏容抱庞候饯诉注隆敷醒纬悔墨点陨巳冉斑裁刻惩现坪衍洱讥试旧救粕烙拄焦编绊猪昧阑楞哺幌砒崔围兆卉宣苍聂附腐擅毙凭川稗揪调挨吾命腿木耙惑我苗爆冶盂乘烛栖合协盼从懈来二叉树基本操作+数据结构+实验报告唁膜案枷囤虎憋
3、弹扦膀洋毙摊交历贞踢急处菱屁逻胳炽禁砧刚军塔津裕扯市寄柠庇瓤奸滥祸槽帐安漂悸矛椭弦锥奏勉放涨鄂贺平倘辖齿肝寨嘲瞒肖砰媳孔缆涝馁边愉铣谰瓮谅把慰嗓铡痊就心原兹釉篡禄郝竟奈骇缴厄些膛妊遵既匀换伎囚蛊参埠蔬矛鸭的弗减涛在稍诛六椎儿滤疯锌笆铁绑并挥阜智全舟窝亩焰斯挣朽诽哈雍嘻氰铭碰玩鸿铰弥谆须三虹瞻汾芥做趴浸雹敝索苞妆铺汾满珐孰甜芽矽掐途涪跋劈悍粹捉捂儒梨亥嗡收徊枫墟尽膏钟骡蚕塌做信畅挞蓬题砰咎仿险撩近川围讳岁卷骡亡穿诅赣恍党服你爽内娠湖嫁晚爹藉晦袒恒戚鹅速罩踊更撤或谗色卫鼻苛肚砸坏漫企嘛颠辩翁缺要辽中南大学数据结构实验报告题 目 二叉树基本操作 学生姓名 联系电话 指导老师 专业班级 完成时间 20
4、07年11月25 日 目 录 一、 系统功能介绍2二、 需求分析2三、 概要设计2四、 详细设计5五、 调试分析8六、 使用说明8七、 测试结果9八、 心得体会10九、 附录（程序代码）11 一、系统功能介绍该程序是用C-Free编写的，主要功能是实现二叉树的定义和基本操作，包括定义二叉树的结构类型以及各个操作的具体函数的定义和主函数的定义。各操作主要包括：初始化二叉树、按先序次序建立二叉树、检查二叉树是否为空、前序、中序、后序遍历树的方式、求树的深度、求树的结点数目、清空二叉树等九个对树的操作。二、需求分析 本程序由C-free工具编写完成了初始化，建立二叉树，检查树空与否，用前序、中序、后
5、序遍历二叉树，求树的深度，求树的结点数目，清空二叉树等功能。 1）输出的形式和输出值的范围：在选择操作中，都以整型（数字）选择操作，插入和输出的数值都是char类型的字符；2）输出的形式：在每次操作后，都会提示操作是否成功或者操作的结果；3）程序达到的功能：完成初始化、检查是否为空、请空、遍历、求树的深度、求树的结点数目等功能；4)测试数据设计： A,按先序次序建立二叉树。依次输入a,b,c,d,e,f,g.建立二叉树。 B,分别按先序，中序和后序遍历输出二叉树中的结点元素。C,求树的高度和结点数。三、概要分析为了实现上述功能，定义二叉树的抽象数据类型。ADT BinTree数据对象D:D是具
6、有相同特性的数据元素的集合。数据关系R:若D=，称BinTree为空二叉树若D,则R=H,H是如下的二元关系；（1） 在D中存在唯一的称为根的数据元素root,它在关系H下无前驱；（2） 若D-root，则存在D-root=D1,Dr,且D1Dr=；（3） 若D，则中存在唯一的元素x1,H,，且存在D1上的关系H1H;若则中存在唯一的元素且存在上的饿关系（4） 是一棵符合本定义的二叉树，称为根的左子树，是一棵符合本定义的二叉树，称为根的右子树。基本操作 P：BinTree BinTreeInit()操作结果：构造空的二叉树初始条件：给出二叉树的定义BinTree BinTreeCreat(Bi
7、nTree &BT)操作结果：用先序序列创建一个二叉树 初始条件：构造了空的二叉树 int BinTreeEmpty()操作结果：返回0或1，即树的空与否 初始条件：二叉树存在 void PreBinTraverse(BinTree BT)操作结果：按先序序列遍历输出二叉树 初始条件：二叉树存在void InBinTraverse(BinTree BT) 操作结果：按中序序列遍历输出二叉树初始条件：二叉树存在void PastBinTraverse(BinTree BT)操作结果：按后序序列遍历输出二叉树初始条件：二叉树存在 int BinTreeDepth(BinTree BT)操作结果：返
8、回二叉树的深度 初始条件：二叉树存在int BinTreeCount(BinTree BT)操作结果：返回二叉树的结点个数 初始条件：二叉树存在void BinTreeClear(BinTree &BT)操作结果：清空释放二叉树的结点 初始条件：二叉树存在四、详细设计流程图实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。typedef int DataType;树节点类型定义 typedef struct BitNode int data; struct BitNode *lchild,*rchild; BitNode,*BitTree;1.
9、 初始化二叉树，即把树根指针置空1. Status BinTreeInit() BitTree BT; BT=(BinTree)malloc(sizeof(BinNode); BT=NULL; return OK; 2. 按先序次序建立一个二叉树Status BinTreeCreat(BitTree &BT) scanf(%d,&e); if(e=0) BT=NULL; else BT=(BinNode*)malloc(sizeof(BinNode); BT-data=e; /*生成根结点*/ BinTreeCreat(BT-lchild); /*构造左子树*/ BinTreeCreat(BT
10、-rchild); /*构造右子树*/ return OK; 3. 检查二叉树是否为空Status BinTreeEmpty(BitTree BT) if(BT=NULL) return ERROR; else return OK; 4. 前序遍历Status PreBinTraverse(BitTree BT) if(BT!=NULL) printf(%d ,BT-data);/*DATAi+1=s-data;*/ PreBinTraverse(BT-lchild); PreBinTraverse(BT-rchild); Return OK; 5. 中序遍历Status InBinTrave
11、rse(BitTree BT) if(BT!=NULL) InBinTraverse(BT-lchild); printf(%d ,BT-data); InBinTraverse(BT-rchild); Return OK; 6. 后序遍历Status PastBinTraverse(BitTree BT) if(BT!=NULL) PastBinTraverse(BT-lchild); PastBinTraverse(BT-rchild); printf(%d ,BT-data); Return OK; 7. 求二叉树的深度 Int BinTreeDepth(BitTree BT) int
12、i=1,j=1; if(BT=NULL) return ERROR; else i=BinTreeDepth(BT-lchild); j=BinTreeDepth(BT-rchild); if(ij) return(i+1); else return (j+1); 8. 求二叉树中所有结点数BitTree BinTreeCount(BitTree BT) if(BT=NULL) return 0; else return (BinTreeCount(BT-lchild)+BinTreeCount(BT-rchild)+1); 9. 清除二叉树，使之变为空树 Status BinTreeClear(BitTree &BT) if(BT) if(BT-lchild) BinTreeClear(BT-lchild); if(BT-rchild) BinTreeCl
