实验六二叉树的递归遍历及其应用
一、实验目的
1、深入了解二叉树递归的逻辑结构特征及其基本操作。
2、了解二叉树各种存储结构的特点及其适用范围，熟练掌握二叉树的二叉链表结构的定义及其递归遍历算法、按层次遍历算法的c语言实现，能深入了解递归算法的执行过程。
3、熟练掌握二叉树递归遍历算法的应用。
一、实验内容和要求
2、设计并验证如下算法：与“12.7.4参考源程序”类似，按中序序列输入建立两棵二叉树的二叉链表结构，求双分支结点数，判断两棵树是否相等。
3、设计并验证如下算法：按层次遍历二叉树，打印结点所在的层次，并求该二叉树的宽度。
二、实验过程及结果
（第一题）
一、需求分析
1、从键盘输入二叉树的序列，但由于建树是从根结点往下建立的，故只能输入先
序序列，则按照中序建树完成二叉树的创建。
2、从键盘输入一段正确的序列后，按回车键自动生成二叉树，若该序列不能生成
一颗二叉树，则程序无法继续进行，只能退出。
3、程序能实现的功能包括：
①初始化二叉树；②创建一棵完整二叉树；③先中后序遍历二叉树；
④求二叉树双分支结点数；⑤比较两棵二叉树是否相等；
二、概要设计
1、二叉树的抽象数据类型定义：
ADT BinaryTree{
数据对象D：D是具有相同特征的数据元素的集合。
数据关系R：
若D=空，则R=空，称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}；
（Dr,{Hr}）（4）（D1,{H1}）是一棵符合本定义的二叉树，称为根的左子树，
是一棵符合本定义的二叉树，称为根的右子树。
基本操作:
InitBiTree(&BT)
操作结果：构造空二叉树
CreateBiTree(&BT)
操作结果：建立二叉树
PreOrder(BT)
初始条件：二叉树BT已存在
操作结果：先序遍历
InOrder(BT)
初始条件：二叉树BT已存在
操作结果：中序遍历
PostOrder(BT)
初始条件：二叉树BT已存在
操作结果：后序遍历
Do_BranNumber(BT)
初始条件：二叉树BT已存在
操作结果：求BT的双分支结点数
Same_CompareTree(BT_a,BT1_b)
初始条件：二叉树BT_a、BT_b已存在
操作结果：比较两棵树是否相等
}ADT BinaryTree；
⒊本程序模块结构
⑴主函数模块
void main(){
初始化两颗二叉树；
创建二叉树BT_a，返回根结点BT_a；
getchar();
创建二叉树BT_b，返回根结点BT_b；
getchar();
先、中、后序遍历BT_a和BT_b；
if(两棵树相等)
printf("相同");
else
printf("不同");
输出BT_a和BT_b的双分支结点数；
｝
三、详细设计
1、基本数据类型操作
⑴二叉链表的存储结构
typedef char TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild; //左右孩子指针}BiTNode,*BiTree;
四、调试分析
1、创建两棵二叉树程序便不能继续运行，只能创建一棵树，加了getchar()后便能操作，原因可能是换行符造成的。
2、进行两棵树的比较时不仅要保证各结点值相等，还要确保结构相同，若结构不同，两棵树则不等，故采用递归算法。
3、求双分支结点数采用递归算法，一定要保证结束条件，此结束条件应为结点为空时返回0。
五、用户说明及测试结果
1、两棵二叉树不相等
2、两颗二叉树相等
七、附录（源代码及部分注释）
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#include "string.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
#define INFEASIBLE -2
#define Max_Tree_SIZE 20//最大结点数
typedef int Status;
typedef char TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild; //左右孩子指针
}BiTNode,*BiTree;
Status InitBiTree(BiTree *BT); //构造空二叉树
Status CreateBiTree(BiTree *BT); //建立二叉树
Status PreOrder(BiTree BT); //先序遍历
Status InOrder(BiTree BT); //中序遍历
Status PostOrder(BiTree BT); //后序遍历
int Do_BranNumber(BiTree BT); //求双分支结点数
Status Same_CompareTree(BiTree BT,BiTree BT1); //比较两棵树是否相等
void main()
{
int flag=1,select;
BiTree BT_a,BT_b;
InitBiTree(&BT_a);
InitBiTree(&BT_b);
printf("To Create Binary Tree, Please Input PreOrder with '#' :\n");//输入二叉树的先序序列，用#代表空结点
printf("Create The First Of Binary Tree(a): ");
CreateBiTree(&BT_a); //创建二叉树，返回根结点BT_a
getchar();
printf("Create The Second Of Binary Tree(b): ");
CreateBiTree(&BT_b); //创建二叉树，返回根结点BT_b
getchar();
printf("The First Of Binary Tree(a) is:\n");
printf("PreOrder Traversal: ");
PreOrder(BT_a); //先序遍历
printf("\nInOrder Traversal: ");
