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

《二叉树应用源代码和实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验十一二叉树的应用姓名：高翠莹学号：6103315009专业班级：数媒151一、实验项目名称二叉树的应用二、实验目的1.通过实验理解二叉树的逻辑结构；2.通过实验掌握二叉树的二叉链表存储结构；3.通过实验掌握二叉树的应用。三、实验基本原理1、数据结构typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;2、算法思想这次实验主要是对二叉树的一些应用：（1）在二叉树中查找值为value的结点：即寻找每一个节点的data,若与v

2、alue相同则返回；（2）统计出二叉树中叶子结点的数目：如果一个左孩子和右孩子都为空，则返回1，然后递归访问左子树和右子树，统计出所有的叶子结点；（3）统计出二叉树中非叶子结点的数目：用所有结点个数减去叶子结点个数即可；（4）统计出二叉树中所有结点的数目：递归调用，返回左子树结点个数加右结点个数，再加1；（5）求二叉树的高度递归求左子树高度h1和右子树高度h2，如果h1>h2，则返回h1+1,否则返回h2+1；3、算法描述见代码四、主要仪器设备及耗材1、硬件环境2、开发平台DevC++五、实验步骤1.分析题目，确定数据结

3、构类型，设计正确的算法；2.编写代码；3.运行及调试程序；4.修改程序，提高其健壮性。六、实验数据及处理结果1、程序清单#include#includeusingnamespacestd;typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;//按先序序列创建二叉树intCreateBiTree(BiTree&T){chardata;scanf("%c",&data);if(data==

4、'#'){T=NULL;}else{T=(BiTree)malloc(sizeof(BiTNode));//生成根结点T->data=data;//构造左子树CreateBiTree(T->lchild);//构造右子树CreateBiTree(T->rchild);}return0;}//输出voidVisit(BiTreeT){if(T->data!='#'){printf("%c",T->data);}}//先序遍历voidPreOrder(BiTreeT){if(T!=NULL){//访问根节点Visit(T);

5、//访问左子结点PreOrder(T->lchild);//访问右子结点PreOrder(T->rchild);}}//叶子结点个数intCalleaf(BiTreeT){if(T==NULL)return0;if(T->lchild==NULL&&T->rchild==NULL)return1;returnCalleaf(T->lchild)+Calleaf(T->rchild);}//统计树的高度intBTreeHigh(BiTNode*tree){inth1,h2;if(tree==NULL)return0;els

6、e{h1=BTreeHigh(tree->lchild);//左子树高度h2=BTreeHigh(tree->rchild);//右子树高度if(h1>h2)returnh1+1;elsereturnh2+1;}}//树的节点intcountBTreeNode(BiTreetree){if(tree==NULL)return0;elsereturn(countBTreeNode(tree->lchild)+countBTreeNode(tree->rchild)+1);}//查找值为value的节点voidlocate(

7、BiTreet,charx)//在二叉树t中查找值为x的结点{BiTreep;p=t;if(t==NULL)printf("无此节点");elseif(t->data==x)printf("%c",p->data);else{p=t->lchild;if(p)locate(t->lchild,x);elselocate(t->rchild,x);}}voidTips(){cout<

8、2.计算二叉树中所有叶子结点的数目"<