树和二叉树的建立及应用数据结构实验报告

《树和二叉树的建立及应用数据结构实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《数据结构与算法》实验报告姓名学号日期实验项目树和二叉树的建立及应用指导教师上机实验的问题和要求（需求分析人实验内容：1、用先序序列生成二叉树；2、给岀先序遍历，中序遍历和后序遍历各项操作结果。3、给出二叉树的髙度。4、给出二叉树的叶子数。5、二叉树的每层结点数。6、查找二叉树的是否存在结点X。实验要求：1、常握树特别是二叉树的建立、插入、删除、周游等算法2、掌握二叉树的存储方法3、会利用树结构解决实际问题二、程序设计的基本思想，原理和算法描述：1.运用二叉树的固有属性一一递归，用递归算法对二叉树行处理描述；2.•为了运算和参数传

2、递的方便，直接将二叉树定义为指向节点的指针类型;3..在输入结点时，为了方便，在程序中把结点定义为字符类型；4、输入的二叉树：a5.在编程过程中，查找了许多相关的程序，经过探索最终得到了如下程序。三、源程序及注释：#include#includetypedefstructBiTNode//泄义一个结构体{chardata;structBiTNode*lchild;〃左右指针structBiTNode*rchild;}BiTNode,*BiTree;voidPreCreateBinTree(Bi

3、Tree&T){charch;printf(n请输入结点:”);scanf("%c",&ch);if(ch=?){T=NULL;printfC*无结点，返回上一层创建“)；)else{printfC噺结点：%cu,ch);T=(BiTNode*)malloc(sizeof(BiTNode));T->data=ch;printf("正在创建％c的左子树",T->data);PreCreateBinTree(T->lchild);printf(”正在创建％c的右子树H,T->data);PreCreateBinTr

4、ee(T->rchild);}voidInTraBinTree(BiTNode*T)〃中序遍历二叉树讦(Tolchild!二NULL)InTraBinTree(T->lchild);}printf("%c",T->data);讦(T->rchild!=NULL){InTraBinTree(T->rchild);}}voidPoTraBinTree(BiTNode*T)〃后序遍历二叉树{if(T->lchild!=NULL){InTraBinTree(T->lchiId);}讦(T->rchild!=NULL){InTraBinTr

5、ee(T->rchild);}printf("%c",T->data);}intGetLeavesCounts(BiTNode*T)〃获得叶子结点个数intcounts=0;〃记录叶子结点个数if(T->lchild==NULL&&T->rchild==NULL){return1;}讦(T->lchild!=NULL){counts+=GetLeavesCounts(T->lchild);}if(T->rchild!=NULL){counts+=GetLeavesCounts(T->rchild);}returncounts;}i

6、ntGetBinTreeDeep(BiTNode*T)〃获得二叉树高度{讦(T・>lchild二二NULL&&T->rchild==NULL){return0;}intleft_deep=O,right_deep=O;if(T->lchild!=NULL)left_deep=GetBinTreeDeep(T->lchild);〃获得左子树的深度if(T->rchild!=NULL)〃获得右了•树的深度{right_deep=GetBinTreeDeep(T->rchild);}if(left_deep>right_deep){re

7、turnleft_deep+l;}returnright_deep+1;}BiTNode*search_ch(BiTNode*T,charx){printf(”请输入x:“)；scanf(n%c“,&x);BiTNode*temp;if(T==NULL)returnNULL;if(x==T->data)returnT;temp=search_ch(T->lchild,x);if(temp!=NULL)returntemp;elsereturnsearch_ch(T->rchild,x);}；voidmain()BiTreeT;

8、BiTNode*p;charx;PreCreateBinTree(T);printf(HM);printf(M树的根结点值为:T->data=%cM,T->data);printf(”中序遍历“)；InTraBinTree(T);print