数据结构实习报告二叉树.doc

数据结构课程设计实习报告 题 目：二叉链表的基本操作学 号：1210522姓 名：何厚华年 级：大二学 院：计算机与控制工程学院专 业：计算机科学与技术完成日期：2014年4月24日授课教师：辛运帏目录1.题目.22.要求 . . . . . . . . . . . . . . . . . . . . . . . . 23.程序实现 . . . . . . . . . . . . . . . . . . . . . 2 3.1程序运行及编译环境 . . . . . . . . . . . . . . . . 2 3.2程序描述 . . . . . . . . . . . . . . . . . 2 3.3实现功能 . . . . . . . . . . . . . . . . . . 2 3.3.1子功能模块1 . . . . . . . . . . . . . . . . . 3 3.3.1.1数据结构的定义 . . . . . . . . . . . . . . . 3 3.3.1.1.1全局数据结构 . . . . . . . . . . . . . . . 3 3.3.1.1.2局部数据结构 . . . . . . . . . . . . . . . 4 3.3.1.4算法及程序说明. . . . . . . . . . . . . . 4 3.3.1.5接口设计. . . . . . . . . . . . . . . . . . 6 3.3.2子功能模块2 . . . . . . . . . . . . . . . . . 7 3.3.3子功能模块3 . . . . . . . . . . . . . . . . . . . 8 3.3.4子功能模块4 . . . . . . . . . . . . . . . . . . . 9 3.3.5子功能模块5 . . . . . . . . . . . . . . . . . . . 103.4运行结果 . . . . . . . . . . . . . . . . . . . 123.5尚未解决的问题 . . . . . . . . . . . . . . . . . . 121.题目 二叉链表的基本操作2.要求设二叉树以二叉链表的形式保存，T为指向根结点的指针。试完成以下功能：1、建立二叉树：从键盘输入各结点的值，可参照二叉树的顺序存储方式。例如输入“a,b,c, ,d”表示结点a是根，b和c是a的两个孩子，b仅有右孩子d。2、统计T中叶结点的个数。3、统计T中度为2的结点的个数。4、求树T的高度。 5、判断T中是否有度为1的结点（即按照国外教材的定义，是否为满树）。3. 程序实现 3.1程序运行及编译环境程序是用Visual Studio 2008即VS9.0 编译的。可以在windows系列的操作系统上运行。 3.2程序描述该程序主要用于构造参考二叉链表的顺序存储结构。其流程如下：A).构造树控制台输入字符，依此构造二叉树的每一个节点B).输出这棵树的信息C).完成3.3实现功能Main BinTree bt;bt.CreateTree();/建树bt.GetInfo(bt.getRoot();/获取信息，包括度为0,1,2节点数等system(pause);return 0;3.3.1子功能模块1 /*函数原型：void Convert2Bin(int num,bool a,int& idx)；函数功能：把一个十进制数转化为二进制数参数含义：num：要转化的十进制数；bool a：为节省空间，采用bool型来存储二进制的每一位用idx表示*/void Convert2Bin(int num,bool a,int& idx)/把一个整数num转化为二进制的形式,存放在数组a里面，idx存放输出到数组的哪一项int i=0;bool temp;while(num1) /除2取余，得到逆序的二进制序列ai+=num%2;num/=2;ai=num;idx=i;for (int j=0;j1) /除2取余，得到逆序的二进制序列ai+=num%2;num/=2;ai=num;idx=i;for (int j=0;j(idx+1)/2;j+)/把逆序的变为正序的temp=aj;aj=aidx-j;aidx-j=temp;/*函数原型：void InsertOrder(int num,bool a,int& idx)；函数功能：由一个十进制数决定插入二叉树的顺序参数含义：num：要转化的十进制数；bool a：为节省空间，采用bool型来存储二进制的每一位用idx表示 如传入的num是9，则a=0,0，1则表示往左，左，右的顺序*/void InsertOrder(int num,bool a,int& idx)Convert2Bin(num,a,idx);for (int i=0;idat=Data;return;bool orderMAXSIZE;/orderMAXSIZE用来存放插入的顺序，则order=0,0，1则表示往左，左，右的顺序，count表示前多少位有效int count=0;InsertOrder(idx,order,count);/由序号得到插入的顺序root-height=count+2;/树高就是位数加1BinNode* binNode=new BinNode;/生成一个结点BinNode* temp=root;binNode-dat=Data;binNode-left=NULL;binNode-right=NULL;for (int i=0;iright;break;case false:temp=temp-left;break;default:coutError happened in inserting node.right=binNode:temp-left=binNode;/最后一步3.3.3子功能模块3void Traversal(BinNode* Root)/递归遍历if(Root)Traversal(Root-left);coutdat;Traversal(Root-right);3.3.4子功能模块4/*函数原型：void CreateTree()；函数功能：从控制台输入数据，然后构造一棵树附加说明：输入的字符串要以#结束，逗号分隔，如a,b,c,d#*/void CreateTree()cout请构造一颗二叉树：以#结束，例如a,b,c,d#left);GetInfo(Root-right);if (Root-left=NULL&Root-right=NULL)/度为0的节点Node0+;if (Root-left!=NULL&Root-right=NULL)|(Root-left=NULL&Root-right!=NULL)/度为1的节点Node1+;if (Root-left!=NULL&Root-right!=NULL)/度为2的节点Node2+;if(Root=root)/后序遍历，到达根节点时，完成遍历cout因为这是一个参考顺序存储的数据结构，所以最后一个结点的深度就是树的高度,所以树高为heightendl;cout度为2的结点数Node