二叉树实验报告

一、实验目的1.掌握树的基本概念、二叉树的基本操作；2.重点掌握二叉树的生成、遍历及求深度等算法；3.掌握赫夫曼树的含义及其应用。二、实验内容1.编写程序实现二叉树的前序遍历的算法【问题描述】前序遍历的方式是每遍历到一个结点就立刻处理结点。便利的顺序是先向着树的左方走直到无法前进后，才转往右方走。【基本要求】首先穿火箭二叉树，然后编写前序遍历函数，最后编写主函数。【测试数据】如图3-1所示二叉树的前序遍历结果为：1,2,4,5,3,6。2.编写程序实现二叉树的后序遍历的算法【问题描述】后序遍历的方式刚好和前序遍历的方式相反，他是等到结点的两个子结点都遍历过后才运行处理。【基本要求】首先创建二叉树，然后编写后序遍历的函数，最后编写主函数。【测试数据】如图3-1所示二叉树的后续遍历结果为：4,5,2,6,3,1。三、实验步骤根据例题基本操作写好源程序，基本操作在例题中基本给出，写出主函数，调试分析程序，找出错误，并修改后程序能够运行，并且得出正确的输出。1.二叉树的前序遍历代码/*-------二叉树先序遍历------*/#includestdlib.hstructtree{intdata;structtree*left;structtree*right;};typedefstructtreetreenode;typedefstructtree*btree;btreeinsertnode(btreeroot,intvalue){btreenewnode;btreecurrent;btreeback;newnode=(btree)malloc(sizeof(treenode));newnode-data=value;newnode-left=NULL;newnode-right=NULL;if(root==NULL){returnnewnode;}else{current=root;while(current!=NULL){back=current;if(current-datavalue)current=current-left;elsecurrent=current-right;}if(back-datavalue)back-left=newnode;elseback-right=newnode;}returnroot;}btreecreatebtree(int*data,intlen){btreeroot=NULL;inti;for(i=0;ilen;i++)root=insertnode(root,data[i]);returnroot;}voidpreorder(btreeptr){if(ptr!=NULL){printf([%2d]\n,ptr-data);preorder(ptr-left);preorder(ptr-right);}}voidmain(){btreeroot=NULL;intdata[9]={5,6,4,8,2,3,7,1,9};root=createbtree(data,9);printf(outputthebtree:\n);preorder(root);}2.二叉树的后序遍历代码/*-------二叉树后序遍历------*/#includestdlib.hstructtree{intdata;structtree*left;structtree*right;};typedefstructtreetreenode;typedefstructtree*btree;btreeinsertnode(btreeroot,intvalue){btreenewnode;btreecurrent;btreeback;newnode=(btree)malloc(sizeof(treenode));newnode-data=value;newnode-left=NULL;newnode-right=NULL;if(root==NULL){returnnewnode;}else{current=root;while(current!=NULL){back=current;if(current-datavalue)current=current-left;elsecurrent=current-right;}if(back-datavalue)back-left=newnode;elseback-right=newnode;}returnroot;}btreecreatebtree(int*data,intlen){btreeroot=NULL;inti;for(i=0;ilen;i++)root=insertnode(root,data[i]);returnroot;}voidpostorder(btreeptr){if(ptr!=NULL){postorder(ptr-left);postorder(ptr-right);printf([%2d]\n,ptr-data);}}voidmain(){btreeroot=NULL;intdata[9]={5,6,4,8,2,3,7,1,9};root=createbtree(data,9);printf(outputthebtree:\n);postorder(root);}四、实验结果分析1.二叉树的前序遍历运行结果2.二叉树的后序遍历运行结果五、实验总结做实验贵在坚持，这是通过这次试验我感受最为深刻的。其次，我了解到，树形结构是一类重要的非线性数据结构。其中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构。二叉树是另一种树形结构，它的特点是每个节点至多只有两棵子树（即二叉树不存在度大于2的节点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。还有，在这次实验中我了解到，3种遍历算法之不同之处仅在于访问根节点和遍历左、右子树的先后关系。如果在算法中暂且抹去和递归无关的Visit语句，则三个遍历算法完全相同。由此，从递归执行过程的角度来看先序、中序和后序遍历也是完全相同的。