实验二、二叉树操作.doc

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

1、实验二、二叉树操作一、目的掌握二叉树的定义、性质及存储方式，各种遍历算法。二、要求采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。三、实验内容1、分析程序存储结构Typedefstructnode{Chardata;Structnode*lchild,*rchild;}BinTNode;//自定义二叉树的结点类型typedefBinTNdoe*BinTree;//自定义二叉树的指针intNodeNum,leaf;//NodeNum为结点数，leaf为叶子数主要流程及模块调用进入主函数先进行

2、创建二叉树CreatBinTree出现主界面调用先序，中序，后序，层次，以及求所有叶子及结点总数的函数进行遍历。2、测试内容及结果：设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。1、改正后的程序：#include#include#include#defineMax20//结点的最大个数typedefstructnode{chardata;structnode*lchild

3、,*rchild;}BinTNode;//自定义二叉树的结点类型typedefBinTNode*BinTree;//定义二叉树的指针intNodeNum,leaf;//NodeNum为结点数，leaf为叶子数,//Nos]deNum是全局变量，应用时要初始化//==========基于先序遍历算法创建二叉树==============//=====要求输入先序序列，其中加入虚结点"#"以示空指针的位置==========BinTreeCreatBinTree(void){BinTreeT;charch;if((ch=getchar())=='#')re

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

5、先序遍历左子树Preorder(T->rchild);//先序遍历右子树}}//========LNR中序遍历===============voidInorder(BinTreeT){if(T){Inorder(T->lchild);//中序遍历左子树printf("%c",T->data);//访问结点Inorder(T->rchild);//中序遍历右子树}}//==========LRN后序遍历============voidPostorder(BinTreeT){if(T){Preorder(T->lchild);//后序遍历左子树Preord

6、er(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&&hr==0)leaf=leaf+1;//若左右

7、深度为0，即为叶子。return(max+1);}elsereturn(0);}//====利用"先进先出"（FIFO）队列，按层次遍历二叉树==========voidLevelorder(BinTreeT)//判断内存分配失败{intfront=0,rear=1;BinTNode*cq[Max],*p;//定义结点的指针数组cqif(T!=NULL){cq[1]=T;//根入队while(front!=rear){front++;//=(front+1);//%NodeNum;p=cq[front];//出队printf("%c",p->data)

8、;//出队，输出结点的值if(p->lchild!=NULL){rear++;//=(rear