数据结构集中上机
试验报告
学院： 计算机科学与技术 专业：计算机科学与技术
学号： 班级： 姓名：
2010/11/26
题目：二叉树的创建与遍历
一、实验目的
1．学会实现二叉树结点结构和对二叉树的基本操作。
2．掌握对二叉树每种操作的具体实现，学会利用递归和非递归方法编写对二叉树这种递归数据结构进行处理的算法。
二、实验要求
1．认真阅读和掌握和本实验相关的教材内容。
2．编写完整程序完成下面的实验内容并上机运行。
3．整理并上交实验报告。
三、实验内容
1．编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归和非递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历。
四、实验步骤
源程序代码
#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 || !S.empty())
{
while(p!=NULL)
{
cout<<p->data; //访问根结点
S.push(p);
p=p->leftChild; //遍历指针进到左子女结点
}
if(!S.empty()) //栈不空时退栈
{
p=S.top();
S.pop();
p = p->rightChild; //遍历指针进到右子女结点
}
}
}
//----------------------------------------------------------------
template<class T>
void InOrder_2(BinTreeNode<T> *p) //非递归中序遍历
{
stack<BinTreeNode<T>* > S;
do
{
while(p!=NULL) //遍历指针未到最左下的结点，不空
{
S.push(p);
p=p->leftChild;
}
if(!S.empty()) //栈不空时退栈
{
p=S.top();
S.pop();
cout<<p->data;
p=p->rightChild;
}
}
while(p !=NULL || !S.empty());
}
//------------------------------------------------------------------
template<class T>
void PostOrder_2(BinTreeNode<T> *p) //非递归后序遍历
{
stack<BinTreeNode<T> * > S;
stack<int> tag;//定义一个新的栈用来保存tag域判别根结点的左右子树是否均遍历过
while(p != NULL || !S.empty()) //左子树经过结点加L进栈
{
while(p!=NULL)
{
S.push(p); //首先将t和tag为0入栈，遍历左子树
tag.push(0);//遍历左子树前的现场保护
p=p->leftChild;
}
while( !S.empty() && tag.top()==1)
{
p=S.top();
S.pop();
tag.pop();
cout<<p->data; //最后访问根结点。
}
if( !S.empty())
{
tag.pop();
tag.push(1);//遍历右子树前的现场保护,修改栈顶tag为1，遍历右子树
p=S.top(); // 取栈顶保存的指针
p=p->rightChild;
}
else
break;
}
}
//--------------------------------------------------------------------
template<class T>
void InOrder_1(BinTreeNode<T> * subTree)
{//递归函数：中序次序遍历以subTree为根的子树。
if(subTree !=NULL) //NULL是递归终止条件
{
InOrder_1(subTree->leftChild); //中序遍历根的左子树
cout<<subTree->data; //访问根结点
InOrder_1(subTree->rightChild); //中序遍历根的右子树
}
}
//--------------------------------------------------------------------------
template<class T>
void PreOrder_1(BinTreeNode<T> * subTree)
{//递归函数：前序遍历以subTree为根的二叉树。
if(subTree !=NULL) //递归结束条件
{
cout<<subTree->data;//访问根结点
PreOrder_1(subTree->leftChild); //前序遍历根的左子树
PreOrder_1(subTree->rightChild); //前序遍历根的右子树
}
}
//---------------------------------------------------------------------------
template<class T>
void PostOrder_1(BinTreeNode<T> * subTree)
{//递归函数：后序次序遍历以subTree为根的子树。
if(subTree !=NULL) //NULL是递归终止条件
{
PostOrder_1(subTree->leftChild); //后序遍历根的左子树
PostOrder_1(subTree->rightChild); //后序遍历根的右子树
cout<<subTree->data; //访问根结点
}
}
//--------------------------------------------------------------------------
template<class T>
void CreateBinTree(BinTreeNode<T> * & subTree)
{//递归方式建立二叉树
T item;
cin>>item;
if(item !=-1)
{
subTree = new BinTreeNode<T>();
if(subTree == NULL)
{
cerr<<"存储分配错！"<<endl;
exit(1);
}
subTree->data = item;
CreateBinTree(subTree->leftChild); //递归建立左子树
CreateBinTree(subTree->rightChild); //递归建立右子树
}
else subTree = NULL; //封闭指向空子树的指针
}
int main()
{
BinTreeNode<int> * Tree = NULL;
cout<<"请输入每个结点，回车确认，并以-1结束：";
CreateBinTree(Tree);
cout<<"先序遍历二叉树结果：";
PreOrder_1(Tree);
cout<<endl;
cout<<"中序遍历二叉树结果：";
InOrder_1(Tree);
cout<<endl;
cout<<"后序遍历二叉树结果：";
PostOrder_1(Tree);
cout<<endl;
cout<<"非递归前序遍历二叉树结果：";
PreOrder_2(Tree);
cout<<endl;
cout<<"非递归中序遍历二叉树结果：";
InOrder_2(Tree);
cout<<endl;
cout<<"非递归后序遍历二叉树结果：";
PostOrder_2(Tree);
cout<<endl;
return 1;
}
第二篇：二叉树遍历 实验报告
数据结构实验报告
报告题目： 二叉树的基本操作
学生班级：
学生姓名： 学号：
一．实验目的
1、 基本要求：深刻理解二叉树性质和各种存储结构的特点及适用范围；掌握用指针类型描述、访问和处理二叉树的运算；熟练掌握二叉树的遍历算法；。
2、 较高要求: 在遍历算法的基础上设计二叉树更复杂操作算法；认识哈夫曼树、哈夫曼编码的作用和意义;掌握树与森林的存储与便利。
二. 实验学时：
课内实验学时：3学时
课外实验学时：6学时
三．实验题目
1． 以二叉链表为存储结构，实现二叉树的创建、遍历（实验类型：验证型）
1）问题描述：在主程序中设计一个简单的菜单，分别调用相应的函数功能：
1…建立树
2…前序遍历树
3…中序遍历树
4…后序遍历树
5…求二叉树的高度
6…求二叉树的叶子节点
7…非递归中序遍历树
0…结束
2）实验要求：在程序中定义下述函数，并实现要求的函数功能：
CreateBinTree(BinTree &T): 按从键盘输入的前序序列，创建树
Preorder(BinTree &T)：前序遍历树（递归）
Inorder(BinTree &T)：中序(递归)遍历树
Postorder(BinTree &T): 后序遍历树（递归）
PostTreeDepth(BinTree &T)：树的高度
leaf(BinTree &T):树的叶子节点
InorderN(BinTree &T)：中序(非递归)遍历树
3)数据结构
² 二叉链表存储数据类型定义
typedef struct node{
TElemType data;
struct node *lchild,*rchild;
}BinTNode;
元素类型：
int CreateBinTree(BinTree &T);
void Preorder(BinTree &T);
void Inorder(BinTree &T);
void Postorder(BinTree &T);
void InorderN(BinTree &T);
int PostTreeDepth(BinTree &T);
int leaf(BinTree &T);
2、编写算法实现二叉树的非递归中序遍历和求二叉树高度。
1）问题描述：实现二叉树的非递归中序遍历和求二叉树高度
2）实验要求：以二叉链表作为存储结构
3) 实现过程：
1、实现非递归中序遍历代码：
void CBiTree::InorderN(BinTree &T)
{
BinTree stack[MAX],p;
int top=0;p=T;
do
{
while(p!=NULL)
{
stack[top]=p;;
top=top+1;
p=p->lchild;
};
if(top>0)
{
top=top-1;
p=stack[top];
printf("%3c",p->data );
p=p->rchild;
}
}
while(p!=NULL||top!=0);
}
2、求二叉树高度：
int CBiTree::PostTreeDepth(BinTree &T)
{
int l,r,max;
if(T!=NULL)
{
l=PostTreeDepth(T->lchild );
r=PostTreeDepth(T->rchild );
max=l>r?l:r;
return(max+1);
}
else return(0);
}
实验步骤：
1） 新建一个基于Console Application的工程，工程名称BiTreeTest；
2） 新建一个类CBiTree二叉树类。
3） 在类CBiTree的头文件上方定义二叉链表存储数据类型结构体BiTNode。
4） 在类CBiTree中定义函数CreateBinTree（）；Preorder()；Inorder()；Postorder();PostTreeDepth();InorderN()；
5） 实现函数CreateBinTree（）；Preorder()；Inorder()；Postorder();PostTreeDepth();InorderN()；
6） 在主函数中定义对象，通过对象调用函数，实现各个函数的操作。
运行结果：
