实验六二叉树的递归遍历及其应用

《实验六二叉树的递归遍历及其应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、..实验六二叉树的递归遍历及其应用一、实验目的1、深入了解二叉树递归的逻辑结构特征及其基本操作。2、了解二叉树各种存储结构的特点及其适用范围，熟练掌握二叉树的二叉链表结构的定义及其递归遍历算法、按层次遍历算法的c语言实现，能深入了解递归算法的执行过程。3、熟练掌握二叉树递归遍历算法的应用。一、实验内容和要求2、设计并验证如下算法：与“12.7.4参考源程序”类似，按中序序列输入建立两棵二叉树的二叉链表结构，求双分支结点数，判断两棵树是否相等。3、设计并验证如下算法：按层次遍历二叉树，打印结点所在的层次，并求该二叉树的宽度。二、实验过

2、程及结果（第一题）一、需求分析1、从键盘输入二叉树的序列，但由于建树是从根结点往下建立的，故只能输入先序序列，则按照中序建树完成二叉树的创建。2、从键盘输入一段正确的序列后，按回车键自动生成二叉树，若该序列不能生成一颗二叉树，则程序无法继续进行，只能退出。3、程序能实现的功能包括：①初始化二叉树；②创建一棵完整二叉树；③先中后序遍历二叉树；④求二叉树双分支结点数；⑤比较两棵二叉树是否相等；二、概要设计1、二叉树的抽象数据类型定义：ADTBinaryTree{数据对象D：D是具有相同特征的数据元素的集合。数据关系R：若D=空，则R=空

3、，称BinaryTree为空二叉树；若D！=空，则R={H}，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若D-{root}!=Φ，则存在D-{root}={D1,Dr}，且D1∩Dr=Φ；（3）若D1！=Φ，则D1中存在唯一元素x1，∈H,且存在D1上的关系H1包含于H；若Dr!=Φ,则Dr中存在唯一的元素，∈H，且存在Dr上的的关系Hr包含于H；H={，，H1，Hr}；（4）（D1,{H1}）是一棵符合本定义

4、的二叉树，称为根的左子树，（Dr,{Hr}）是一棵符合本定义的二叉树，称为根的右子树。基本操作:InitBiTree(&BT)操作结果：构造空二叉树CreateBiTree(&BT)word教育资料..操作结果：建立二叉树PreOrder(BT)初始条件：二叉树BT已存在操作结果：先序遍历InOrder(BT)初始条件：二叉树BT已存在操作结果：中序遍历PostOrder(BT)初始条件：二叉树BT已存在操作结果：后序遍历Do_BranNumber(BT)初始条件：二叉树BT已存在操作结果：求BT的双分支结点数Same_Compar

5、eTree(BT_a,BT1_b)初始条件：二叉树BT_a、BT_b已存在操作结果：比较两棵树是否相等}ADTBinaryTree；⒊本程序模块结构⑴主函数模块voidmain(){初始化两颗二叉树；创建二叉树BT_a，返回根结点BT_a；getchar();创建二叉树BT_b，返回根结点BT_b；getchar();先、中、后序遍历BT_a和BT_b；if(两棵树相等)printf("相同");elseprintf("不同");输出BT_a和BT_b的双分支结点数；｝三、详细设计1、基本数据类型操作⑴二叉链表的存储结构typede

6、fcharTElemType;typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;四、调试分析word教育资料..1、创建两棵二叉树程序便不能继续运行，只能创建一棵树，加了getchar()后便能操作，原因可能是换行符造成的。2、进行两棵树的比较时不仅要保证各结点值相等，还要确保结构相同，若结构不同，两棵树则不等，故采用递归算法。3、求双分支结点数采用递归算法，一定要保证结束条件，此结束条件应为结点为空时返回

7、0。五、用户说明及测试结果1、两棵二叉树不相等2、两颗二叉树相等七、附录（源代码及部分注释）#include"stdio.h"#include"stdlib.h"word教育资料..#include"conio.h"#include"string.h"#defineOK1#defineERROR0#defineTRUE1#defineFALSE0#defineOVERFLOW-1#defineINFEASIBLE-2#defineMax_Tree_SIZE20//最大结点数typedefintStatus;typedefcharTE

8、lemType;typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;StatusInitBiTree(BiT