树与二叉树实验报告.docx
文本预览下载声明
树和二叉树实验报告
课程 数据结构 实验名称 树和二叉树
系 别____ 计算机学院 专业班级__ 软件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 1 typedef 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
显示全部