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

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

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

3、oot，它在关系H下无前驱；（2） 若D-root!=，则存在D-root=D1,Dr，且D1Dr=；（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；（4） （D1,H1）是一棵符合本定义的二叉树，称为根的左子树，（Dr,Hr）是一棵符合本定义的二叉树，称为根的右子树。基本操作: InitBiTree(&BT)操作结果：构造空二叉树Creat

4、eBiTree(&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； 本程序模块结构1 主函数模块void main()初始化两颗二叉树；创建二叉树BT_a，返回根结

5、点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、创建两棵二叉树

6、程序便不能继续运行，只能创建一棵树，加了getchar()后便能操作，原因可能是换行符造成的。2、进行两棵树的比较时不仅要保证各结点值相等，还要确保结构相同，若结构不同，两棵树则不等，故采用递归算法。3、求双分支结点数采用递归算法，一定要保证结束条件，此结束条件应为结点为空时返回0。 五、用户说明及测试结果1、两棵二叉树不相等2、两颗二叉树相等七、附录（源代码及部分注释）#include "stdio.h"#include "stdlib.h"#include "conio.h"#include "string.h"

7、;#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);/构造空二叉树S

8、tatus 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);InitBi

9、Tree(&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(&a

10、mp;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("nnThe Second O

11、f 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("nnThe Binary Tree a and B is Same!n");

12、elseprintf("nnThe 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: %dnn",Do_BranNumber(BT_b);/*InitBiTree*/Status InitBiTree(BiTree *BT)

13、/构造空二叉树*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);/构造

14、右子树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

15、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);

16、/访问结点return OK;/*Do_BranNumber*/int Do_BranNumber(BiTree BT)if(!BT)return 0;elseif(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