数据结构线性表实验报告-胡志鹏.doc

数据结构实验报告 实验四 实验题目：二叉树子系统 指导老师：任姚鹏 专业班级：计算机科学与技术系1106班 　　 姓 名：胡志鹏 2011100642 2013年 5月15日 实验类型__验证__ 实验室_软件实验室一 二叉树子系统 需求分析 按提示用前序方法建立一棵二叉树，并能按凹入法显示二叉树结构，编写前序遍历、中序遍历、后序遍历、层次遍历程序。编写求二叉树的叶结点数、总结点数和深度的程序。设计一个选择式菜单，以菜单方式选择下列操作。 2.概要设计 （1）创建一颗二叉树如下图： （2）基本操作 InitTree(T) 操作结果：创造空树T CreateTree(); 初始条件：给出树的定义 操作结果：按definition构造树 ShowTree(BT *T); 初始条件：树T存在 操作结果：返回树的根 Preorder(BT *T); 操作结果：先序遍历 Inorder(BT *T); 操作结果：中序遍历 Postorder(BT *T); 操作结果：后序遍历 TreeDepth(BT *T); 初始条件：树T存在 操作结果：二叉树的深度 Leafnum(BT *T); 操作结果：二叉树的叶子结点数 Nodenum(BT *T); 操作结果：二叉树的结点数 3.详细设计 （1）二叉树的数据类型： typedef struct BT { char data; BT *lchild; BT *rchild; }BT; （2）主程序界面及操作说明 二 叉 树 子 系 统 ****************************************** * 1---------建 二 叉 树 * * 2---------凹 入 显 示 * * 3---------先 序 遍 历 * * 4---------中 序 遍 历 * * 5---------后 序 遍 历 * * 6---------层 次 遍 历 * * 7---------求 叶 子 数 * * 8---------求 结 点 数 * * 9---------求 树 深 度 * * 0---------返 回 * ****************************************** （3）二叉树的叶子结点数 void Leafnum(BT *T) { if(T) { if(T-lchild==NULLT-rchild==NULL) count++; Leafnum(T-lchild); Leafnum(T-rchild); } } （4）二叉树的深度 void Nodenum(BT *T) { if(T) { count++; Nodenum(T-lchild); Nodenum(T-rchild); } } （5）二叉树的结点数 int TreeDepth(B