数据结构实验四树与二叉树.docx
数据结构实验四 树与二叉树数据结构实验四 树与二叉树 班级 学号 姓名 分数 一、实验目的： 1、掌握二叉树的定义、性质及存储方式，各种遍历算法。 2、掌握这种存储结构的构造算法以及基于每一种结构上的算法设计 3、初步掌握算法分析方法并对已设计出的算法进行分析，给出相应的结果。 二、实验要求： 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。 三、实验内容及分析： 1、分析、理解程序。 2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点，如ABD#CE#F#，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。 四、程序的调试及运行结果 先序遍历中序遍历后序遍历树的深度及叶子树层次遍历五、程序代码 #include"stdio.h" #include"stdlib.h" #include"string.h" #define Max 20 /结点的最大个数 typedef struct node char data; struct node *lchild,*rchild; BinTNode; /自定义二叉树的结点类型 typedef BinTNode *BinTree; /定义二叉树的指针 int NodeNum,leaf; /NodeNum为结点数，leaf为叶子数 /=基于先序遍历算法创建二叉树= /=要求输入先序序列，其中加入虚结点"#"以示空指针的位置= BinTree CreatBinTree(void) BinTree T; char ch; if(ch=getchar)='#') return(NULL); /读入#，返回空指针 else T= (BinTNode *)malloc(sizeof(BinTNode); /生成结点 T->data=ch; T->lchild=CreatBinTree; /构造左子树 T->rchild=CreatBinTree; /构造右子树 return(T); /=NLR 先序遍历= void Preorder(BinTree T) if(T) printf("%c",T->data); /访问结点 Preorder(T->lchild); /先序遍历左子树 Preorder(T->rchild); /先序遍历右子树 /=LNR 中序遍历= void Inorder(BinTree T) if(T) Inorder(T->lchild); /中序遍历左子树 printf("%c",T->data); /访问结点 Inorder(T->rchild); /中序遍历右子树 /=LRN 后序遍历= void Postorder(BinTree T) if(T) Postorder(T->lchild); /后序遍历左子树 Postorder(T->rchild); /后序遍历右子树 printf("%c",T->data); /访问结点 /=采用后序遍历求二叉树的深度、结点数及叶子数的递归算法= int TreeDepth(BinTree T) int hl,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; /若左右深度为0，即为叶子。 return(max+1); else return(0); /=利用"先进先出"队列，按层次遍历二叉树= void Levelorder(BinTree T) int front=0,rear=1; BinTNode *cqMax,*p; /定义结点的指针数组cq cq1=T; /根入队 while(front!=rear) front=(front+1)%NodeNum; p=cqfront; /出队 printf("%c",p->data); /出队，输出结点的值 if(p->lchild!=NULL) rear=(rear+1)%NodeNum; cqrear=p->lchild; /左子树入队 if(p->rchild!=NULL) rear=(rear+1)%NodeNum; cqrear=p->rchild; /右子树入队 /=数叶子节点个数= int countleaf(BinTree T) int hl,hr; if(T) hl=countleaf(T->lchild); hr=countleaf(T->rchild); if(hl=0&&hr=0) /若左右深度为0，即为叶子。 return(1); else return hl+hr; else return 0; /=主函数= void main BinTree root; char i; int depth; printf("n"); printf("Creat Bin_Tree； Input preorder:"); /输入完全二叉树的先序序列， / 用#代表虚结点，如ABD#CE#F# root=CreatBinTree; /创建二叉树，返回根结点 do /从菜单中选择遍历方式，输入序号。 printf("t* select *n"); printf("t1: Preorder Traversaln"); printf("t2: Iorder Traversaln"); printf("t3: Postorder traversaln"); printf("t4: PostTreeDepth,Node number,Leaf numbern"); printf("t5: Level Depthn"); /按层次遍历之前，先选择4，求出该树的结点数。 printf("t0: Exitn"); printf("t*n"); fflush(stdin); scanf("%c",&i); /输入菜单序号 switch (i-'0') case 1: printf("Print Bin_tree Preorder: "); Preorder(root); /先序遍历 break; case 2: printf("Print Bin_Tree Inorder: "); Inorder(root); /中序遍历 break; case 3: printf("Print Bin_Tree Postorder: "); Postorder(root); /后序遍历 break; case 4: depth=TreeDepth(root); /求树的深度及叶子数 printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum); printf(" BinTree Leaf number=%d",countleaf(root); break; case 5: printf("LevePrint Bin_Tree: "); Levelorder(root); /按层次遍历 break; default: exit(1); printf("n"); while(i!=0);
