数据结构-实验四-二叉树的基本操作学习资料.docx

《数据结构-实验四-二叉树的基本操作学习资料.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构-实验四-二叉树的基本操作精品文档 实验四二叉树的基本操作一、实验目的：   （1）掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法；  （2）掌握二叉树的遍历算法（先序、中序、后序遍历算法）的思想；  （3）掌握二叉树和叶子数、深度之间的关系及联系。二、实验内容：  构造二叉树，再实现二叉树的先序、中序、后序遍历，最后统计二叉树的叶子数和深度。三、实验步骤：  (一)需求分析   1.二叉树的建立首先要建立一个二叉链表的结构体，包含根节点和左右子树。因为树的每一个左右子树又是一颗二叉树，所以用递归的方法来建立其左右子树。二叉树的遍历是一种把二叉树的每一个

2、节点访问并输出的过程，遍历时根结点与左右孩子的输出顺序构成了不同的遍历方法，这个过程需要按照不同的遍历的方法，先输出根结点还是先输出左右孩子，可以用选择语句来实现。  2．程序的执行命令为：   1）构造结点类型，然后创建二叉树。  2）根据提示，从键盘输入各个结点。   3）通过选择一种方式（先序、中序或者后序）遍历。  4）输出结果，结束。  (二)概要设计   1.二叉树的二叉链表结点存储类型定义 收集于网络，如有侵权请联系管理员删除精品文档   typedefstructNode{     DataTypedata;     structNode*LChild; 

3、    structNode*RChild;    }BitNode,*BitTree;     2.建立如下图所示二叉树：       3.本程序包含六个模块    1)主程序模块     2)先序遍历模块    3)中序遍历模块    4)后序遍历模块收集于网络，如有侵权请联系管理员删除精品文档    5）叶子数模块    6）深度模块 四、测试结果    1.进入演示程序后的显示主界面：    请输入二叉树中的元素；    先序、中序、后序遍历和叶子数、深度分别输出结果。    2.测试结果    以扩展先序遍历序列输入，其中#代表空子树：ABC##DE#G##F#

4、##    先序遍历序列为：ABCDEGF     中序遍历序列为：CBEGDFA     后序遍历序列为：CGEFDBA    此二叉树的叶子数为：3    此二叉树的深度为：5    3.程序运行结果截图：收集于网络，如有侵权请联系管理员删除精品文档五、源代码#include#include//节点声明，数据域、左孩子指针、右孩子指针typedefstructBiTNode{  chardata;  structBiTNode*lchild,*rchild;}BiTNode,*BiTree;       //先序建立二叉树收集于网络，如有侵权请联系管理员删除精品文档B

5、iTreeCreateBiTree(){  charch;BiTreeT;  scanf("%c",&ch);  if(ch=='#')T=NULL;  else{    T=(BiTree)malloc(sizeof(BiTNode));    T->data=ch;    T->lchild=CreateBiTree();    T->rchild=CreateBiTree();  }  returnT;//返回根节点}//先序遍历voidPreOrderTraverse(BiTreeT){  if(T){    printf("%c",T->data);    Pr

6、eOrderTraverse(T->lchild);    PreOrderTraverse(T->rchild);  }} //中序遍历voidInOrderTraverse(BiTreeT){  if(T){    InOrderTraverse(T->lchild);    printf("%c",T->data);    InOrderTraverse(T->rchild);  }}收集于网络，如有侵权请联系管理员删除精品文档//后序遍历voidPostOrderTraverse(BiTreeT){  if(T){    PostOrderTraverse(T->

7、lchild);    PostOrderTraverse(T->rchild);    printf("%c",T->data);  }}//求二叉树的深度intDepth(BiTreeT)  {intdep=0,depl,depr;if(!T)dep=0;else{depl=Depth(T->lchild);depr=Depth(T->rchild);dep=1+(depl>depr?depl:depr);}returndep;}//计算叶子节点数intleef(BiTreeT){if(!T)return0;elseif(