二叉树应用源代码和实验报告

实验十一 二叉树的应用 姓名：高翠莹 学号：6103315009 专业班级：数媒1511、 实验项目名称 二叉树的应用2、 实验目的 1.通过实验理解二叉树的逻辑结构； 2.通过实验掌握二叉树的二叉链表存储结构； 3.通过实验掌握二叉树的应用。三、实验基本原理 1、数据结构 typedef struct BiTNode char data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree; 2、算法思想 这次实验主要是对二叉树的一些应用： （1）在二叉树中查找值为value的结点： 即寻找每一个节点的data,若与value相同则返回；（2） 统计出二叉树中叶子结点的数目： 如果一个左孩子和右孩子都为空，则返回1，然后递归访问左子树和右子树，统计 出所有的叶子结点；（3） 统计出二叉树中非叶子结点的数目： 用所有结点个数减去叶子结点个数即可；（4）统计出二叉树中所有结点的数目： 递归调用，返回左子树结点个数加右结点个数，再加1；（5）求二叉树的高度 递归求左子树高度h1和右子树高度h2，如果h1h2，则返回h1+1,否则返回h2+1； 3、算法描述 见代码四、主要仪器设备及耗材 1、硬件环境 2、开发平台 Dev C+5、 实验步骤 1.分析题目，确定数据结构类型，设计正确的算法； 2.编写代码； 3.运行及调试程序； 4.修改程序，提高其健壮性。六、实验数据及处理结果 1、程序清单#include #includeusing namespace std; typedef struct BiTNode char data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree; /按先序序列创建二叉树 int CreateBiTree(BiTree &T) char data; scanf(%c,&data); if(data = #) T = NULL; else T = (BiTree)malloc(sizeof(BiTNode); /生成根结点 T-data = data; /构造左子树 CreateBiTree(T-lchild); /构造右子树 CreateBiTree(T-rchild); return 0; /输出 void Visit(BiTree T) if(T-data != #) printf(%c ,T-data); /先序遍历 void PreOrder(BiTree T) if(T != NULL) /访问根节点 Visit(T); /访问左子结点 PreOrder(T-lchild); /访问右子结点 PreOrder(T-rchild); /叶子结点个数int Calleaf(BiTree T) if (T = NULL) return 0; if (T-lchild = NULL & T-rchild = NULL) return 1; return Calleaf(T-lchild) + Calleaf(T-rchild); /统计树的高度int BTreeHigh(BiTNode *tree) int h1,h2; if(tree = NULL) return 0; else h1 = BTreeHigh(tree-lchild);/左子树高度 h2 = BTreeHigh(tree-rchild);/右子树高度 if(h1 h2) return h1+1; else return h2+1; /树的节点 int countBTreeNode (BiTree tree) if(tree = NULL) return 0; else return (countBTreeNode(tree-lchild) + countBTreeNode(tree-rchild) + 1);/查找值为value的节点void locate(BiTree t, char x)/在二叉树t中查找值为x的结点 BiTree p; p=t; if (t = NULL) printf(无此节点n); else if( t-data = x) printf(%cn,p-data); else p=t-lchild; if(p) locate(t-lchild, x); else locate(t-rchild, x); void Tips()coutendl;cout按相应数字进行操作endl;cout1.计算二叉树中所有结点的数目endl;cout2.计算二叉树中所有叶子结点的数目endl;cout3.计算二叉树中所有非叶子结点的数目endl;cout4.查找二叉树中值为value的结点endl;cout5.求二叉树中的高度endl;cout0.退出endl; int main()cout*二叉树的应用*endl;cout一、创建二叉树endl; BiTree T;cout按先序次序输入二叉树中结点的值（一个字符），#表示空树endl; CreateBiTree(T);cout先序遍历这课树： endl;PreOrder(T);coutendl; cout二、具体操作op;while(op)switch(op)case 1:cout树的所有节点个数为： ; coutcountBTreeNode(T);break;case 2:cout所有叶子结点个数为： ;coutCalleaf(T);break;case 3:int count;cout非叶子结点的个数为： countBTreeNode(T)-Calleaf(T)endl; break;case 4:coutx; cout值为x的结点为: ; locate(T,x);break;case 5:cout树的高度为： ; coutop; 2、运行结果（1） 创建（2）操作求所有结点个数：求所有叶子结点个数：求所有非叶子结点个数：求值为value的结点：求二叉树的高度：7、 思