b11050311欧阳斌判断满二叉树

《b11050311欧阳斌判断满二叉树》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、洛阳理工学院实验报告系别计算机系班级B110503学号B11050311姓名欧阳斌课程名称数据结构实验日期4.23实验名称判断一棵二叉树是否为满二叉树成绩实验目的：熟悉掌握满二叉树的性质与特点，掌握与应用二叉链表存储的二叉树的基本操作算法，学会将二叉树三种遍历的递归算法应用于二叉树实际问题的解决，训练和提高分析问题能力，综合运用知识能力。实验条件：计算机一台，VisualC++6.0实验内容：1.【问题描述】判断一棵二叉树是否为满二叉树。要求二叉树用二叉链表存储。2.【测试数据】输入：ab$$c$$$这是一个满二叉树。3.【数据结构】typedefstructNode{chardata;st

2、ructNode*LChild;structNode*RChild;}BiTNode,*BiTree;4.【算法思想】首先初始化二叉链表，建立一颗二叉树，然后求出这颗二叉树的叶子节点M和非叶子结点N，然后在求出这颗二叉树的高度H，根据M+N与2H--1的大小关系判断其是否为满二叉树。1、创建二叉链表CreateBiTree(BiTree*bt)。2、先序遍历求二叉树的高度PreTreeDepth(BiTreeroot,inth)。3、求叶子结点PreLeaf(BiTreeroot)。4、求非叶子结点NoPreLeaf(BiTreeroot)。1、判断其是否为满二叉树IsTree(BiTree

3、root)。2、主函数intmain()。源程序#include#include#includeintdepth,Leaf,NLeaf,temp=1;typedefstructNode{chardata;structNode*LChild;structNode*RChild;}BiTNode,*BiTree;voidCreateBiTree(BiTree*bt){charch;ch=getchar();if(ch=='$')*bt=NULL;else{*bt=(BiTree)malloc(sizeof(BiTNode));(*bt)->d

4、ata=ch;CreateBiTree(&((*bt)->LChild));CreateBiTree(&((*bt)->RChild));}}voidPreTreeDepth(BiTreeroot,inth)//先序遍历求二叉树高度{if(root!=NULL){if(h>depth)depth=h;PreTreeDepth(root->LChild,h+1);PreTreeDepth(root->RChild,h+1);}}voidPreLeaf(BiTreeroot)//求叶子结点{if(root!=NULL){if(!(root->LChild)&&!(root->RChild)){L

5、eaf++;}PreLeaf(root->LChild);PreLeaf(root->RChild);}}voidNoPreLeaf(BiTreeroot)//求非叶子节点{if(root!=NULL){if((root->LChild)!=NULL

6、

7、(root->RChild)!=NULL){NLeaf++;}NoPreLeaf(root->LChild);NoPreLeaf(root->RChild);}}voidIsTree(BiTreeroot)//判断满二叉树{PreLeaf(root);NoPreLeaf(root);PreTreeDepth(root,0);inta,b;a=

8、Leaf+NLeaf-1;if((Leaf+NLeaf)