树与二叉树实验报告.docxVIP

树和二叉树实验报告 课程 数据结构 实验名称 树和二叉树 系 别____ 计算机学院 专业班级__ 软件134_____ 姓 名__ 徐雅欣____ 学号_201300406134 实验日期：2014 年6 月7日 实验目的: 掌握二叉树，二叉树排序数的概念及存储方法。 掌握二叉树的遍历算法 熟练掌握编写实现树的各种运算的算法 实验内容 （－）实验题目一：建立一棵二叉树并中序遍历（填空） 1.要点分析：中序遍历的遍历规则是（前 中 后），既先访问左子树，在访问当前节点，最后访问右子树。 2.程序源代码： #includestdio.h #includemalloc.h struct node { char data; struct node *lchild,*rchild; }bnode; typedef struct node *blink; blink add(blink bt,char ch) { if(bt==NULL) { bt=(blink)malloc(sizeof(bnode)); bt-data=ch; bt-lchild=bt-rchild=NULL; } else if(chbt-data) bt-lchild=add(bt-lchild,ch); else bt-rchild=add(bt-rchild,ch); return bt; } void inorder(blink bt) { if(bt) { inorder(bt-lchild); printf(%2c,bt-data); inorder(bt-rchild); } } main() { blink root=NULL; int i,n; char x; scanf(%d,n); for(i=0;i=n;i++) { x=getchar(); root=add(root,x); } inorder(root); printf(\n); } 3.实验结果： （二）实验题目2：编写程序，求二叉树的节点数和叶子树。 1.要点分析：.定理： HYPERLINK /search?word=%E4%BA%8C%E5%8F%89%E6%A0%91fr=qb_search_expie=utf8 \t _blank 二叉树如果有v0 个 叶子节点 ，那么就有v0-1个 度为二的节点 就是v0-1=v2  定理： HYPERLINK /search?word=%E4%BA%8C%E5%8F%89%E6%A0%91fr=qb_search_expie=utf8 \t _blank 二叉树有N个节点 N=v0+v1+v2 即 节点总数等于度为0，1，2的节点的和。 2.程序源代码： #includestdio.h#includemalloc.h#define ERROR 0#define OK 1#define OVERFLOW -2#define TRUE 1typedef int Status;typedef char TElemType; typedef struct BiTNode{ TElemType data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;int count=0;Status CreateBiTree(BiTree *T){char ch;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));}return OK;}Status Countleaf(BiTree T){ if(T){ if((!T-lchild)(!T-rchild)) count++;Countleaf(T-lchild);Countleaf(T-rchild );}return count;}Status Depth(BiTree T){ int depthval,depthleft=0,depthright=0;if(!T) depthval=0;else{ depthleft=Depth(T-lchild);depthr