数据结构实验3

《数据结构》实验报告三学校：班级：学号：姓名：日期：2011.6.7程序名：作业二叉树的递归操作.cpp一、上机实验的问题和要求：要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。具体实现要求：1.基于先序遍历的构造算法：输入是二叉树的先序序列，但必须在其中加入虚结点以示空指针的位置。假设虚结点输入时用空格字符表示。2.用广义表表示所建二叉树。3.用凹入表表示所建二叉树。4.分别利用前序遍历、中序遍历、后序遍历所建二叉树。5.求二叉树结点总数，观察输出结果。6.求二叉树叶子总数，观察输出结果。7.交换各结点的左右子树，用广义表表示法显示新的二叉树。8.（★）二叉树采用链接存储结构，其根结点指针为T，设计一个算法对这棵二叉树的每个结点赋值：（注意要修改DataType类型）叶结点的值为3只有左孩子或右孩子的结点则其值分别等于左孩子或右孩子的值左、右孩子均有的结点，则其值等于左、右孩子结点的值之和用广义表表示法显示所建二叉树阅读理解建立Huffman树的算法，对该算法进行运行及调试。具体实现要求：1.调试并运行Huffman算法，验算《回家作业六》的第3题。2.（★）求Huffman树的带权路径长度WPL。二、程序设计的基本思想，原理和算法描述：（包括程序的结构，数据结构，输入/输出设计，符号名说明等）基本思想：对任意一棵二叉树，试将其所有节点的左、右子树交换。并将交换前、后不同的二叉树分别用前序、中序、和后序三种不同的方法进行遍历。基本原理：同基本线性表、特殊线性表相似，二叉树也有顺序和链式两种基本的存储结构。因此针对不同的存储结构，在实现左右子树交换的过程中方法会有不同。在程序实现过程中要求不同功能分别用单个的函数实现，其中按层遍历二叉树的函数用顺序方法实现，其他函数用链式方法实现。基本原理：（1）创建二叉树。（2）用三种不同的方法遍历交换左右子树前的二叉树。（3）交换二叉树中所有结点的左右子树。（4）用三种不同的方法遍历交换左右子树后的二叉树。三、源程序及注释：//要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等#includestdio.h#includestring.h#includemalloc.h#includestdlib.h#defineNULL0typedefcharDataType;typedefstructBinTNode{DataTypedata;structBinTNode*rchild,*lchild;}BinTNode,*BinTree;//创建二叉数voidCreate(BinTree*T){charch;if((ch=getchar())=='*')//输入'*'时该节点为空*T=NULL;else{*T=(BinTree)malloc(sizeof(BinTNode));(*T)-data=ch;Create(&(*T)-lchild);Create(&(*T)-rchild);}}//先序遍历二叉树voidPreOrder(BinTreeT){if(T){printf(%c,T-data);PreOrder(T-lchild);PreOrder(T-rchild);}}//中序遍历二叉树voidInOrder(BinTreeT){if(T){InOrder(T-lchild);printf(%c,T-data);InOrder(T-rchild);}}//后序遍历二叉树voidPostOrder(BinTreeT){if(T){PostOrder(T-lchild);PostOrder(T-rchild);printf(%c,T-data);}}//用广义表表示二叉树voidListPrint(BinTreeT){if(T){printf(%c,T-data);if(T-lchild!=NULL||T-rchild!=NULL){printf(();ListPrint(T-lchild);if(T-lchild!=NULL)printf(,);ListPrint(T-rchild);printf());}}}//用凹入表表示二叉树/*对于凹入表表示二叉树，其实就是把二叉树结点的深度表示出来*/voidDisplayPrint(BinTreeT,intlay){if(T){for(inti=0;ilay;i++)printf();printf(%c\n,T-data);DisplayPrint(T-lchild,lay+1);DisplayPrint(T-rchild,lay+1);}}//求结点的个数intNode(BinTreeT){intstaticN=0;if(T){Node(T-lchild);N++;Node(T-rchild);}returnN;}//求叶子的个数intLeaf(BinTreeT){intstaticL=0;if(T){Leaf(T-lchild);if(!(T-lchild||T-rchild))//没有左子树和右子树,就是叶子L++;Leaf(T-rchild);}returnL;}//交换左子树和右子树voidChange(BinTree*T){if(*T){BinTNode*temp;Change(&(*T)-lchild);Change(&(*T)-rchild);temp=(*T)-lchild;(*T)-lchild=(*T)-rchild;(*T)-rchild=temp;}}voidmain(){BinTreeT;printf(输入先序序列:);Create(&T);printf(输出先序遍历:);PreOrder(T);printf(\n);printf(输出中序遍历:);InOrder(T);printf(\n);printf(输出后序遍历:);PostOrder(T);printf(\n);printf(输出广义表表示法:);ListPrint(T);printf(\n);printf(输出凹入表表示法:\n);DisplayPrint(T,1);printf(结点的个数:nodes=%d\n,Node(T));printf(叶子的个数:leaves=%d\n,Leaf(T));Change(&T);printf(交换左右子树，并用广义表表示法:);ListPrint(T);printf(\n);}四、运行输出结果：五、调试和运行程序过程中产生的问题及采取的措施：有语法错误和打程序时的拼写错误，主要就是根据出错的地方进行单方面的调试。六、对算法的程序的讨论、分析，改进设想，其它经验教训：在算法实现上，从算法的效率看，非递归方法具有较好的时间效率，递归方法书写形式较为简捷，更为直观，一般具有较好的空间效率。在按要求访问树中某些结点的数据元素时，选择一种合适的访问顺序是有必要的。利用树对不同数据元素进行组合，在排序和某些特殊应用情景下是一种不错的选择。七、对实验方式、组织、设备、题目的意见和建议：对题目可以更加综合一下，与后面学到的图结合起来，那么它的作用会更大。