试验三二叉树及其应用.doc

实验三 二叉树及其应用 一、实验名称：二叉树及其应用 二、实验目的：本实验以二叉树的链式表示、建立和应用为基础，旨在让学生了解树和二叉树的存储结构，熟悉树及二叉树上的各种运算，掌握对二叉树进行三种遍历的算法，将算法改编成程序，上机调试并给出三种遍历序列的结果。设计性实验，效果良好。 三、实验原理：树是一种非线性结构，其应用极为广泛。本章首先以二叉树这种特殊、简单的树为原型，讨论数据元素(结点)之间关系的表示(顺序映像——完全二叉树的顺序存储；链式映像——二叉链表、三叉链表)；重点介绍二叉树的各种遍历算法(先序、中序、后序遍历)；并以这些遍历算法为基础，进一步讨论二叉树的其他各种问题的求解算法。然后，展开对一般树的表示(双亲表示法、孩子表示法、孩子-兄弟表示法)和操作算法的讨论；强调树(森林)的孩子-兄弟表示法及其相关应用；并将表示树(森林)的孩子-兄弟链表映射到二叉链，从而获得树(森林)与二叉树的相互转换。 遍历是二叉树上最重要的运算之一，它是二叉树上进行其他运算之基础。所谓遍历是指沿着某条有哪些信誉好的足球投注网站路线，依次对树中每个结点进行一次且仅做一次访问。二叉树遍历操作有三种次序：前序遍历、中序遍历和后序遍历。遍历规则采用递归的遍历算法，以中序遍历为例，其具体算法为： 若二叉树非空，则依次执行如下操作： 中序遍历左子树； 访问根结点； 中序遍历右子树。 将操作1和2次序对调即为先序遍历，而将2和3次序对调则得到后序遍历。遍历算法中的递归终止条件是二叉树为空，此时应为空操作。 四、实验内容： 从文件中读入一组随机数，以二叉链表作为存储结构，建立二叉树。 用先序、中序、后序算法遍历二叉树。 五、算法步骤：本实验由以下环节组成： 以二叉链表或三叉链表作为二叉树的存储结构； 图 1 以某种遍历的次序录入二叉树的元素，写出相应的二/三叉链表的创建算法，并上机实现该算法。 二叉树输入次序的方法：通过添加虚结点，将二叉树中的每一实在结点补足成度为2的结点，对补足虚结点后的二叉树按先序/中序/后序遍历的次序输入。如图1的二叉树按先序遍历的输入次序为： A, B, ???D, G, ?????????C, E, ???H, ??????F?????? 对所建的二叉树进行验证：按初始输入元素采用的遍历方法遍历该二叉树，看遍历的结果是否与初始输入一致； 六、代码： #include stdio.h #include stdlib.h typedef char DataType; /*设数据域类型为字符型*/ typedef struct node{ DataType data; struct node *lchild,*rchild; /*左右链域为指向结点结构的指针类型*/ }BinTNode; /*结点类型*/ typedef BinTNode *BinTree; /*指向二叉树结点的指针类型*/ int count; /*全局变量用于统计结点个数*/ void CreateBinTree(BinTree *T); /*以加入结点的先序序列输入，构造二叉链表*/ void Preorder(BinTree T); /*先序遍历二叉树T*/ void Inorder(BinTree T); /*中序遍历二叉树T*/ void Postorder(BinTree T); /*后序遍历二叉树T*/ void Leafnum(BinTree T); /*统计二叉树T中叶子结点的数目*/ void Nodenum(BinTree T); /*统计二叉树T的结点数目*/ main() { BinTree T; char ch1,ch2; printf(\n欢迎进入二叉树基本操作测试程序，请选择：\n); ch1=y; while(ch1==y || ch1==Y) { printf(\nA-------------------------二叉树建立); printf(\nB-------------------------先序遍历); printf(\nC-------------------------中序遍历); printf(\nD-------------------------后序遍历); printf(\nE-------------------------求叶子数); printf(\nF-------------------------求结点总数); printf(\nG-------------------------退出\n); scanf(\n%c,ch2); switch(ch2) { ca