二叉树各种基本运算与遍历算法.doc

数据结构与算法 实验报告 实验名称： 二叉树各种基本运算与遍历算法 班 级： 10软工转本1 姓 名： 季佳宾 学 号： 类 型： 综合 实验地点： 鹤琴404 日 期： 2012.11.15 一、实验目的： 理解二叉树的概念及其基本运算算法（这些算法包括二叉树的创建、节点访问、求二叉树的深度以及二叉树的先根遍历、中根遍历、后根遍历算法） 用c语言实现二叉树的基本运算算法和遍历算法。 调试程序，编译运行并用数据测试程序 熟悉c语言编程 二、实验环境： PC机一台（带有VS 6.0软件） 三、实验内容和要求： 1、用c语言实现二叉树的基本运算算法（包括二叉树的创建、节点访问、求二叉树的深度）； 2、用c语言实现二叉树的三种遍历算法（先根遍历、中根遍历、后根遍历），其中中根遍历算法用递归和非递归两种方式实现，加深理解栈在非递归实现中的应用； 3、调试程序，编译运行并用数据测试程序 四、实验步骤： （对实验步骤的说明应该能够保证根据该说明即可重复完整的实验内容，得到正确结果。） 对实现二叉树的基本运算算法以及遍历算法做分析，绘制算法流程图 设计二叉树的节点表示方法 2）设计和实现相关算法函数 2、在VS6.0环境下编译实现代码 1）编辑源程序，达到调试编译运行的目的 2）利用数据进行测试验证 五、实验结果与分析（含程序、数据记录及分析和实验总结等）： 实验7.1实现二叉树各种基本运算的算法，代码如下所示：#include?stdio.h#include?malloc.h#define?MaxSize?100typedef?char?ElemType;typedef?struct?node{?ElemType?data;?struct?node?*lchild;?struct?node?*rchild;}BTNode;void?CreateBTNode(BTNode?*b,char?*str){BTNode?*St[MaxSize],*p=NULL;int?top=-1,k,j=0;char?ch?;b=NULL;ch=str[j];while?(ch!=\0){switch(ch){case?(:top++;St[top]=p;k=1;break;case):top--;break;case?,:k=2;break;default:p=(BTNode?*)malloc(sizeof(BTNode));p-data=ch;p-lchild=p-rchild=NULL;if(b==NULL)b=p;else?{switch(k){case?1:St[top]-lchild=p;break;case?2:St[top]-rchild=p;break;}}}j++;ch=str[j];}}BTNode?*FindNode(BTNode?*b,ElemType?x){BTNode?*p;if(b==NULL)return?NULL;else?if(b-data==x)return?b;else?{p=FindNode(b-lchild,x);if(p!=NULL)return?p;else?return?FindNode(b-rchild,x);}}BTNode?*LchildNode(BTNode?*p){return?p-lchild;}BTNode?*RchildNode(BTNode?*p){return?p-rchild;}int?BTNodeDepth(BTNode?*b){int?lchilddep,rchilddep;if(b==NULL)return(0);else?{lchilddep=BTNodeDepth(b-lchild);rchilddep=BTNodeDepth(b-rchild);return?(lchilddeprchilddep)?(lchilddep+1):(rchilddep+1);}}void?DispBTNode(BTNode?*b){if(b!=NULL){printf(%c,b-data);if(b-lchild!=NULL||b-rchild!=NULL){printf(();DispBTNode(b-lchild);if(b-rchild!=NULL)printf(,);DispBTNode(b-rchild);printf());}}}int?BTWidth(BTNode