二叉树的建立和遍历的实验报告

二叉树的建立和遍历的实验报告篇一：二叉树的建立及遍历实验报告实验三：二叉树的建立及遍历【实验目的】（1） 掌握利用先序序列建立二叉树的二叉链表的过程。（2） 掌握二叉树的先序、中序和后序遍历算法。【实验内容】编写程序，实现二叉树的建立，并实现先序、中序和后序遍历。如：输入先序序列abc###de###，则建立如下图所示的二叉树。并显示其先序序列为：abcde中序序列为：cbaed后序序列为：cbeda【实验步骤】打开VC++。建立工程：点File->New，选Project标签，在列表中选Win32ConsoleApplication，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。创建源文件或头文件：点File->New，选File标签，在列表里选C++SourceFileo给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。写好代码编译一〉链接一〉调试#include#include#defineOK1#defineOVERFLOW-2typedefintStatus;typedefcharTElemType;typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;StatusCreateBiTree(BiTree&T){TElemTypech;scanf(〃%c〃,&ch);if(ch==，#，)T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))returnOVERFLOW;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}returnOK;}//CreateBiTreevoidPreOrder(BiTreeT){if(T){printf(〃%c〃,T->data);PreOrder(T->lchild);PreOrder(T->rchild);}}voidInOrder(BiTreeT){if(T){InOrder(T->lchild);printf(〃%c〃,T->data);InOrder(T->rchild);}}voidPostOrder(BiTreeT){if(T){PostOrder(T->lchild);PostOrder(T->rchild);printf(〃%c〃,T->data);}}voidmain(){BiTreeT;CreateBiTree(T);printf("\n先序遍历序列:");PreOrder(T);printf("\n中序遍历序列：")；InOrder(T);printf("\n后序遍历序列：")；PostOrder(T);}【实验心得】这次实验主要是通过先序序列建立二叉树，和二叉树的先序、中序、后续遍历算法。通过这次实验，我巩固了二叉树这部分知识，从中体会理论知识的重要性。在做实验之前，要充分的理解本次实验的理论依据，这样才能达到事半功倍的效果。如果在没有真正理解实验原理之盲目的开始实验，只会浪费时间和精力。例如进行二叉树的遍历的时候，要先理解各种遍历的特点。先序遍历是先遍历根节点，再依次先序遍历左右子树。中序遍历是先中序遍历左子树，再访问根节点，最后中序遍历右子树。而后序遍历则是先依次后续遍历左右子树，再访问根节点。掌握了这些，在实验中我们就可以融会贯通，举一反三。所以，这次实验让我懂得了理论知识的重要性，只有领悟了最基本的知识，在实验过程中我们才能够独立的思考，文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.大胆的推断，不断的创新，进而提高动手能力。篇二：C++二叉树的创建与遍历实验报告二叉树的创建与遍历一、 实验目的学会实现二叉树结点结构和对二叉树的基本操作。掌握对二叉树每种操作的具体实现，学会利用递归和非递归方法编写对二叉树这种递归数据结构进行处理的算法。二、 实验要求认真阅读和掌握和本实验相关的教材内容。编写完整程序完成下面的实验内容并上机运彳丁。整理并上交实验报告。三、 实验内容1.编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归和非递归遍历算法（前序、中序、后序）对这棵二叉树进行遍历。四、实验步骤源程序代码1#include#includeusingnamespacestd;templatestructBinTreeNode//二叉树结点类定义{Tdata;//数据域BinTreeNode*leftChild,*rightChild;//左子女、右子女域BinTreeNode(Tx=T(),BinTreeNode*l=NULL,BinTreeNode* r =NULL):data(x),leftChild(l),rightChild(r){}//可选择参数的默认构造函数};// templatevoidPreOrder_2(BinTreeNode*p)//非递归前序遍历{stack*>S;}while(p!=NULL||!S.empty()){} }p=S.top();S.pop();p=p->rightChild;//遍历指针进至U右子女结点while(p!=NULL){coutdata;//访问根结点}if(!S.empty())//栈不空时退栈{S.push(p);p=p->leftChild;//遍历指针进到左子女结点// templatevoidInOrder_2(BinTreeNode*p)//非递归中序遍历{}stack*>S;do{}while(p!=NULL||!S.empty());while(p!=NULL)//遍历指针未到最左下的结点，不空 {}if(!S.empty())//栈不空时退栈{}p=S・top();S.pop();coutdata; p=p->rightChild;S.push(p);p=p->leftChild;// templatevoidPostOrder_2(BinTreeNode*p)//非递归后序遍历{}templatevoidInOrder_1(BinTreeNode*subTree){//递归函数：中序次序遍历以subTree为根的子树。}if(subTree!=NULL)//NULL是递归终止条件{}coutdata;//访问根结点InOrder_1(subTree->rightChild);//中序遍历根的右子树InOrder_1(subTree->leftChild);//中序遍历根的左子树stack*>S;stacktag;//定义一个新的栈用来保存tag域判别根结点的左右子树是否均遍历过while(p!=NULL||!S.empty())//左子树经过结点加L进栈{}while(p!=NULL){}while(!S.empty()&&tag.top()==1){ }if(!S.empty()){ }elsebreak;tag.pop();tag.push(l);//遍历右子树前的现场保护，修改栈顶tag为，遍历右子树p=S.top();//取栈顶保存的指针p=p->rightChild;p=S.top();S.pop();tag.pop();coutdata;//最后访问根结点。S.push(p);//首先将t和tag为入栈，遍历左子树p=p->leftChild;tag.push(0);//遍历左子树前的现场保护templatevoidPreOrder_1(BinTreeNode*subTree){//递归函数：前序遍历以subTree为根的二叉树。}templatevoidPostOrder_1(BinTreeNode*subTree){//递归函数：后序次序遍历以subTree为根的子树。}// templatevoidCreateBinTree(BinTreeNode*&subTree){//递归方式建立二叉树if(item!=-1){}elsesubTree=NULL;//封闭指向空子树的指针subTree=newBinTreeNode();if(subTree == NULL) {}CreateBinTree(subTree->leftChild);//递归建立左子树CreateBinTree(subTree->rightChild);//递归建立右子树cerr>item;}coutdata;//访问根结点if(subTree!=NULL)//NULL是递归终止条件{PostOrder_1(subTree->leftChild);//后序遍历根的左子树PostOrder_1(subTree->rightChild);//后序遍历根的右子树coutdata;//访问根结点}PreOrder_1(subTree->leftChild);//前