文档介绍：数据结构树和二叉树实验报告
《数据结构》课程实验报告
实验名称
树与二叉树
实验序号
5
实验日期
姓
名
院系
班 级
学 号
专
业
指导教师
成 绩
教师评语
一、实验目的与要求
掌握树的相关概念 ,包括树、结点的度、树的度、分支结点、叶子结点、儿子结点、双亲结点、树的深度、森林等定义。
掌握树的表示 ,包括树形表示法、文氏图表示法、凹入表示法与括号表示法等。
掌握二叉树的概念 ,包括二叉树、满二叉树与完全二叉树的定义。
掌握二叉树的性质。
重点掌握二叉树的存储结构 ,包括二叉树顺序存储结构与链式存储结构。
重点掌握二叉树的基本运算与各种遍历算法的实现。
掌握线索二叉树的概念与相关算法的实现。
掌握哈夫曼树的定义、哈夫曼树的构造过程与哈夫曼编码产生方法。
掌握并查集的相关概念与算法。
(10)灵活掌握运用二叉树这种数据结构解决一些综合应用问题。
二、实验项目摘要
,实现二叉树的各种基本运算 ,并在此基础上设计一个主程序完成如下功能 :
1）输出二叉树 b;
2）输出 H 结点的左、右孩子结点值 ;
3）输出二叉树 b 的深度 ;
4）输出二叉树 b 的宽度 ;
5）输出二叉树 b 的结点个数 ;
6）输出二叉树 b 的叶子结点个数。
,实现二叉树的先序遍历、中序遍历与后序遍历的各种递归与非递归算法 ,以及层次遍历的
算法。
三、实验预习内容
二叉树存储结构 ,二叉树基本运算 (创建二叉树、寻找结点、找孩子结点、求高度、输出二叉树 )
数据结构树和二叉树实验报告
三、实验结果与分析
7-1
#include <stdio 、 h>
#include <malloc 、 h>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
ElemType data;
struct node *lchild;
struct node *rchild;
} BTNode;
void CreateBTNode(BTNode *&b,char *str)
{
BTNode *St[MaxSize],*p=NULL;
int top=-1,k,j=0;
char ch;
b=NULL;
ch=str[j];
while (ch!='\0')
{
switch(ch)
{
case '(':top++;St[top]=p;k=1; break;
case ')':top--;break;
case ',':k=2; break;
default:p=(BTNode *)malloc(sizeof(BTNode));
p->data=ch;p->lchild=p->rchild=NULL;
if (b==NULL)
b=p;
else
{
switch(k)
{
case 1:St[top]->lchild=p;break;
case 2:St[top]->rchild=p;break;
}
}
}
j++;
ch=str[j];
}
}
数据结构树和二叉树实验报告
BTNode *FindNode(BTNode *b,ElemType x)
{
BTNode *p;
if (b==NULL)
return NULL;
else if (b->data==x)
return b;
else
{
p=FindNode(b->lchild,x);
if (p!=NULL)
return p;
else
return FindNode(b->rchild,x);
}
}
BTNode *LchildNode(BTNode *p)
{
return p->lchild;
}
BTNode *RchildNode(BTNode *p)
{
return p->rchild;
}
int BTNodeDepth(BTNode *b)
{
int