文档介绍：word
word
1 / 8
word
实验三二叉树
一、实验目的
1．掌握二叉树的链式存储结构与其相关操作的实现。
2．掌握二叉树的先序、中序、后序的递归遍历算法。
3．理解二叉树的各种非递归遍历算法的实现。
二、实验要求
1．实验前做好充分准备，包括复习第六章所学容，事先预录实验结果，按要求完成各题。
3．实验完毕后，给出实验总结与分析并与时给出本次实验的实验报告。
三、实验题目
本次实验给出的选定题目如下表所示。
实验名称
学
时
实验容
实验要求
实验
类型
二叉树
4
〔1〕二叉树的创建、递归遍历与其它根本操作的实现。
必做
设计性
〔2〕二叉树非递归遍历算法的实现。
选做
设计性
〔3〕哈夫曼树与哈夫曼编码的算法实现。
选做
综合性
说明：
〔1〕实验容1〕为必做容。
〔2〕实验容2〕与实验容3〕为选做容。
四、实验容与要求
1、实验题目一：〔1〕二叉树的创建、递归遍历与其它根本操作的实现。
要求：定义用二叉链表表示的二叉树，并实现二叉树的创建、遍历〔先序、中序后序〕的递归算法与求深度操作等，并对其进展验证。
2、实验题目二：二叉树非递归遍历算法的实现
要求：在题目一的根底上，实现二叉树的非递归遍历算法〔先序、中序、后序或按层〕，并对其进展验证。
3、实验题目三：哈夫曼树与哈夫曼编码的算法实现
要求：编程实现哈夫曼树的创建与利用哈夫曼树求解哈夫曼编码。
word
word
2 / 8
word
实验步骤
源代码：
#include<iostream>
#include<stack>
using namespace std;
template<class T>
struct BinTreeNode //二叉树结点类定义
{
T data; //数据域
BinTreeNode<T> *leftChild,*rightChild; //左子女、右子女域
BinTreeNode(T x=T(),BinTreeNode<T>* l =NULL,BinTreeNode<T>* r = NULL )
:data(x),leftChild(l),rightChild(r){} //可选择参数的默认构造函数
};
//-------------------------------------------------------------------------
template<class T>
void PreOrder_2(BinTreeNode<T> *p) //非递归前序遍历
{
stack<BinTreeNode<T> * > S;
while(p!=NULL || !())
{
while(p!=NULL)
{
cout<<p->data; //访问根结点
(p);
p=p->leftChild; //遍历指针进到左子女结点
}
if(!())