数据结构二叉树基本操作的编程实现.doc

数据结构（2013）实验报告05 班级号:T 学生姓名: 实验方式:上机操作 成绩: 教师批阅处： 【实验名称】 二叉树基本操作的编程实现 【实验目的】 内容：二叉树基本操作的编程实现 要求： 二叉树基本操作的编程实现，掌握二叉树的建立、遍历、插入、删除等基本操作的编程实现，存储结构主要采用链接结构。 【实验分析】 本次实验同上次实验一样，由于时间比较紧急，实验内容有比较多，并且这节课程也上的比较急，所以老师就给了一部分源代码，然后实验过程中根据所给的代码和功能要求，修改和完善程序功能。这次实验主要是以二叉树为主，练习和掌握二叉树的相关操作。 【程序运行主界面】 由于老师给了大部分代码，为了练习和提高自己的阅读程序的能力，将程序函数的整体框架以框图形式表示出来。 【程序函数亮点】 用到的类： 、结点类——class node，由于二叉树是由每一个点构成的，所以构造一个结点类来管理。此处类中具体有二叉树中的数据、二叉树结点的深度、左儿子、右儿子、父亲节点、用单链表处理所有结点时指向下一个结点等。 具体形式如下： class node { friend class btree;//二叉树类的友元类 public: node(char initdata=0,int initdeep=0,node *initl=NULL,node *initr=NULL, Node *initf=NULL,node *initn=NULL); ~node() {}; protected: char data; //二叉树结点中的数据，此处定义为字符 int deep; //设置二叉树结点的深度 node *lchild; //左儿子 node *rchild; //右儿子 node *father; //父亲结点 node *next; }; 、二叉树类——class btree，这个类中功能很多。对一般而言，就有常规的查找、插入、删除等功能块。但这里最主要的是遍历，并且遍历又分为很多种。具体的遍历种类有：递归先根遍历、递归中根遍历、递归后根遍历、非递归先根遍历、非递归中根遍历、非递归后根遍历、层次遍历。 class btree //创建一个二叉树类 { private: char btreedata[Maxsize]; //广义表字符数组 char answer; //用于回答菜单选项 node *root; //指向根结点位置的指针 node *workinp,*linkrear; //定义一个工作指针，尾部指针 int btreecount; //结点个数计数器 bool firstbracket; //显示广义表时处理第一个括号，为1是，变成0就不是了 int countnow; //每一次需要使用计数器时临时保存该值 int leafcount; int countall; int sondeep; //创建儿子结点时保存当前深度 void visit(node *searchp); //访问当前结点数据域 void showbtreedata(); //在主界面中显示当前工作数组 int rgetcount(node *searchp); //递归统计二叉树中的结点个数 int getcount(); //记录二叉树中的结点个数 returninfo changeworkinpp(); //将工作指针指向左儿子、右儿子或者父亲 returninfo findnode(); //查找结点 returninfo addchild(); //增加左儿子或者右儿子 returninfo deletenode(); //删除结点 returninfo getinformation(); //获取二叉树结点和叶子信息 returninfo gliststravel(node *searchp);//以广义表glists表示法输出二叉树 public: btree(node *initrootp); btree() { root=NULL; firstbracket=1; countall=0; //递归函数内部统计结点个数 btreecount=0;