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

实验题目树和二叉树小组合作否姓名班级学 号一、实验目的(1)掌握树的相关概念,包括树、结点的度、树的度、分支结点、叶子结点、儿子结点、双亲结点、树的深度、森林等定义。(2)掌握二叉树的概念,包括二叉树、满二叉树和完全二叉树的定义。(3)掌握哈夫曼树的定义、哈夫曼树的构造过程和哈夫曼编码产生方法。二实验环境装有Visual C+6.0的计算机一台。三、实验内容与步骤1、二叉树遍历递归算法：假设二叉树采用二叉链存储结构存储，是设计一个算法，输出一棵给定二叉树的所有叶子节结点。#include stdafx.h#include exam7-8.cppint 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.cppint 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.cppint 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.datai=si;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) 访问根结点。五、实验总结通过此次试验我对二叉树的遍历有了一定的了解，仅有一个序列无法确定这棵二叉树的树形。但是，如果同时知道一棵二叉树的先序序列和中序序列，或者同时知道中序序列和后序序列，就能确定这棵二叉树。六、指导教师评语及成绩有完整的实验过程，运行出了正确