数据结构树和二叉树实验报告.doc

《数据结构树和二叉树实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验题目树和二叉树小组合作否姓名班级学号一、实验目的(1)掌握树的相关概念,包括树、结点的度、树的度、分支结点、叶子结点、儿子结点、双亲结点、树的深度、森林等定义。(2)掌握二叉树的概念,包括二叉树、满二叉树和完全二叉树的定义。(3)掌握哈夫曼树的定义、哈夫曼树的构造过程和哈夫曼编码产生方法。二．实验环境装有VisualC++6.0的计算机一台。三、实验内容与步骤1、二叉树遍历递归算法：假设二叉树采用二叉链存储结构存储，是设计一个算法，输出一棵给定二叉树的所有叶子节结点。#include"stdaf

2、x.h"#include"exam7-8.cpp"intmain(intargc,char*argv[]){BTNode*b;CreateBTNode(b,"A(B(D(,G)),C(E,F))");printf("b:");DispBTNode(b);printf("");printf("从左到右输出所有叶子结点:");DispLeaf(b);printf("");printf("从右到左输出所有叶子结点:");DispLeaf1(b);printf("");return0;}假设二叉

3、树采用二叉树链式存储结构，设计一个算法输出从根结点到每个叶子结点的路径之逆（因为树中路径是从根结点到其他结点的结点序列，就是求叶子结点及其双亲结点、该双亲结点的双亲结点，直到根结点的序列，或者说求叶子结点及其所有祖先结点的序列）。要求采用后根遍历非递归算法。#include"stdafx.h"#include"exam7-12.cpp"intmain(intargc,char*argv[]){BTNode*b;CreateBTNode(b,"A(B(D(,G)),C(E,F))");printf("

4、b:");DispBTNode(b);printf("");printf("输出所有从叶子结点到根结点的序列:");AllPath1(b);return0;}设计一个算法将二叉树的顺序存储结构转换成二叉链式存储结构。#include"stdafx.h"#include"exam7-14.cpp"intmain(intargc,char*argv[]){inti,n=10;BTNode*b;SqBTreea;ElemTypes[]="0ABCD#EF##G";for(i=0;i<=n;i++)

5、a.data[i]=s[i];a.n=n;b=trans(a,1);printf("b:");DispBTNode(b);printf("");return0;}四、实验过程与分析1.先序遍历先序遍历二叉树的过程是：(1)访问根结点；(2)先序遍历左子树；(3)先序遍历右子树。2.中序遍历中序遍历二叉树的过程是：(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右子树。3.后序遍历后序遍历二叉树的过程是：(1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点。五、实验总结通过此次试验我

6、对二叉树的遍历有了一定的了解，仅有一个序列无法确定这棵二叉树的树形。但是，如果同时知道一棵二叉树的先序序列和中序序列，或者同时知道中序序列和后序序列，就能确定这棵二叉树。六、指导教师评语及成绩有完整的实验过程，运行出了正确的实验结果，很好的达到了实验的要求及实验目的。在实验过程中，该同学有效的发现了实验中的问题，并且很好的解决了问题，达到了培养解决问题的能力。