北邮数据结构第三次实验-实验报告

第1页数据结构实验报告实验名称：实验三——栈和队列学生姓名：班级：班内序号：学号：日期：1.实验要求1.1实验目的通过选择下面两个题目之一进行实现，掌握如下内容：掌握二叉树基本操作的实现方法了解赫夫曼树的思想和相关概念学习使用二叉树解决实际问题的能力1.2实验内容根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。二叉树的基本功能：1、二叉树的建立2、前序遍历二叉树3、中序遍历二叉树4、后序遍历二叉树5、按层序遍历二叉树6、求二叉树的深度7、求指定结点到根的路径8、二叉树的销毁9、其他：自定义操作编写测试main()函数测试线性表的正确性2.程序分析2.1二叉链表第2页2.2二叉树的二叉链表存储示意图2.3关键算法分析2.3.1算法1：voidcreate(BinodeT*&R,Tdata[],inti);[1]算法功能：创建一个二叉树[2]算法基本思想：通过构造函数创建一个二叉树，构造函数通过调用函数create()创建二叉树，关于函数create()的伪代码：1.定义根指针，输入节点储存的data，若输入“#”，则该节点为空；2.申请一个新节点，判断它的父结点是否不为空，如果不为空在判断其为左或者右孩子，并把地址付给父结点，把data写入。[3]算法空间、时间复杂度：O（n）[4]代码逻辑（可用伪代码描述）：if(data[i-1]!=0){R=newBinodeT;R-data=data[i-1];R-lch=R-rch=NULL;create(R-lch,data,2*i);create(R-rch,data,2*i+1);}2.3.2算法2：voidDestroy(BinodeT*R);[1]算法功能：二叉树的销毁[2]算法基本思想：采用后序遍历的方法，释放节点。[3]算法空间、时间复杂度：O(n)第3页[4]代码逻辑（可用伪代码描述）：if(R!=NULL){Destroy(R-lch);Destroy(R-rch);deleteR;}2.3.3算法3：voidpreorder(BinodeT*R);[1]算法功能：前序遍历二叉树[2]算法基本思想：设置递归边界条件：ifroot==null则停止递归；2打印起始节点的值，并先后在左子数右子数上递归调用打印函数[3]算法空间、时间复杂度：O（n)[4]代码逻辑（可用伪代码描述）：if(R!=NULL){coutR-data;preorder(R-lch);preorder(R-rch);}2.3.4算法4：voidInorder(BinodeT*R);[1]算法功能：中序遍历二叉树[2]算法基本思想：1.设置递归边界条件：ifroot==null则停止递归，2.递归遍历左子树3.打印根节点数据域内容4.递归遍历右子树[3]算法空间、时间复杂度：O（n)[4]代码逻辑（可用伪代码描述）：if(R!=NULL){Inorder(R-lch);coutR-data;Inorder(R-rch);}2.3.5算法5：voidPostorder(BinodeT*R);[1]算法功能：后序遍历二叉树[2]算法基本思想：1.设置递归边界条件：ifroot==null则停止递归2.递归遍历左子树3.递归遍历右子树4.访问根结点数据域[3]算法空间、时间复杂度：O（n)[4]代码逻辑（可用伪代码描述）：if(R!=NULL){Postorder(R-lch);Postorder(R-rch);coutR-data;}}2.3.6算法6：voidLevelorder(BinodeT*R);[1]算法功能：层序遍历二叉树[2]算法基本思想：1.队列Q及所需指针的定义和初始化2.如果二叉树非空，将根指针入队3.循环直到队列Q为空3.1q=队列Q的队头元素出队3.2访问节点q的数据域coutq-data;3.3若节点q存在左孩子，则将左孩子指针入队if(q-lchild!=NULL)Q[rear++]=q-lchild;3.4若节点q存在右孩子，则将右孩子指针入队if(q-rchild!=NULL)第4页[3]算法空间、时间复杂度：O（n)[4]代码逻辑（可用伪代码描述）：BinodeT*queue[10000];intf=0,r=0;if(R!=NULL)queue[++r]=R;while(f!=r){BinodeT*queue[++f];coutp-data;if(p-lch!=NULL)queue[++r]=p-lch;if(p-rch!=NULL)queue[++r]=p-rch;}2.3.7算法7：intDepth(BinodeT*R,intd);[1]算法功能：计算二叉树深度[2]算法基本思想：1.定义和初始化计数深度的参数2．如果根节点为空，return03．如果根节点为非空，递归调用自身的到叶子节点到根的路径长度，输出其中较大的作为树的深度[3]算法空间、时间复杂度：O（n)[4]代码逻辑（可用伪代码描述）：if(R==NULL)returnd;if((R-lch==NULL)&&(R-rch==NULL))returnd+1;else{intm=Depth(R-lch,d+1);intn=Depth(R-rch,d+1);returnnm?n:m;}2.3.8算法8：voidpath(BinodeT*root,charm);[1]算法功能：输出指定结点到根结点的路径[2]算法基本思想：代码：1.建立一个存储路径结点结构，定义和初始化结构体的数组2.当root不为空或top为0时，进入循环3.当此时root所指的节点的数据不为指定数据时，将root指向它的左孩子4.当此时root所指的节点的数据为指定数据时，访问其数据域并输出[3]算法空间、时间复杂度：O(n)[4]代码逻辑（可用伪代码描述）：BinodeT*stack[10000];BinodeT*s;inttag[10000];inttop=0;s=root;do{while(s!=NULL){top++;stack[top]=s;tag[top]=0;s=s-lch;}if(top0){if(tag[top]==1){if(stack[top]-data==m){cout路径：\t;for(inti=1;i=top;i++)coutstack[i]-data;break;}top--;}else{s=stack[top];if(top0){s=s-rch;tag[top]=1;}}}}while(s!=NULL||top!=0);}3.程序运行结果第5页第6页第7页4.总结1．本次实验内容相对基础，很多代码在书上都能找到，但是写程序的时候还是遇到了一些问题特别是在参数传递方面很容易出错，因为本次实验的很多算法都依靠递归来实现，递归具有代码简洁但理解不易的特点，特别是在参数传递方面，要通过作图等方式才能搞清楚整个递归过程。2.由于单单靠前序、中序、后者序都无法唯一确定的建立一个二叉树，所以课本上提供的算法是输入按一定规则补全后的二叉树，首先应该明白输入的规则，要不然程序运行也很容易出错。3.本程序多了两个计算结点的函数，本来最开始想编一个打印树的函数，可是发现定位光标的位置实在非常有难度，而且采用本程序的存储结构好像很难实现，只好作罢，但是还是很希望能有机会编出来。4.开始的时候也是写了按前序遍历创树的，用了简单的递归调用，但是发现输入会有许多不便。所以很希望可以按层输入，于是做了尝试，虽然代码可能写的不是很简单，但是终于实现了按层输入。在c++语言的编写中就应该使其有更好的实用性，并敢于尝试，不断改进。第8页附源代码：#includeiostreamusingnamespacestd;templateclassTstructBinode//节点结构{Tdata;//数据BinodeT*lch;//左孩子BinodeT*rch;//右孩子};templateclassTclassBitree//二叉树类{private:voidcreate(BinodeT*&R,Tdata[],inti);voidDestroy(BinodeT*R);public:BinodeT*root;Bitree(Tdata[]);Bitree(){};voidpreorder(BinodeT*R);voidInorder(BinodeT*R);voidPostorder(BinodeT*R);voidLevelorder(BinodeT*R);intDepth(BinodeT*R,intd);voidpath(BinodeT*root,charm);~Bitree();};templateclassTvoidBitreeT::create(BinodeT*&R,Tdata[],inti)//创建二叉树{if(data[i-1]!=0){R=newBinodeT;R-data=data[i-1];R-lch=R-rch=NULL;create(R-lch,data,2*i);create(R-rch,data,2*i+1);}}templateclassT第9页BitreeT::Bitree(Tdata[])//创建根节点{create(root,data,1);}templateclassTvoidBitreeT::preorder(BinodeT*R)//前序遍历二叉树{if(R!=NULL){coutR-data;preorder(R-lch);preorder(R-rch);}}templateclassTvoidBitreeT::Inorder(BinodeT*R)//中序遍历二叉树{if(R!=NULL){Inorder(R-lch);coutR-data;Inorder(R-rch);}}templateclassTvoidBitreeT::Postorder(BinodeT*R)//后序遍历二叉树{if(R!=NULL){Postorder(R-lch);Postorder(R-rch);coutR-data;}}templateclassTvoidBitreeT::Levelorder(BinodeT*R)//层序遍历二叉树{BinodeT*queue[10000];intf=0,r=0;第10页if(R!=NULL)queue[++r]=R;while(f!=r){BinodeT*p=queue[++f];coutp-data;if(p-lch!=NULL)queue[++r]=p-lch;if(p-rch!=NULL)queue[++r]=p-rch;}}templateclassTvoidBitreeT::Destroy(BinodeT*R)//销毁二叉树{if(R!=NULL){Destroy(R-lch);Destroy(R-rch);deleteR;}}templateclassTBitreeT::~Bitree()//析构函数，销毁根节点，释放内存{Destroy(root);}templateclassTintBitreeT::Depth(BinodeT*R,intd)//求深度{if(R==NULL)returnd;if((R-lch==NULL)&&(R-rch==NULL))returnd+1;else{intm=Depth(R-lch,d+1);intn=Depth(R-rch,d+1);returnnm?n:m;//选择最大深度返回}}第11页templatecla