实验六二叉树的递归遍历及其应用一、实验目的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，<root,x1>∈H,且存在D1上的关系H1包含于H；若Dr!=Φ,则Dr中存在唯一的元素，<root,xr>∈H，且存在Dr上的的关系Hr包含于H；H={<root,,x1>，<root,xr>，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("相同");elseprintf("不同");输出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_agetchar();printf("Create The Second Of Binary Tree(b): ");CreateBiTree(&BT_b); //创建二叉树，返回根结点BT_bgetchar();printf("The First Of Binary Tree(a) is:\n");printf("PreOrder Traversal: ");PreOrder(BT_a); //先序遍历printf("\nInOrder Traversal: ");InOrder(BT_a); //中序遍历printf("\nPostOrder Traversal: ");PostOrder(BT_a); //后序遍历printf("\n\nThe Second Of Binary Tree(b) is:\n");printf("PreOrder Traversal: ");PreOrder(BT_b); //先序遍历printf("\nInOrder Traversal: ");InOrder(BT_b); //中序遍历printf("\nPostOrder Traversal: ");PostOrder(BT_b); //后序遍历if(Same_CompareTree(BT_a,BT_b))printf("\n\nThe Binary Tree a and B is Same!\n");elseprintf("\n\nThe Binary Tree a and B is Different!\n");printf("\nThe Binary Tree a's Number of Double Branch is: %d",Do_BranNumber(BT_a));printf("\nThe Binary Tree b's Number of Double Branch is: %d\n\n",Do_BranNumber(BT_b));}/**********************InitBiTree********************/Status InitBiTree(BiTree *BT){ //构造空二叉树*BT=NULL;return OK;}/**********************CreateBiTree********************/Status CreateBiTree(BiTree *BT){//建立二叉树TElemType ch;scanf("%c",&ch);if(ch!='#'){*BT=(BiTree)malloc(sizeof(BiTNode));if(!(*BT))return OVERFLOW;CreateBiTree(&((*BT)->lchild)); //构造左子树(*BT)->data=ch;CreateBiTree(&((*BT)->rchild)); //构造右子树}else*BT=NULL; //读入#，返回空指针return OK;}/*********************PreOrder***********************/Status PreOrder(BiTree BT){ //先序遍历if(BT){if(!(BT->data))return ERROR;printf("%c",BT->data); //访问结点PreOrder(BT->lchild); //先序遍历左子树PreOrder(BT->rchild); //先序遍历右子树}return OK;}/*******************InOrder*******************/Status InOrder(BiTree BT){ //中序遍历if(BT){if(!(BT->data))return ERROR;InOrder(BT->lchild); //中序遍历左子树printf("%c",BT->data); //访问结点InOrder(BT->rchild); //中序遍历右子树}return OK;}/*******************PostOrder*****************/Status PostOrder(BiTree BT){ //后序遍历if(BT){if(!(BT->data))return ERROR;PostOrder(BT->lchild); //后序遍历左子树PostOrder(BT->rchild); //后序遍历右子树printf("%c",BT->data); //访问结点return OK;}}/******************Do_BranNumber*****************/int Do_BranNumber(BiTree BT){if(!BT)return 0;else{if(BT->lchild&&BT->rchild)return Do_BranNumber(BT->lchild)+Do_BranNumber(BT->rchild)+1;elsereturn Do_BranNumber(BT->lchild)+Do_BranNumber(BT->rchild);}}/*****************Same_Compare*******************/Status Same_CompareTree(BiTree BT,BiTree BT1){//递归遍历并比较if(BT==NULL&&BT1==NULL)return TRUE; //两棵树均为空时认为相等else if(BT==NULL||BT1==NULL)return FALSE;else if(BT!=NULL&&BT1!=NULL){if(BT->data==BT1->data){if(Same_CompareTree(BT->lchild,BT1->lchild)&&Same_CompareTree(BT->rchild,BT1->rchild) ||Same_CompareTree(BT->lchild,BT1->rchild)&&Same_CompareTree(BT->rchild,BT1->lchild)) {return TRUE;}}}return FALSE;}。