实验报告2栈和队列

《实验报告2栈和队列》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数学与计算机科学系实验报告课程：数据结构地点：软件实验室一时间：2012年12月7日学生姓名韩玉班级11计本2班学号110312241成绩组别第二组同组姓名徐小凤钱学钦王汉平吴卓俊方朔刘振亮学号48,15,21，24,05，14实验项目树和二叉树指导教师帅小应实验目的掌握树的基本操作实验要求实现树的初始化实现树的遍历操作统计树的节点数和深度实验环境硬件：计算机软件：windowsXP,C实验内容及实验结果请写出具体的实验步骤，并给出相应的实验结果，附上编写的程序及其运行结果截图!!一.程序代码如下

2、：#include#include#includeintcount=0,high=0，hl=0，h2=0;structnode{chardata;node*leftChild;node*rigthChild;}；typedefnode*BTree;intInit(BTree&bt){bt=(BTree)malloc(sizeof(node));if(bt==0)return0;bt=NULL;return1;}//DLRcreatetr

3、ee//建立二叉树voidCreate(BTree&btr){charch;cin»ch;if(ch==,#t){btr=NULL;return;}else{btr=(BTree)malloc(sizeof(node));btr->data=ch;Create(btr->leftChild);Create(btr->rigthChild);}}//outputtreeDLR二叉树先序遍历voidPreOrder_DLR(BTree&root){if(root!=NULL)cout«root->da

4、ta;PreOrder_DLR(root->leftChild);PreOrder_DLR(root->rigthChild);}}//outputtreeLDR二叉树中序遍历voidmidOrder_LDR(BTree&root){if(root!=NULL){midOrder_LDR(root->leftChild);cout«root->data;midOrder_LDR(root->rigthChild);}}//outputtreeLRD二叉树后序遍历voidlastOrder_LRD(

5、BTree&root){if(root!=NULL){lastOrder一LRD(root->leftChild);lastOrder一LRD(root->rigthChild);cout«root->data;}}//计算二叉树结点数intTravjeaf(BTreeroot){if(root!=NULL){if(root->leftChild==NULL&&root->rigthChild==NULL)count++;Trav_leaf(root->leftChild);Trav_leaf(r

6、oot->rigthChild);}elsereturncount;}intPostTreeDepth(BTreebt){if(bt!=NULL){hl=PostTreeDepth(bt->leftChild);h2=PostTreeDepth(bt->rigthChild);high=(hl>=h2)?hl:h2;return(high+1);elsereturn0;}//主函数intmain(){BTreebt;cout<<"成功创建二叉树！"«endl;Create(bt);cout«"DL

7、R:’’；PreOrder_DLR(bt);cout«endl;cout<<’’LDRmidOrder_LDR(bt);cout«endl;cout«’’LRD:lastOrder_LRD(bt);cout«endl;intgetcout=Trav_leaf(bt);cout«’’叶结点数：”《getcout«endl;cout«"树的深度:1*«PostTreeDepth(bt)«endl;cout«nhigh=H«high«nhl=M«hl«nh2="«h2«endl;return0;}二.实

8、验结果•C:UsersAdministratorDesktopDebug儀二粗.exe’成功创建二叉树？DLR:12435LDR=42153技术原理：1.建立一个二叉树，利用递归的方法实现对该二叉树的遍历，并输出遍历结果。.2.叶子结点就是度为0的结点就是没有孩子结点的结点3.从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加1。实验步骤：1.建立一个二叉树