数据结构树和二叉树实验报告.doc
文本预览下载声明
实验题目 树和二叉树 小组合作 否 姓名 班级 学 号 一、实验目的 (1)掌握树的相关概念,包括树、结点的度、树的度、分支结点、叶子结点、儿子结点、双亲结点、树的深度、森林等定义。
(2)掌握二叉树的概念,包括二叉树、满二叉树和完全二叉树的定义。
(3)掌握哈夫曼树的定义、哈夫曼树的构造过程和哈夫曼编码产生方法。
二．实验环境 装有Visual C++6.0的计算机一台。 三、实验内容与步骤 1、二叉树遍历递归算法：
假设二叉树采用二叉链存储结构存储，是设计一个算法，输出一棵给定二叉树的所有叶子节结点。
#include stdafx.h
#include exam7-8.cpp
int main(int argc, char* argv[])
{
BTNode *b;
CreateBTNode(b,A(B(D(,G)),C(E,F)));
printf(b:);DispBTNode(b);printf(\n);
printf(从左到右输出所有叶子结点:);DispLeaf(b);printf(\n);
printf(从右到左输出所有叶子结点:);DispLeaf1(b);printf(\n);
return 0;
}
假设二叉树采用二叉树链式存储结构，设计一个算法输出从根结点到每个叶子结点的路径之逆（因为树中路径是从根结点到其他结点的结点序列，就是求叶子结点及其双亲结点、该双亲结点的双亲结点，直到根结点的序列，或者说求叶子结点及其所有祖先结点的序列）。要求采用后根遍历非递归算法。
#include stdafx.h
#include exam7-12.cpp
int main(int argc, char* argv[])
{
BTNode *b;
CreateBTNode(b,A(B(D(,G)),C(E,F)));
printf(b:);DispBTNode(b);printf(\n);
printf(输出所有从叶子结点到根结点的序列:\n);
AllPath1(b);
return 0;
}
设计一个算法将二叉树的顺序存储结构转换成二叉链式存储结构。
#include stdafx.h
#include exam7-14.cpp
int main(int argc, char* argv[])
{
int i,n=10;
BTNode *b;
SqBTree a;
ElemType s[]=0ABCD#EF##G;
for (i=0;i=n;i++)
a.data[i]=s[i];
a.n=n;
b=trans(a,1);
printf(b:);DispBTNode(b);printf(\n);
return 0;
}
四、实验过程与分析 1. 先序遍历
先序遍历二叉树的过程是：
(1) 访问根结点；(2) 先序遍历左子树；(3) 先序遍历右子树。
2. 中序遍历
中序遍历二叉树的过程是：
(1) 中序遍历左子树；(2) 访问根结点；(3) 中序遍历右子树。
3. 后序遍历
后序遍历二叉树的过程是：
(1) 后序遍历左子树；(2) 后序遍历右子树；(3) 访问根结点。 五、实验总结
通过此次试验我对二叉树的遍历有了一定的了解，仅有一个序列无法确定这棵二叉树的树形。但是，如果同时知道一棵二叉树的先序序列和中序序列，或者同时知道中序序列和后序序列，就能确定这棵二叉树。 六、指导教师评语及成绩 有完整的实验过程，运行出了正确的实验结果，很好的达到了实验的要求及实验目的。在实验过程中，该同学有效的发现了实验中的问题，并且很好的解决了问题，达到了培养解决问题的能力。
显示全部