数据结构实验(三).doc

《数据结构》实验报告三
实验内容: 二叉树的遍历、赫夫曼编码设计
学号:_2010412105____     姓名:_陈栋栋______      
一、上机实验的问题和要求(需求分析):
A
B
C
D
E
F
G
H
I
[ 题目1] 对下图所示的二叉树,以二叉链表作为存储结构,建立二叉树(以先序来建立),并对其进行遍历(先序、中序、后序),打印输出遍历结果。从键盘接受输入(先序),并采用递归算法对其进行遍历(先序、中序、后序),将遍历结果打印输出。
二、程序设计的基本思想,原理和算法描述:
建立二叉树,对从键盘输入的字符进行检测,为非空字符创建结点并使当前结点指针指向该结点,并且递归地调用自己去建立它的左右子树;遇空格字符,使当前结点指针指向0即可,即空子树。
遍历二叉树,以先序遍历函数为例,若当前结点指针非空,输出指针所指结点中存储的元素,然后调用函数自身去处理当前结点指针的左右孩子。每个下层被委派的函数在输出上层传给它的指针指向结点的元素后,又像它的上层函数一样将当前结点的左右孩子分别委派给另外两个这样的函数去处理,这样层层下放任务,直至遍历完整棵二叉树。中序、后序只是输出当前结点中的元素的次序发生了变化。
题中二叉树的先序输入为:AB□CD□□□EFGH□□I□□□□(□为空格键)
三、调试和运行程序过程中产生的问题及采取的措施:
四、源程序及注释
#include <iostream>
using namespace std;
// 二叉树结构
typedef struct BinaryTree
{
char element; // 元素
BinaryTree *left; // 指向左孩子的指针
BinaryTree *right; // 指向右孩子的指针
}BiTree, *pBiTree;
// 创建一棵二叉树,数据来自键盘,空格表示空子树
void CreateBiTree(pBiTree &T, char &ch)
{
ch = getchar(); // 从键盘输入读入一个字符
if(ch== ' ') // 这个字符是否为空格
{
T=0; // 空子树// 改变了T值
}
else
{
T=(pBiTree)malloc(sizeof(BiTree));// 这里对T被改变,引用传递
T-> element=ch;
CreateBiTree(T->left, ch); // 调用自身去创建左子树
CreateBiTree(T->right,ch); // 调用自身创建右子树
}
}
void CreateBiT(pBiTree &T)
{
char ch;
CreateBiTree(T, ch);
}
// 先序遍历
void PreOrderTraverse(pBiTree tree)
{
if(tree != 0) // 当前结点非空才执行以下操作
{
cout<<tree->element; // 先输出当前结点的元素,再操作其左右子树
PreOrderTraverse(tree->left);
PreOrderTraverse(tree->ri