二叉树操作设计和实现实验报告

《二叉树操作设计和实现实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二叉树操作设计和实现实验报告一、目的：掌握二叉树的定义、性质及存储方式，各种遍历算法。二、要求：采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。三、实验内容：1、分析、理解程序程序的功能是采用二叉树链表存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作。如输入二叉树ABD###CE##F##，链表示意图如下：ABCDEF82、添加中序和后序遍历算法//========LNR中序遍历===============voidInor

2、der(BinTreeT){if(T){Inorder(T->lchild);printf("%c",T->data);Inorder(T->rchild);}}//==========LRN后序遍历============voidPostorder(BinTreeT){8if(T){Postorder(T->lchild);Postorder(T->rchild);printf("%c",T->data);}}3、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD#

3、##CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。（1）输入完全二叉树的先序序列ABD###CE##F##，程序运行结果如下：(2)先序序列:(3)中序序列:8(4)后序序列:(5)所有叶子及结点总数:(6)按层次遍历序列:8四、源程序代码#include"stdio.h"#include"string.h"#include"stdlib.h"#defineMax20//结点的最大个数typedefstructnode{chardata;structnode*

4、lchild,*rchild;}BinTNode;//自定义二叉树的结点类型typedefBinTNode*BinTree;//定义二叉树的指针intNodeNum,leaf;//NodeNum为结点数，leaf为叶子数//==========基于先序遍历算法创建二叉树==============//=====要求输入先序序列，其中加入虚结点"#"以示空指针的位置==========BinTreeCreatBinTree(void){BinTreeT;charch;if((ch=getchar())==

5、'#')return(NULL);//读入#，返回空指针else{T=(BinTNode*)malloc(sizeof(BinTNode));//生成结点T->data=ch;T->lchild=CreatBinTree();//构造左子树T->rchild=CreatBinTree();//构造右子树return(T);}}//========NLR先序遍历=============voidPreorder(BinTreeT){8if(T){printf("%c",T->data);//访问结点Pre

6、order(T->lchild);//先序遍历左子树Preorder(T->rchild);//先序遍历右子树}}//========LNR中序遍历===============voidInorder(BinTreeT){if(T){Inorder(T->lchild);printf("%c",T->data);Inorder(T->rchild);}}//==========LRN后序遍历============voidPostorder(BinTreeT){if(T){Postorder(T->lc

7、hild);Postorder(T->rchild);printf("%c",T->data);}}//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法========intTreeDepth(BinTreeT){inthl,hr,max;if(T){hl=TreeDepth(T->lchild);//求左深度hr=TreeDepth(T->rchild);//求右深度max=hl>hr?hl:hr;//取左右深度的最大值NodeNum=NodeNum+1;//求结点数if(hl==0&&

8、hr==0)leaf=leaf+1;//若左右深度为0，即为叶子。return(max+1);}elsereturn(0);}//====利用"先进先出"（FIFO）队列，按层次遍历二叉树==========voidLevelorder(BinTreeT){8intfront=0,rear=1;BinTNode*cq[Max],*p;//定义结点的指针数组cqcq[1]=T;//根入队while(front!=rear){front=(fr