数据结构上机实验二叉树的操作和实现

《数据结构上机实验二叉树的操作和实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构实验指导书实验三二叉树操作设计和实现实验题目：二叉树操作设计和实现实验目的：掌握二叉树的定义、性质及存储方式，各种遍历算法。实验要求：采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。实验主要步骤：1、分析、理解程序。2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。//参考程序#include"stdio.h"#include"stdlib.h

2、"#include"string.h"#defineMax20//结点的最大个数typedefstructnode{chardata;structnode*lchild,*rchild;}BinTNode;//自定义二叉树的结点类型typedefBinTNode*BinTree;//定义二叉树的指针intNodeNum,leaf;//NodeNum为结点数，leaf为叶子数//==========基于先序遍历算法创建二叉树==============//=====要求输入先序序列，其中加入虚结点"#"以示空指针的位置==========BinTre

3、eCreatBinTree(void){BinTreeT;charch;if((ch=getchar())=='#')return(NULL);//读入#，返回空指针else{T=(BinTNode*)malloc(sizeof(BinTNode));//生成结点T->data=ch;T->lchild=CreatBinTree();//构造左子树T->rchild=CreatBinTree();//构造右子树return(T);}}//========NLR先序遍历=============voidPreorder(BinTreeT)第1页共4页

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

5、torder(BinTreeT){if(T){Postorder(T->lchild);//后序遍历左子树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;//取左右深

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

7、=cq[front];//出队printf("%c",p->data);//出队，输出结点的值if(p->lchild!=NULL){rear=(rear+1)%NodeNum;cq[rear]=p->lchild;//左子树入队}if(p->rchild!=NULL){rear=(rear+1)%NodeNum;cq[rear]=p->rchild;//右子树入队}}}//====数叶子节点个数==========intcountleaf(BinTreeT){inthl,hr;if(T){hl=countleaf(T->lchild);hr=co

8、untleaf(T->rchild);if(hl==0&&hr==0)//若左右深度为0，即为叶子。return(1);e