数据结构实验四-树与二叉树.doc

实验四 树与二叉树 一、实验目的掌握树与二叉树的基本操作：建立树、遍历树、哈夫曼树等相关运算。二、实验要求包含有头文件和main函数；1. 格式正确，语句采用缩进格式； 2. 设计子函数实现题目要求的功能；3. 编译、连接通过，熟练使用命令键；4. 运行结果正确，输入输出有提示，格式美观。三、实验设备、材料和工具1. 奔腾2计算机或以上机型2. turboc2,win-tc四、实验内容和步骤实验内容：1. 分析程序。2. 完成程序编写和补充步骤：3. 确定数据的结构；4. 利用main函数调用各子函数；5. 调试、分析运行结果。五、实验报告要求1. 根据实验内容初步设计好程序，并从理论上排除错误；2. 针对程序的健壮性准备好测试数据；3. 结果分析中如实填写运行后的结果，记录调试过程中产生的重要问题和解决方法。六、根据实验过程填写下面内容基础部分1.构建bitree.h头文件。2.编写先序遍历、中序遍历、后序遍历函数，参照教材内容，写出一个完整程序验证二叉树的建立和遍历结果。程序：#include bitree.hvoid Visit(char ch)printf(%c ,ch);void PreOrder(BiTree root) /*先序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/if(root!=NULL)Visit(root-data);PreOrder(root-LChild);PreOrder(root-RChild);void InOrder(BiTree root) /*中序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/if(root!=NULL)PreOrder(root-LChild);Visit(root-data);PreOrder(root-RChild);void PostOrder(BiTree root) /* 后序遍历二叉树，root为指向二叉树(或某一子树)根结点的指针*/if(root!=NULL)PreOrder(root-LChild);PreOrder(root-RChild);Visit(root-data);void main()BiTree T;printf(按照扩展先序遍历输入结点（用.表示空）:n); CreateBiTree(&T);printf(先序遍历序列为:);PreOrder(T);printf(n中序遍历序列为:);InOrder(T);printf(n后序遍历序列为:);PostOrder(T);printf(n);结果截图：3.修改以上任意一个遍历的过程，分别统计二叉树中叶节点、度为1和度为2的结点个数，并输出统计结果。程序：#include bitree.hint v0,v1,v2;void PreOrder(BiTree root) if(root!=NULL) if(root-LChild=NULL&root-RChild=NULL)v0+;else if(root-LChild!=NULL&root-RChild!=NULL)v2+;elsev1+;PreOrder(root-LChild);PreOrder(root-RChild);void main()BiTree T;printf(按照扩展先序遍历输入结点（用.表示空）:n); CreateBiTree(&T);printf(按照先序遍历统计结点结果为:);PreOrder(T); printf(n); printf(v0=%d ,v0); printf(v1=%d ,v1); printf(v2=%d ,v2); printf(n); 结果截图：提高部分4.利用以上的头文件，采用扩展先序遍历的方法建立一个二叉树，写一函数完成二叉树左右子树交换的功能，并用先序遍历检验交换结果，观察交换是否成功。（考虑：交换左右子树用那种遍历方式最好？）程序：#include bitree.hvoid Visit(char ch);void PreOrder(BiTree root);void PostOrder(BiTree root) BiTree temp;if(root!=NULL)temp=root-LChild;root-LChild=root-RChild;root-RChild=temp;PostOrder(root-LChild);PostOrder(root-RChild);printf(%c,root-data);void PreOrder(BiTree root) if(root!=NULL)Visit(root-data);PreOrder(root-LChild);PreOrder(root-RChild);void Visit(char ch)printf(%c ,ch);void main()BiTree T;printf(按照扩展先序遍历输入结点（用