实 验 报 告
课程名称 算法与数据结构
专 业
学号
姓名
实验日期 2013年11月17日
算法与数据结构实验报告
二叉树的应用
一、实验目的
1.了解二叉树的结构特点及有关概念，掌握二叉树建立的基本算法
2.了解二叉树遍历的概念，掌握遍历二叉的算法
3.进一步掌握树的结构及非线性特点，递归特点和动态性。
二、实验内容
二叉树的实现和运算
三、实验要求
1．用C++/C完成算法设计和程序设计并上机调试通过。
2．撰写实验报告，提供实验结果和数据。
3．分析算法，并简要给出算法设计小结和心得。
四、算法步骤
用户以三元组形式输入二叉树的结点元素及其位置关系，建立二叉树，并打印输出该二叉树。
用户输入选择结点，程序调用BiTNode* Find Node(char tag, BiTNode* node)函数，返回子树的根结点，然后调用BiTreeDepth(BiTree T)函数，求出子树的深度，并输出该值。
3.用户可以选择是否继续执行程序，若继续，则输入1，否则输入0，结束程序。
五、主程序代码：
int main(void)
{
BiTree T;
TElemType e1;
char node; // node为用户选择输入的结点//
int b,choose; // b为以选定结点为子树的深度，choose为实现多次选择输入的标志//
BiTNode* a; // a为选定结点为子树的根结点//
choose=1; // 多次选择的标志，当choose为1时运行程序，为0时结束程序// InitBiTree(T);
printf("构造空二叉树后,树空否？%d(1:是0:否), 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
e1 = Root(T);
if(e1 != Nil)
#ifdef CHAR
printf("二叉树的根为: %c\n",e1);
#endif
#ifdef INT
printf("二叉树的根为: %d\n",e1);
#endif
else
printf("树空，无根\n"); //三元组构建二叉树string x;
printf("输入格式说明：三元组（P,C,L/R）方式输入,P:parent, C: child, L/R: C is P's left child / right child, 输入end 结束输入\n");
printf("eg. the root: input ^AL, its left child is B: input ABL, its right child is C: input ACR!\n");
GetUserWord(x);
while(x!="end")
{
AddNode(T, x[0], x[1], x[2]);
GetUserWord(x);
} //输出树 PrintTreeLevel( T );
//以三元组形式输入任意二叉树（以大写字母表示结点），求以任意一选定结点为子树的深度。
while(choose) // 实现多次选择输入//
{
printf("Please select a node: ");
fflush(stdin);
scanf("%c",&node);
a= FindNode(node,T); // a为生成子树的根//
b=BiTreeDepth(a);
printf("the Depth of BiTree is : %d\n",b);
printf("\nif you want to cointue choose 1,else choose 0: ");
fflush(stdin);
scanf("%d",&choose);
}
DestroyBiTree( T );
return EXIT_SUCCESS;
}
六、心得体会
树是常用的数据结构。通过实验加深了我对树的遍历的认识，巩固了课本中所学的关于树的基本算法。按要求完成了实验内容。
通过实验，有如下几点收获和体会：
1、通过实验还提高了一点改错能力，对于一些常见问题加深了印象。
2、编程需要有耐心，尤其实在单步调试的时候，更是马虎不得，有时候关键就是那么一步，错过了就得从头来过了。编程也需要勇气，要勇于发现自己的错误，也要勇于推翻自己之前的思路，要坚信“没有最好，只有更好”。编程，最好是一鼓作气，得天天“摸摸”它，时时想着它，要是过一阵再去碰它那就得先去读懂自己的程序了，一切的一切几乎都得从头开始。编程需要细心，有时一个不注意小错误就能引出大问题。编程也需要规范，不仅为了他人能看得懂程序，也为了方便自己以后程序的更改与进一步的完善。
3、程序由算法和数据结构组成，一个好的程序不仅算法重要，数据结构的设计也很重要。
4.以前在学C语言时总觉得函数的递归调用是一样很复杂的算法，经常会理解不了而导致编程的错误。但在这次实验中，二叉树的先序、中序与后序的输出都用了递归算法。而且用起来并不复杂，这使我更进一步学习理解了函数的递归调用并得到灵活的运用。 经过本次实验基本上解决的一些所遇到的问题，我对二叉树的结构等有了较为深入的理解。我会继续我的兴趣编写程序的，相信在越来越多的尝试之后，自己会不断进步。
第二篇：C++二叉树的创建与遍历实验报告
数据结构集中上机
试验报告
学院： 计算机科学与技术 专业：计算机科学与技术
学号： 班级： 姓名：
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;
}
