《《数据结构》实验报告(普本)-(二)1.docx》由会员分享，可在线阅读，更多相关《《数据结构》实验报告(普本)-(二)1.docx（6页珍藏版）》请在三一文库上搜索。
1、实验三课程名称：数据结构班级：完成日期：姓名：学号：指导教师：实验名称：二叉树的应用实验序号：实验成绩：一、实验目的及要求掌握二叉树的动态存储结构-二叉链表，掌握二叉树的三种遍历方法，会运用三种遍历的方 法求解有关问题。二、实验环境硬件：计算机软件：Microsoft Visual C+三、实验内容1 .以二叉链表作存储结构，建立一棵二叉树；2 .输出其先序、中序、后序遍历序列；3 .统计其叶子结点数；4 .求出它的深度。四、调试过程及实验结果d C ; Dacu*ents and Sett ingsdBini3t rat QTOebugTodeNun：0reat Bin_Tree ； Inp
2、ut preorder = abc de q f:M MJtfWKX - ltSM 号 elect WB w1:2：3：4：Preorder TraversalI order Trauersal Postorder trauersal PostlreeDepth,Node numbeij.Leaf nunbet* Level DepthExit梵 MK30tMlM 梵 MX M WE MM： W K MM 梵 M M 就 M M6DocuBents und S&ttincstAdMlaistcatqrDebuv. xeE ： Lbhie! 1 Dept li9 * Exil;KKK-JM M-
3、JK K-M M-K KM KJK X-KMJ434X M M MKMKM-KM44M1LFpint Bifi_tree Pre order- abcdegf J JC JM X J( K Ji8： Exit美1著：1(餐箕*不蕤过注注玉音*KM堇英MW * JtM薜MJf Meal. 2 = I order Trave rsal 3 = Postorder traversal 4： PnutTpfpDftptlij- Nndfl nuimh好f* I龄mF niumli笔肥 E * Level Vcptli B： Exit-* -ru fj一 1r- -m- ；j . 全拼 学;*C :Do
4、ctuient s andl Sett inc s Ada ini st r sit o r D ebug v eze*5 - Leuel Depth8- ExitX M MrM：= MHM KXJf JMHK MHM *，*甄* K * 剧出 JM4BinTree Depth=5 Bi nTi*eft Node nunhe=7 BinTree Leaf iniimhep=3 蕤MM MM S fi lect 注MX 注yN=XXX耳1： Freor4&r Traversal2： larder Traversal3： Pastorder tFdversaL4： Post!reeDepth,No
5、de numberLeaf numberS： Lsucl DepthQt ExitX*KXKXKXKXXKJItIKil，KWELeuePrlfit Bira_TFte 1 Abe def cfM MM s e lect NBtMKHNMKJiHJt，1 - Pre order Tiaueisal2 - lordei* Tiaueisal3 = Pos tojrder- Crduersal4 : PostTieeDepthj.Node number,Leaf numbei*5 : Level Depth R: ExitXMUJCBtMJCMiMXMHlCKMKMKMjXlCMltKM： X X
6、MJCJCM：_五、总结通过本次试验，我了解了二叉树的建立与运行过程，在这次试验中也遇到不少 困难，经过老师和同学的指导，最终完成本次试验，受益匪浅。六、附录(源程序清单)#include using namespace std;/定义树的结构typedef struct _binTreechar data;_binTree *lNode,*rNode;binTree;/创建二叉树void createT(binTree *&rootNode,binTree *tempNode)if(rootNode=NULL)rootNode=tempNode; return;elseif(rootNode
7、-data tempNode-data)createT(rootNode-lNode,tempNode);else if(rootNode-data data)createT(rootNode-rNode,tempNode);/ 已创建的数void printT(binTree *rootNode)if(rootNode=NULL)return ;elseprintT(rootNode-lNode);coutdatarNode);/ 先序遍历二叉树void preTraverse(binTree *rootNode)if(rootNode=NULL)return ;elsecoutdatalN
8、ode);printT(rootNode-rNode);/ 中序遍历二叉树void midTraverse(binTree *rootNode)if(rootNode=NULL)return ;elseprintT(rootNode-lNode);coutdatarNode);/ 后序遍历二叉树void lastTraverse(binTree *rootNode)if(rootNode=NULL)return ;elseprintT(rootNode-lNode);printT(rootNode-rNode);coutdatalNode)+nodeTotal(rootNode-rNode);
9、/ 计算二叉树的深度int treeDepth(binTree *rootNode)if(rootNode=NULL)return -1;elseint lH=treeDepth(rootNode-lNode);int rH=treeDepth(rootNode-rNode);if(lHrH)return lH+1;return rH+1;/ 计算叶子结点的个数int leafTotal(binTree *rootNode)if(rootNode=NULL)return 0;elseif(rootNode-lNode=NULL & rootNode-rNode=NULL)return 1; e
10、lseint lH=leafTotal(rootNode-lNode);int rH=leafTotal(rootNode-rNode);return rH+lH;int main()binTree *rootNode,*tNode;rootNode=NULL; tNode=NULL;char ch;cout 按照下面给出的顺序进行输入构建二叉树： endlF D B E A C JH K G I Lch;while(ch!=0)tNode=new binTree;tNode-data=ch; tNode-lNode=NULL; tNode-rNode=NULL;createT(rootNod
11、e,tNode);cinch;if(rootNode=NULL)coutTree is NULL.endl;elsecout 正常输出二叉树的各节点数据： ;printT(rootNode); coutendl;cout 先序遍历二叉树的各节点数据：;preTraverse(rootNode);coutendl;cout 中序遍历二叉树的各节点数据：;midTraverse(rootNode);coutendl;cout 后序遍历二叉树的各节点数据：;lastTraverse(rootNode); coutendl;cout 二叉树的深度为： treeDepth(rootNode)endl;cout 二叉树的结点的个数为： nodeTotal(rootNode)endl;cout 二叉树的叶子结点的个数为： leafTotal(rootNode)endl;return 0;