树和二叉树实验报告.docx

《树和二叉树实验报告.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、树和二叉树实验报告课程数据结构实验名称树和二叉树系别____计算机学院专业班级__软件134_____姓名__徐雅欣____学号_4实验日期：2014年6月7日一.实验目的:（一）掌握二叉树，二叉树排序数的概念及存储方法。（二）掌握二叉树的遍历算法（三）熟练掌握编写实现树的各种运算的算法二.实验内容（－）实验题目一：建立一棵二叉树并中序遍历（填空）1.要点分析：中序遍历的遍历规则是（前中后），既先访问左子树，在访问当前节点，最后访问右子树。2.程序源代码：#include#includestructnode{chard

2、ata;structnode*lchild,*rchild;}bnode;typedefstructnode*blink;blinkadd(blinkbt,charch){if(bt==NULL){bt=(blink)malloc(sizeof(bnode));bt->data=ch;bt->lchild=bt->rchild=NULL;}elseif(chdata)bt->lchild=add(bt->lchild,ch);elsebt->rchild=add(bt->rchild,ch);returnbt;}voidinorder(blink

3、bt){if(bt){inorder(bt->lchild);printf("%2c",bt->data);inorder(bt->rchild);}}main(){blinkroot=NULL;inti,n;charx;scanf("%d",&n);for(i=0;i<=n;i++){x=getchar();root=add(root,x);}inorder(root);printf("");}3.实验结果：（二）实验题目2：编写程序，求二叉树的节点数和叶子树。1.要点分析：.定理：二叉树如果有v0个叶子节点，那么就有v0-1个度为二的节点就是v0-

4、1=v2定理：二叉树有N个节点N=v0+v1+v2即节点总数等于度为0，1，2的节点的和。2.程序源代码：#include#include#defineERROR0#defineOK1#defineOVERFLOW-2#defineTRUE1typedefintStatus;typedefcharTElemType;typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;intcount=0;StatusCreat

5、eBiTree(BiTree*T){charch;scanf("%c",&ch);if(ch=='')(*T)=NULL;else{if(!((*T)=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);(*T)->data=ch;CreateBiTree(&((*T)->lchild));CreateBiTree(&((*T)->rchild));}returnOK;}StatusCountleaf(BiTreeT){if(T){if((!T->lchild)&&(!T->rchild))count++;C

6、ountleaf(T->lchild);Countleaf(T->rchild);}returncount;}StatusDepth(BiTreeT){intdepthval,depthleft=0,depthright=0;if(!T)depthval=0;else{depthleft=Depth(T->lchild);depthright=Depth(T->rchild);depthval=1+(depthleft>depthright?depthleft:depthright);}returndepthval;}StatusPreorder(BiTr

7、eeT){if(T){printf("%c",T->data);Preorder(T->lchild);Preorder(T->rchild);}}StatusInOrderTraverse（BiTreeT，Status （*Visit）（TElemTypee））{StackS；InitStack（S）；p=T;while(p=!StackEmpty（S）){if （p）{Push(S,p);p=p->lchild;}else{Pop(S,p);if(!Visit(p->data))returnERROR;p=p->rchild;}}returnOK;}v

8、oidmain(){BiTreeT;printf("pleasei