实验六二叉树实验报告

实验四 二叉树操作
班级：计算机班 姓名： 学号： 完成日期：2010
题目：定二叉树实现种约定遍历
实验目：
（1）掌握二叉树定义存储表示学会建立棵特定二叉树方法
（2）掌握二叉树遍历算法（先序中序序遍历算法）思想学会遍历算法递实现非递实现
二实验容：构造二叉树实现二叉树先序中序序遍历统计二叉树深度
三实验步骤：
() 需求分析
1 二叉树建立首先建立二叉链表结构体包含根节点左右子树树左右子树颗二叉树递方法建立左右子树二叉树遍历种二叉树节点访问输出程遍历时根结点左右孩子输出序构成遍历方法程需遍历方法先输出根结点先输出左右孩子选择语句实现
2．程序执行命令：
1）构造结点类型然创建二叉树
2）根提示键盘输入结点
3）通选择种方式（先序中序者序）遍历
4）输出结果结束
(二)概设计
1二叉树二叉链表结点存储类型定义
typedef struct Node
{
DataType data
struct Node *LChild
struct Node *RChild
}BitNode*BitTree
2建立图示二叉树：void CreatBiTree(BitTree *bt)扩展先序遍历序列创建二叉树果前树根置空否申请新节点
3程序包含四模块
1) 程序模块：
2)先序遍历模块
3)中序遍历模块
4)序遍历模块
4模块调关系：
程序模块
先序遍历模块
中序遍历模块
序遍历模块
（三）详细设计
1建立二叉树存储类型
构造二叉树
void CreatBiTree(BitTree *bt)扩展先序遍历序列创建二叉树果前树根置空否申请新节点
{
char ch
chgetchar()
if(ch＇＇)*btNULL
else
{
*bt(BitTree)malloc(sizeof(BitNode))申请段关该节点类型存储空间
(*bt)>datach 生成根结点
CreatBiTree(&((*bt)>LChild)) 构造左子树
CreatBiTree(&((*bt)>RChild)) 构造右子树
}
}
2 编程实现二叉树前序中序序遍历操作输出遍历序列
1）先序遍历二叉树递算法：
void PreOrder(BitTree root)
{
if (rootNULL)
{
Visit(root >data)
PreOrder(root >LChild) 递调核心
PreOrder(root >RChild)
}
}
2）中序遍历二叉树递算法：
void InOrder(BitTree root)
{
if (rootNULL)
{
InOrder(root >LChild)
Visit(root >data)
InOrder(root >RChild)
}
}
3）序遍历二叉树递算法：
void PostOrder(BitTree root)
{
if(rootNULL)
{
PostOrder(root >LChild)
PostOrder(root >RChild)
Visit(root >data)
}
}
4）计算二叉树深度算法：
int PostTreeDepth(BitTree bt) 求二叉树深度
{
int hlhrmax
if(btNULL)
{
hlPostTreeDepth(bt>LChild) 求左子树深度
hrPostTreeDepth(bt>RChild) 求右子树深度
maxhl>hrhlhr 左右子树深度较者
return(max+1) 返回树深度
}
else return(0) 果空树返回0
}
四调试分析测试结果
1 进入演示程序显示界面：
请输入二叉树中元素
先序中序序遍历分输出结果
2测试结果
扩展先序遍历序列输入中代表空子树：ABCDEGF…
先序遍历序列：ABCDEGF
中序遍历序列：CBEGDFA
序遍历序列：CGEFDBA
二叉树深度：5
3程序运行结果
1）输入二叉树中元素（扩展先序遍历序列输入中代表空子树）显示截图：

图
2）输出结果显示界面：

图二
4调试分析：
程序通分调先序遍历中序遍历序遍历函数二叉树中元素进行遍历整程序基满足实验求细节问题面存缺陷写字母会导致程序法运行需处理问题认真细致程序完善总会更加努力程序更完美

六实验总结
1 二叉树进行表达式前缀中缀缀表示明显优势方便容易理解先序中序序分应表达式前缀中缀缀
2 建树进行树遍历时候定理解建树遍历整程然会连什样做知道遍历树时候常栈结构（非递）
3次实验更加解哈夫曼树构造生成方法序结构存储哈夫曼树构树程信息进行编码译码感知模块程序设计程序设计中普遍性该实验证明通模块程序设计程序读写性明显加强
通次实验初步掌握二叉树结构特性种存储结构特点适范围掌握哈夫曼树定义思想初步掌握凹入法显示树程序树显示够完善缺点学中会断学学中注意改变






























附录
源程序清单
#include
#include
#include
#include
typedef int DataType
typedef struct Node 创建结点类型结构体
{
DataType data
struct Node *LChild
struct Node *RChild
}BitNode*BitTree
void CreatBiTree(BitTree *bt) 扩展先序遍历序列创建二叉树果前树根置空否申请新节点
{
char ch
chgetchar()
if(ch＇＇)*btNULL
else
{
*bt(BitTree)malloc(sizeof(BitNode))
(*bt)>datach
CreatBiTree(&((*bt)>LChild))
CreatBiTree(&((*bt)>RChild))
}
}
void visit(char ch)访问根节点
{
printf(cch)
}
void PreOrder(BitTree root) 先序遍历二叉树递算法
{
if (rootNULL)
{
Visit(root >data)
PreOrder(root >LChild)
PreOrder(root >RChild)
}
}
void InOrder(BitTree root) 中序遍历二叉树递算法

{
if (rootNULL)
{
InOrder(root >LChild)
Visit(root >data)
InOrder(root >RChild)
}
}
void PostOrder(BitTree root) 序遍历求二叉树递算法
{
if(rootNULL)
{
PostOrder(root >LChild)
PostOrder(root >RChild)
Visit(root >data)
}
}
int PostTreeDepth(BitTree bt) 求二叉树深度
{
int hlhrmax
if(btNULL)
{
hlPostTreeDepth(bt>LChild) 求左子树深度
hrPostTreeDepth(bt>RChild) 求右子树深度
maxhl>hrhlhr 左右子树深度较者
return(max+1) 返回树深度
}
else return(0) 果空树返回0
}
void main()
{ BitTree T
int h
int layer
int treeleaf
layer0
printf(请输入二叉树中元素(扩展先序遍历序列输入中代表空子树)＼n) CreatBiTree(&T)
printf(先序遍历序列)
PreOrder(T)
printf(＼n中序遍历序列)
InOrder(T)
printf(＼n序遍历序列)
PostOrder(T)
hPostTreeDepth(T)
printf(＼n)
printf(二叉树深度d＼nh)}
文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档