实验四-二叉树子系统

韶韶 关关 学学 院院 学学 生生 实实 验验 报报 告告 册册 实验课程名称 数据结构与算法实验课程名称 数据结构与算法 实验项目名称 实验四实验项目名称 实验四 二叉树子系统二叉树子系统 实验类型 打实验类型 打 基础 基础 综合 综合 设计 设计 院院 系 计算机科学学院系 计算机科学学院 专专 业 计算机科学技术业 计算机科学技术 姓姓 名 名 学学 号 号 指导老师 陈正铭指导老师 陈正铭 韶关学院教务处编制韶关学院教务处编制 一 实验预习报告内容一 实验预习报告内容 预习日期 预习日期 2011 年年 9 月月 18 日日 实验目的 1 掌握二叉树的特点及其存储的方式 2 掌握二叉树的创建和显示方法 3 复习二叉树遍历的概念 掌握二叉树遍历的方法 4 掌握求二叉树的叶结点数 总结点数和深度等算法 实验内容实验内容 1 1 按屏幕提示用前序方法建立一棵二叉树 并能按凹入法显示二叉树结构 按屏幕提示用前序方法建立一棵二叉树 并能按凹入法显示二叉树结构 2 2 编写前序遍历 中序遍历 后序遍历 层次遍历程序 编写前序遍历 中序遍历 后序遍历 层次遍历程序 3 3 编写求二叉树的叶结点数 总结点数和深度的程序 编写求二叉树的叶结点数 总结点数和深度的程序 4 4 设计一个选择式菜单 以菜单方式选择下列操作 设计一个选择式菜单 以菜单方式选择下列操作 二二 叉叉 树树 子子 系系 统统 1 1 建建 二二 叉叉 树树 2 2 凹凹 入入 显显 示示 3 3 先先 序序 遍遍 历历 4 4 中中 序序 遍遍 历历 5 5 后后 序序 遍遍 历历 6 6 层层 次次 遍遍 历历 7 7 求求 叶叶 子子 数数 8 8 求求 结结 点点 数数 9 9 求求 树树 深深 度度 0 0 返返 回回 请选择菜单号请选择菜单号 三 实验报告内容三 实验报告内容 2011年年 9 月月 21 日日 实验程序主要代码 include define TREEMAX 100 typedef struct BT 定义二叉树结构体 char data BT lchild BT rchild BT BT CreateTree void ShowTree BT T void Preorder BT T void Postorder BT T void Levelorder BT T void Inorder BT T void Leafnum BT T void Nodenum BT T int TreeDepth BT T int count 0 定义计算结点个数的变量 void main BT T NULL char ch1 ch2 a ch1 y while ch1 y ch1 Y printf n printf n t t 二叉树子系统 printf n t t printf n t t 1 建 二 叉 树 printf n t t 2 凹 入 显 示 printf n t t 3 先 序 遍 历 printf n t t 4 中 序 遍 历 printf n t t 5 后 序 遍 历 printf n t t 6 层 次 遍 历 printf n t t 7 求 叶 子 数 printf n t t 8 求 结 点 数 printf n t t 9 求 树 深 度 printf n t t 0 返 回 printf n t t printf n t t 请选择菜单号 0 9 scanf c getchar printf n switch ch2 case 1 printf n t t 请按先序序列输入二叉树的结点 n printf n t t 说明 输入结点 0 表示后继结点为空 后按回车 n printf n t t 请输入根结点 T CreateTree printf n t t 二叉树成功建立 n break case 2 ShowTree T break case 3 printf n t t 该二叉树的先序遍历序列为 Preorder T break case 4 printf n t t 该二叉树的中序遍历序列为 Inorder T break case 5 printf n t t 该二叉树的后序遍历序列为 Postorder T break case 6 printf n t t 该二叉树的层次遍历序列为 Levelorder T break case 7 count 0 Leafnum T printf n t t 该二叉树有 d 个叶子 n count break case 8 count 0 Nodenum T printf n t t 该二叉树总共有 d 个结点 n count break case 9 printf n t t 该树的深度是 d TreeDepth T break case 0 ch1 n break default printf n t t 请注意 输入有误 if ch2 0 printf n n t t 按回车键继续 按任意键返回主菜单 n a getchar if a xA getchar ch1 n BT CreateTree 建立二叉树 BT t char x scanf c getchar if x 0 t NULL else t new BT t data x printf n t t 请输入 c 结点的左子结点 t data t lchild CreateTree printf n t t 请输入 c 结点的右子结点 t data t rchild CreateTree return t void Preorder BT T 先序遍历 if T printf 3c T data Preorder T lchild Preorder T rchild void Inorder BT T 中序遍历 if T Inorder T lchild printf 3c T data Inorder T rchild void Postorder BT T 后序遍历 if T Postorder T lchild Postorder T rchild printf 3c T data void Levelorder BT T 层次遍历 int i j BT q 100 p p T if p NULL i 1 q i p j 2 while i j p q i printf 3c p data if p lchild NULL q j p lchild j if p rchild NULL q j p rchild j i void Leafnum BT T 求叶子数 if T if T lchild NULL Leafnum T lchild Leafnum T rchild void Nodenum BT T 求结点数 if T count Nodenum T lchild Nodenum T rchild int TreeDepth BT T 求树深度 int ldep rdep if T NULL return 0 else ldep TreeDepth T lchild rdep TreeDepth T rchild if ldep rdep return ldep 1 else return rdep 1 void ShowTree BT T 凹入法显示二叉树 BT stack TREEMAX p int level TREEMAX 2 top n i width 4 if T NULL printf n t t 凹入表示法 n t t top 1 stack top T level top 0 width while top 0 p stack top n level top 0 for i 1 idata for i n 1 irchild NULL top stack top p rchild level top 0 n width level top 1 2 if p lchild NULL top