北理工数据结构实验遍历二叉树

实验报告一，实验目的：·掌握二叉树的链式存储结构；·掌握构造二叉树的方法；·加深对二叉树的中序遍历的理解；二，实验方法：·用递归调用算法中序遍历二叉树。

三，实验步骤：·通过链式存储建立一颗二叉树。

·设计一个算法实现中序遍历二叉树。

四，具体实验步骤：#include<stdio.h>#include<stdlib.h>#define LEFT 0#define RIGHT 1#define TRUE 1#define FALSE 0typedef struct _BTNODE{char c;struct _BTNODE *lchild;struct _BTNODE *rchild;}BTNODE,*PBTNODE;void PrintBTree(PBTNODE p,int depth);void ConstructBTree(PBTNODE p);void InorderTraverse(PBTNODE p);void main(){PBTNODE p;p=(PBTNODE)calloc(1,sizeof(BTNODE));printf("Input the data:");ConstructBTree(p);PrintBTree(p,0);printf("Now InorderTraverse:");InorderTraverse(p);printf("\nPress any key to continue...");getchar();}void PrintBTree(PBTNODE p,int depth){int i;if(p==NULL){return;}else{for(i=0;i<depth;i++){printf("--");}printf(">");printf("%c\n",p->c);PrintBTree(p->lchild,depth+1);PrintBTree(p->rchild,depth+1);}}void ConstructBTree(PBTNODE p){int side;char c;side=LEFT;while(TRUE){scanf("%c",&c);if(c=='\n'){//printf("EOF\n");return;}// printf("%d\n",c);switch(c){case '|':break;case')':return;case',':side=RIGHT;break;case'(':if(side==LEFT){if(p->lchild==NULL){p->lchild=(PBTNODE)calloc(1,sizeof(BTNODE));}ConstructBTree(p->lchild);}else{if(p->rchild==NULL){p->rchild=(PBTNODE)calloc(1,sizeof(BTNODE));}ConstructBTree(p->rchild);}break;default:if(side==LEFT){p->lchild=(PBTNODE)calloc(1,sizeof(BTNODE));p->lchild->c=c;}else{p->rchild=(PBTNODE)calloc(1,sizeof(BTNODE));p->rchild->c=c;}}}}void InorderTraverse(PBTNODE p){if(p==NULL){return;}else{InorderTraverse(p->lchild);printf("[%c] ",p->c);InorderTraverse(p->rchild);}return;}五，实验过程：·输出：Input the date;·输入：1(2(3,4),5(6,7));·输出：Now InorderTraverse:【3】【2】【4】【1】【6】【5】【7】;六，上机实验体会：·体会到熟练掌握各种程序算法的重要性；·通过上机练习，充分理解了链式建立二叉树的算法；·形象的了解二叉树的结构，能够熟练的进行先序，中序，后序遍历二叉树。

二叉树的建立和遍历的实验报告篇一：二叉树的建立及遍历实验报告实验三：二叉树的建立及遍历【实验目的】（1）掌握利用先序序列建立二叉树的二叉链表的过程。

（2）掌握二叉树的先序、中序和后序遍历算法。

【实验内容】1. 编写程序，实现二叉树的建立，并实现先序、中序和后序遍历。

如：输入先序序列abc###de###，则建立如下图所示的二叉树。

并显示其先序序列为：abcde中序序列为：cbaed后序序列为：cbeda【实验步骤】1.打开VC++。

2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。

至此工程建立完毕。

3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。

给文件起好名字，选好路径，点OK。

至此一个源文件就被添加到了你刚创建的工程之中。

4．写好代码5．编译－＞链接－＞调试#include#include#define OK 1#define OVERFLOW -2typedef int Status;typedef char TElemType;typedef struct BiTNode{TElemType data;struct BiTNode *lchild, *rchild;}BiTNode,*BiTree;Status CreateBiTree(BiTree &T){TElemType ch;scanf("%c",&ch);if (ch=='#')T= NULL;else{if (!(T = (BiTNode *)malloc(sizeof(BiTNode))))return OVERFLOW;T->data = ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); }return OK;} // CreateBiTreevoid PreOrder(BiTree T) {if(T){printf("%c",T->data); PreOrder(T->lchild); PreOrder(T->rchild);}}void InOrder(BiTree T) {if(T){InOrder(T->lchild);printf("%c",T->data);InOrder(T->rchild);}}void PostOrder(BiTree T){if(T){PostOrder(T->lchild); PostOrder(T->rchild);printf("%c",T->data);}}void main(){BiTree T;CreateBiTree(T);printf("\n先序遍历序列:"); PreOrder(T);printf("\n中序遍历序列:"); InOrder(T);printf("\n后序遍历序列:"); PostOrder(T);}【实验心得】这次实验主要是通过先序序列建立二叉树，和二叉树的先序、中序、后续遍历算法。

本科实验报告实验名称：遍历二叉树课程名称：数据结构实验时间：任课教师：实验地点：良乡机房实验教师：实验类型：□原理验证■综合设计□自主创新学生姓名：学号/班级：组号：学院：同组搭档：专业：成绩：一、实验目的1、熟悉VC环境，学习使用C语言实现树的基本操作。

2、通过编程、上机调试，进一步理解数、二叉数、拓展二叉数的基本概念。

3、了解并熟悉二叉数的存储结构及其各种操作，掌握各种二叉数的遍历方法。

4、锻炼动手编程，独立思考的能力。

二、实验题目遍历二叉树（1）问题描述遍历二叉树：要求：请输入一棵二叉树的扩展的前序序列，经过处理后生成一棵二叉树，然后对于该二叉树输出前序、中序和后序遍历序列。

例如：124*5***3**三、实验基础知识线性表、二叉树的基本概念的熟练掌握并实际运用。

并了解创建树、遍历二叉树的思想解决问题的能力四、实验设计方法1、概要设计为实现上述程序功能，首先需要二叉树的抽象数据结构。

⑴二叉树的抽象数据类型定义为：ADT BinaryTree {数据对象D：D是具有相同特性的数据元素的集合。

数据关系R：若D=Φ，则R=Φ，称BinaryTree为空二叉树；若D≠Φ，则R={H}，H是如下二元关系；（1）在D中存在惟一的称为根的数据元素root，它在关系H下无前驱；（2）若D-{root}≠Φ，则存在D-{root}={D1,Dr}，且D1∩Dr =Φ；（3）若D1≠Φ，则D1中存在惟一的元素x1，<root,x1>∈H，且存在D1上的关系H1 ⊆H；若Dr≠Φ，则Dr中存在惟一的元素xr，<root,xr>∈H，且存在上的关系Hr ⊆H；H={<root,x1>,<root,xr>,H1,Hr}；（4）(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树；(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。

基本操作：CreateTree(&T)操作结果：按先序次序建立二叉链表表示的二叉树TPreOrderTraverse( T,Visit())初始条件：二叉树T已经存在，visit是对结点操作的应用函数操作结果：先序遍历二叉树T ，对每个结点调用visit函数仅一次；一旦visit（）失败，则操作失败。

实验目的编写一个程序，实现二叉树的先序遍历，中序遍历，后序遍历。

实验内容编程序并上机调试运行。

编写一个程序，实现二叉树的先序遍历，中序遍历，后序遍历。

编写程序/***********二叉树的遍历**************/#include<stdio.h>#include<stdlib.h>typedef struct BiTNode{char data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;/*************************************************///按先序次序构建的二叉树链表void CreatBiTree(BiTree *T){char ch;if((ch=getchar())==' ')*T=NULL;else{*T=(BiTNode*)malloc(sizeof(BiTNode));if(!(*T))exit(1);(*T)->data=ch;CreatBiTree(&(*T)->lchild);CreatBiTree(&(*T)->rchild);}}/*************************************************/ //先序遍历--递归算法void PreOrderTraverse(BiTree T){if(T){printf("%c",T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}/*************************************************/ //中序遍历--递归算法void InOrderTraverse(BiTree T){if(T){InOrderTraverse(T->lchild);printf("%c",T->data);InOrderTraverse(T->rchild);}}/*************************************************/ //后序遍历--递归算法void PostOrderTraverse(BiTree T){if(T){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf("%c",T->data);}}/*************************************************/ //main函数void main(){BiTree T;printf("请按先序次序输入二叉树中结点的值，空格字符表示空树:\n" );CreatBiTree(&T);printf("\n");printf("先序遍历为:\n");PreOrderTraverse(T);printf("\n\n");printf("中序遍历为:\n");InOrderTraverse(T);printf("\n\n");printf("后序遍历为:\n");PostOrderTraverse(T);printf("\n\n");getchar();}运行程序：结果分析：按先序输入的二叉树为ABC^^DE^G^^F^^^（^为空格）该二叉树画成树形为：其先序遍历为：ABCDEGF其中序遍历为：CBEGDFA其后序遍历为：CGEFDBA可以看出运行结果是正确的。

1．实验题目二叉树的建立与遍历[问题描述]建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。

2．需求分析（1）输入的形式和输入值的范围：以字符形式按先序遍历输入（2）输出的形式：依次按递归先序、中序、后序遍历，非递归先序、中序、后序遍历结果输出(3) 程序所能达到的功能：从键盘接受输入（先序）进行遍历（先序、中序、后序），将遍历结果打印输。

(4) 测试数据：ABCффDEфGффFффф（其中ф表示空格字符）则输出结果为先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA3．概要设计（1）struct btnode{char data; 数据struct btnode *Lchild;左子数指针struct btnode *Rchild; 右子数指针};struct btnode *createbt(struct btnode *bt )初始条件：空二叉树存在操作结果：先序建立二叉树void preOrder(struct btnode *bt)初始条件：二叉树存在递归先序遍历二叉树void preOrder1(struct btnode *bt)初始条件：二叉树存在操作结果：非递归先序遍历void midOrder(struct btnode *bt)初始条件：二叉树存在操作结果：递归中序遍历void midOrder1(struct btnode *bt)初始条件：二叉树存在操作结果：非递归中序遍历void postOrder(struct btnode *bt)初始条件：二叉树存在操作结果：递归后序遍历void postOrder1 (struct btnode *bt)初始条件：二叉树存在操作结果：非递归后序遍历void main() 主函数（2）void main() 主函数{*createbtpreOrderpreOrder1midOrdermidOrder1postOrderpostOrder1}4．详细设计struct btnode{char data;struct btnode *Lchild;struct btnode *Rchild;};struct btnode *createbt(struct btnode *bt ){ 输入结点数据c检查存储空间将c赋给结点参数p递归建立左子树递归建立右子树}void preOrder(struct btnode *bt){判断树是否为空输出根结点数data递归遍历左子树递归遍历右子树}void preOrder1(struct btnode *bt){定义栈，结点参数pWhile(栈或p是否为空){While(p!=null){输出根结点数data将根结点压栈遍历左子树}提取栈顶元素值栈顶元素出栈访问右子树}void midOrder(struct btnode *bt){判断树是否为空递归遍历左子树输出根结点数data递归遍历右子树}void midOrder1(struct btnode *bt){定义栈，结点参数pWhile(栈或p是否为空){While(p!=null){将根结点压栈遍历左子树}提取栈顶元素值输出根结点数data栈顶元素出栈访问右子树}void postOrder(struct btnode *bt){判断树是否为空递归遍历左子树递归遍历右子树输出根结点数data}void postOrder1 (struct btnode *bt){定义栈，结点参数p,prebt入栈While(栈或p是否为空){提取栈顶元素值if判断p是否为空或是pre的根结点输出根结点数data栈顶元素出栈栈顶元素p赋给pre记录else if右结点非空将右结点压栈if左结点将左结点压栈}}void main(){struct btnode *root=NULL;root=createbt(root);preOrder(root); midOrder(root); postOrder(root);preOrder1(root); midOrder1(root)；postOrder1(root);}5.调试分析（1）先序建立二叉树时，虽用到递归建左右子树，但没有把他们赋值给根节点的左右指针，造成二叉树脱节。

实验6 二叉树的遍历一、实习目的1.熟练掌握二叉树在二叉链表存储结构中的常用遍历方法：先序、中序、后序递归和非递归遍历以及二叉树的按层遍历方法。

二、实例二叉树的建立和各种遍历算法在教材中，已经有很详细的介绍。

本例题将介绍另外一种建立二叉树的算法。

同时介绍对“遍历算法”灵活应用：修改原有二叉树中结点的数值；将二叉树中每个结点的左右子树进行交换。

介绍求二叉树深度的算法。

叉树先序遍历思路有点相似。

数据的组织是先序遍历的顺序，但是当某结点的某孩子为空时以数据0来充当，也要输入。

结合右图的二叉树，其数据的输入顺序应该是：1 2 4 0 0 0 3 5 0 7 0 0 6 8 0 0 9 0 0。

若当前数据不为0，则申请一个结点存入当前数据。

如果输入0表明是空（NULL），不分配结点。

递归调用建立函数，建立当前结点的左右子树。

[源程序]#include <iostream.h>#include <conio.h>typedef int ElemType;struct NodeType //定义结点结构体{ ElemType data;NodeType *lch，*rch;};class BiTree //定义二叉树类class{public:BiTree(){root=NULL;}; //构造函数~BiTree(){destroy(root) ;} //析构函数void inorder() //中序遍历{ i norder(root); }void preordertswap() //利用先序遍历方法交换左右子树{ p reorderswap(root); }int theight() //求二叉树高度{ r eturn height(root); }void creat0();private:NodeType *root; //数据成员，树根NodeType *creat(); //建立二叉树递归方法void inorder(NodeType *p); //中序遍历void preorderswap(NodeType *p); //利用先序遍历方法交换左右子树int height(NodeType *p); //求二叉树高度递归算法void destroy(NodeType* &p); //删除二叉树所有结点};void BiTree::creat0() //建立树函数，{ cout<<"请按照树的先序遍历顺序组织数据"<<endl;cout<<"若结点信息是int，把每个结点的空孩子以0输入;"<<endl;cout<<"一个结点的二叉树11，输入：11 0 0;"<<endl;root=creat(); //调用私有creat();}NodeType * BiTree::creat() //递归建立二叉树算法{ NodeType *p; ElemType x;cout<<"\n 输入数据："; cin>>x;if( x==0) p=NULL;else { p=new NodeType; p->data=x;p->lch=creat(); //递归调用自身p->rch=creat();}return p;}void BiTree::inorder(NodeType *p) //中序遍历{ if(p != NULL){ inorder(p->lch);cout<<p->data<<" ";inorder(p->rch);}}void BiTree::preorderswap(NodeType *p) //利用先序遍历方法交换左右子树{ if(p != NULL){ NodeType *r; r=p->lch;p->lch=p->rch; p->rch=r;//上面几条语句可以认为对结点的访问（交换左右孩子）//替换了原来的：cout<<p->data<<" "; 语句preorderswap(p->lch);preorderswap(p->rch);}}void BiTree::destroy(NodeType* &p) //删除二叉树所有结点{ if(p != NULL){ destroy(p->lch);destroy(p->rch);delete p;p = NULL;}}int BiTree::height(NodeType *p) //求二叉树高度递归{ if(p == NULL) return 0;else{ int hl=height(p->lch);int hr=height(p->rch);return 1 + (hl>hr?hl:hr); //1加上hl和hr的较大值}}//---------------------------------------------------------------------------int main(){ int k; BiTree root0; //声明创建二叉树对象，调用构造函数do{ cout<<"\n\n";cout<<"\n\n 1. 建立二叉树";cout<<"\n\n 2. 交换左右子树";cout<<"\n\n 3. 求二叉树深度";cout<<"\n\n 4. 结束程序运行";cout<<"\n======================================";cout<<"\n 请输入您的选择(0,1,2,3,4):"; cin>>k;switch(k){ case 1:{ cout<<"\n s输入（0 0）结束：";root0.creat0();cout<<"\n 中先根遍历结果："; root0.inorder();} break;case 2:{ cout<<"\n 交换左右子树结果：";root0.preordertswap();cout<<"\n 中先根遍历结果：";root0.inorder();} break;case 3:{ int deep;//=root0.theight();deep=root0.theight();cout<<"\n 树的深度是："<<deep;} break;case 4: exit(0);} // switchcout<<"\n ----------------";} while(k>=0 && k<4);_getch(); return 0;}//-------------------------------------------------------三、实习题1.建立一棵二叉树，要求用先序非递归方法遍历二叉树。

TextFile中。

(4) P：打印代码文件(Print)。

将文件CodeFile以紧凑格式显示在终端上，每行50个代码。

同时将此字符形式的编码文件写入文件CodePrin中。

(5) T：打印哈夫曼树(Tree printing)。

将已在内存中的哈夫曼树以直观的方式显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。

3) 实现提示：(1) 文件CodeFile的基类型可以设为字节型。

(2) 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。

请用户键入一个选择功能符。

此功能执行完毕后再显示此菜单，直至某次用户选择了“E”为止。

(3) 在程序的一次执行过程中，第一次执行I、D或C命令之后，哈夫曼树已经在内存了，不必再读入。

每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。

三、实验过程与实验结果实验3-01：以二叉链表为存储结构，实现二叉树的创建、遍历数据结构定义：typedef struct BiTNode{char data;BiTNode *lchild, *rchild;}BiTNode;typedef BiTNode *BiTree;算法设计思路简介：本实验需要实现以下操作：二叉树的初始化、前中后序遍历等基本操作1.利用递归实现前后序遍历，思路简洁，仅需要调整递归体的执行顺序即可实现。

2.利用非递归实现中序遍历，需要利用栈操作，按照中序遍历规则将节点依次入栈后出栈实现。

算法描述：图1 中序遍历（非递归）实现算法的实现和测试结果（参考OJ）实验3-02：编写算法交换二叉树中所有结点的左、右子树数据结构定义：typedef struct BiTNode{char data;BiTNode *lchild, *rchild;}BiTNode;typedef BiTNode *BiTree;算法设计思路简介：本实验需要实现以下操作：二叉树的初始化、前中后序遍历等基本操作1.利用递归实现前后序遍历，思路简洁，仅需要调整递归体的执行顺序即可实现。

《数据结构》第六次实验报告学生学生班级学生学号指导老师一、实验容1) 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。

2) 输出树的深度，最大元，最小元。

二、需求分析遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。

递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结束一层递归调用。

直到递归全部结束。

下面重点来讲述非递归方法：首先介绍先序遍历：先序遍历的顺序是根左右，也就是说先访问根结点然后访问其左子再然后访问其右子。

具体算法实现如下：如果结点的指针不为空，结点指针入栈，输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问，如此循环，直至结点指针和栈均为空时，遍历结束。

再次介绍中序遍历：中序遍历的顺序是左根右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。

具体实现算法如下：如果结点指针不为空，结点入栈，指针指向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。

如此循环直至结点指针和栈均为空，遍历结束。

最后介绍后序遍历：后序遍历的顺序是左右根，后序遍历是比较难的一种，首先需要建立两个栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点，如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈，并赋值0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子，父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。

如果相应的标志位值为1，表示右子树已经访问完成，此时要输出相应结点的数据，同时将结点指针赋值为空，如此循环直至结点指针和栈均为空，遍历结束。

二叉树的遍历实验报告一、需求分析在二叉树的应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理，这就是二叉树的遍历问题。

对二叉树的数据结构进行定义，建立一棵二叉树，然后进行各种实验操作。

二叉树是一个非线性结构，遍历时要先明确遍历的规则，先访问根结点还时先访问子树，然后先访问左子树还是先访问有右子树，这些要事先定好，因为采用不同的遍历规则会产生不同的结果。

本次实验要实现先序、中序、后序三种遍历。

基于二叉树的递归定义，以及遍历规则，本次实验也采用的是先序遍历的规则进行建树的以及用递归的方式进行二叉树的遍历。

二、系统总框图三、各模块设计分析（1）建立二叉树结构建立二叉树时，要先明确是按哪一种遍历规则输入，该二叉树是按你所输入的遍历规则来建立的。

本实验用的是先序遍历的规则进行建树。

二叉树用链表存储来实现，因此要先定义一个二叉树链表存储结构。

因此要先定义一个结构体。

此结构体的每个结点都是由数据域data 、左指针域Lchild 、右指针域Rchild 组成，两个指针域分别指向该结点的左、右孩子，若某结点没有左孩子或者右孩子时，对应的指针域就为空。

最后，还需要一个链表的头指针指向根结点。

要注意的是，第一步的时候一定要先定义一个结束标志符号，例如空格键、＃等。

当它遇到该标志时，就指向为空。

建立左右子树时，仍然是调用create（）函数，依此递归进行下去，直到遇到结束标志时停止操作。

（2）输入二叉树元素输入二叉树时，是按上面所确定的遍历规则输入的。

最后，用一个返回值来表示所需要的结果。

（3）先序遍历二叉树当二叉树为非空时，执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。

（4）中序遍历二叉树当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。

（5）后序遍历二叉树当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。

二叉树的创建与遍历实验题目：二叉树的创建与遍历实验目的：根据二叉树先序、中序遍历结果创建二叉树，并对该二叉树进行后序遍历1 需求分析本实验要求根据二叉树先序、中序遍历结果创建二叉树，并进行后序遍历。

1.输入形式及范围：形式：以两个字符串分别表示先序和中序遍历结果范围：字母字符串2.输出形式由先序、中序遍历结果所确定的二叉树后序遍历结果3.功能利用二叉树先序、中序遍历结果确定二叉树，并对该二叉树进行后序遍历4.测试数据Please enter the Binary Tree’s preorder:ABDEHICFGPlease enter the Binary Tree’s inorder:DBHEIAFCG（预设结果）The Binary Tree’s postorder is:DHIEBFGCAP2 设计概要2.1 问题分析通过先序、中序遍历（或后序、中序）结果能够唯一确定一棵二叉树。

比较各元素在先序、中序中的不同位置，归纳其中的规律，即可创建出两者唯一确定的二叉树。

程序的核心算法就是通过分别读取一个元素在两种序列中的不同序号来确定其与其他元素的位置关系（即亲子关系）。

在算法的实现中，利用栈存储子树的根结点地址是非常关键的操作。

此外，程序的基本操作包括结点的初始化、出入栈及输入输出函数。

2.2 程序模块程序包括三个主要模块：1）主函数2）二叉树创建函数3）后序遍历函数下面将逐一叙述各模块：主函数执行一系列提示信息连接主要模块●二叉树创建函数这是程序的核心，根据问题分析，我们设计具体的算法如下：输入先序、中序遍历结果，以先序遍历结果为基准，逐一读取字符串中元素；对于每个读取的元素，确定其在中序遍历结果中的序号，申请新结点存储该元素并进行以下选择操作：若栈空，则该元素必为树根，元素的地址及在中序中的序号入栈若该元素中序序号小于栈顶元素序号，即为栈顶元素左子，将前一元素左指针指向该元素地址，元素入栈若该元素中序序号大于栈顶元素序号，栈顶元素退栈，直至该元素中序学号小于栈顶元素序号，该元素即为最后出栈元素右子。

二叉树的遍历实验报告一、实验目的1.了解二叉树的存储结构。

2.掌握二叉树的遍历方式。

二、实验原理1.二叉树的定义：二叉树是一种特殊的树形结构，它的每个结点最多只能有两个子结点，分别称为左子结点和右子结点。

一般有两种存储方式，分别是顺序存储和链式存储。

其中顺序存储需要用到数组，而链式存储则需要用到指针。

遍历二叉树的方式主要有三种，分别是前序遍历、中序遍历和后序遍历。

其中前序遍历是先遍历根节点，然后遍历左子树和右子树；中序遍历是先遍历左子树，然后遍历根节点和右子树；后序遍历是先遍历左子树和右子树，然后遍历根节点。

三、实验步骤typedef struct binaryTree {char data; //数据域struct binaryTree *left; //左子树struct binaryTree *right; //右子树} BTree;2.创建二叉树：BTree *createBTree(BTree *bt) {char ch;scanf("%c", &ch);if (ch == '#') {bt = NULL;}else {bt = (BTree*)malloc(sizeof(BTree));bt->data = ch;bt->left = createBTree(bt->left); //递归创建左子树bt->right = createBTree(bt->right); //递归创建右子树}return bt;}3.前序遍历：6.测试代码：四、实验结果分析测试所得结果如下：输入字符：AB#C##D#F##前序遍历结果：ABCFD中序遍历结果：BACFD后序遍历结果：BCFD A五、实验总结通过本次实验，我了解了二叉树的基本概念和存储结构，掌握了二叉树的前、中、后序遍历方式的实现方法。

这些知识对于我以后学习数据结构和算法，具有重要意义，对我的编程能力的提升也是有益的。

《数据结构》第六次实验报告学生姓名学生班级学生学号指导老师一、实验内容1) 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。

2) 输出树的深度，最大元，最小元。

二、需求分析遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。

递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结束一层递归调用。

直到递归全部结束。

下面重点来讲述非递归方法：首先介绍先序遍历：先序遍历的顺序是根左右，也就是说先访问根结点然后访问其左子再然后访问其右子。

具体算法实现如下：如果结点的指针不为空，结点指针入栈，输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问，如此循环，直至结点指针和栈均为空时，遍历结束。

再次介绍中序遍历：中序遍历的顺序是左根右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。

具体实现算法如下：如果结点指针不为空，结点入栈，指针指向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。

如此循环直至结点指针和栈均为空，遍历结束。

最后介绍后序遍历：后序遍历的顺序是左右根，后序遍历是比较难的一种，首先需要建立两个栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点，如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈，并赋值0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子，父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。

数据结构二叉树遍历实验报告数据结构二叉树遍历实验报告1. 实验目的本实验旨在通过实现二叉树的前序、中序和后序遍历算法，加深对二叉树遍历的理解，并验证算法的正确性。

2. 实验原理2.1 二叉树二叉树是一种特殊的树状数据结构，它的每个节点最多只能有两个子节点。

二叉树可以为空树，也可以是由根节点、左子树和右子树组成的非空树。

2.2 遍历算法二叉树的遍历算法包括前序遍历、中序遍历和后序遍历。

- 前序遍历：先访问根节点，然后依次递归访问左子树和右子树。

- 中序遍历：先递归访问左子树，然后访问根节点，最后递归访问右子树。

- 后序遍历：先递归访问左子树，然后递归访问右子树，最后访问根节点。

3. 实验过程3.1 数据结构设计首先，我们需要设计表示二叉树的数据结构。

在本次实验中，二叉树的每个节点包含三个成员变量：值、左子节点和右子节点。

我们可以使用面向对象编程语言提供的类来实现。

具体实现如下：```pythonclass TreeNode:def __init__(self, val=0, left=None, right=None): self.val = valself.left = leftself.right = right```3.2 前序遍历算法前序遍历算法的实现主要包括以下步骤：1. 若二叉树为空，则返回空列表。

2. 创建一个栈，用于存储遍历过程中的节点。

3. 将根节点入栈。

4. 循环执行以下步骤，直到栈为空：- 弹出栈顶节点，并将其值添加到结果列表中。

- 若当前节点存在右子节点，则将右子节点压入栈。

- 若当前节点存在左子节点，则将左子节点压入栈。

具体实现如下：```pythondef preorderTraversal(root):if not root:return []stack = []result = []stack.append(root)while stack:node = stack.pop()result.append(node.val)if node.right:stack.append(node.right)if node.left:stack.append(node.left)return result```3.3 中序遍历算法中序遍历算法的实现主要包括以下步骤：1. 若二叉树为空，则返回空列表。

二叉树的创建与遍历的实验总结引言二叉树是一种重要的数据结构，在计算机科学中有着广泛的应用。

了解二叉树的创建和遍历方法对于数据结构的学习和算法的理解至关重要。

本文将对二叉树的创建和遍历进行实验，并总结相应的经验和思考。

二叉树的定义在开始实验之前，我们首先需要了解二叉树的定义和基本概念。

二叉树是一种每个节点最多拥有两个子节点的树形结构。

每个节点包含一个值和指向其左右子节点的指针。

根据节点的位置，可以将二叉树分为左子树和右子树。

创建二叉树二叉树的创建可以采用多种方法，包括手动创建和通过编程实现。

在实验中，我们主要关注通过编程方式实现二叉树的创建。

1. 递归方法递归是一种常用的创建二叉树的方法。

通过递归，我们可以从根节点开始，逐层创建左子树和右子树。

具体步骤如下：1.创建一个空节点作为根节点。

2.递归地创建左子树。

3.递归地创建右子树。

递归方法的代码实现如下所示：class TreeNode:def __init__(self, value):self.value = valueself.left = Noneself.right = Nonedef create_binary_tree(values):if not values:return None# 使用队列辅助创建二叉树queue = []root = TreeNode(values[0])queue.append(root)for i in range(1, len(values)):node = TreeNode(values[i])# 当前节点的左子节点为空，则将新节点作为左子节点if not queue[0].left:queue[0].left = node# 当前节点的右子节点为空，则将新节点作为右子节点elif not queue[0].right:queue[0].right = node# 当前节点的左右子节点已经齐全，可以从队列中删除该节点queue.pop(0)# 将新节点添加到队列中，下一次循环时可以使用该节点queue.append(node)return root2. 非递归方法除了递归方法，我们还可以使用非递归方法创建二叉树。

数据结构（双语）——项目文档报告用递归、非递归两种方法遍历二叉树专业：计算机科学与技术班级：15计算机1班指导教师：苏亚光姓名：学号：目录一、设计思想 (3)二、算法流程图 (4)三、源代码 (7)四、运行结果 (12)五、遇到的问题及解决 (13)六、心得体会 (14)一、设计思想程序代码是用两种算法实现二叉树的遍历，并输出遍历后的值。

第一种算法是递归实现二叉树的遍历首先对于先序遍历，若二叉树为空，则空操作；否则，先访问根结点，然后先序遍历左子树，再先序遍历右子树。

对于中序遍历，若二叉树为空，则空操作；否则，先中序遍历左子树，然后访问根节点，在中序遍历右子树。

对于后续遍历，若二叉树为空，则空操作；否则，先后续遍历左子树，然后后续遍历右子树，在访问跟结点。

第二种算法是非递归实现二叉树的遍历首先对于先序非递归遍历，先序遍历是借用栈来实现的。

先声明并初始化一个栈。

首先站在根节点上，对于根节点直接访问它，即打印它的data，再将其压入栈中，再判断栈stack是否为空，如果stack 为空，则循环结束，遍历结束；如果不为空，则访问该根结点。

对于其它结点上如果它有左子，则访问它的左子，即打印其左子中成员data 的值，然后再将该左子压入栈中；如果该结点没有左子，则弹出栈顶元素，站在其右子所在的结点上，再对当前所在的结点是否有左子进行判断，此时进入了一个循环。

循环结束的条件是栈stack 和最后所在结点也为空。

此时，所输出的结果即为先序遍历的结果。

对于中序非递归遍历，也是借用一个栈来实现的，先声明并初始化一个栈，站到一个结点a 上，如果当前结点a 有左子b，则将其左子b 入栈，如果其左子b 还有左子c 也将当前所站的结点b 入栈，循环此过程直到遇到没有左子的结点p，此时弹出栈顶元素p，并访问它，即打印p 结点的data，然后判断p 结点的成员指针变量right ，把right 当成第一个开始的结点进行处理，直到最后栈为空且当前所站得结点为NULL ，则中序遍历结束。

实验⼋⼆叉树的遍历实验⼋⼆叉树的遍历⼀、【实验⽬的】1、掌握⼆叉树遍历的基本⽅法（前序、中序、后序）2、掌握递归⼆叉树遍历算法3、掌握⾮递归的⼆叉树遍历算法⼆、【实验内容】1、利⽤⾮递归实现前序遍历算法BiTree.htypedef struct Node{ElemType data; /*数据域*/struct Node *leftChild; /*左⼦树指针*/struct Node *rightChild; /*右⼦树指针*/}BiTreeNode; /*结点的结构体定义*/ /*初始化创建⼆叉树的头结点*/ void Initiate(BiTreeNode **root){*root = (BiTreeNode *)malloc(sizeof(BiTreeNode));(*root)->leftChild = NULL;(*root)->rightChild = NULL;}void Destroy(BiTreeNode **root){if((*root) != NULL && (*root)->leftChild != NULL)Destroy(&(*root)->leftChild);if((*root) != NULL && (*root)->rightChild != NULL)Destroy(&(*root)->rightChild);free(*root);}/*若当前结点curr⾮空，在curr的左⼦树插⼊元素值为x的新结点*/ /*原curr所指结点的左⼦树成为新插⼊结点的左⼦树*//*若插⼊成功返回新插⼊结点的指针，否则返回空指针*/ BiTreeNode *InsertLeftNode(BiTreeNode *curr, ElemType x){BiTreeNode *s, *t;if(curr == NULL) return NULL;t = curr->leftChild; /*保存原curr所指结点的左⼦树指针*/ s = (BiTreeNode *)malloc(sizeof(BiTreeNode)); s->data = x;s->leftChild = t; /*新插⼊结点的左⼦树为原curr的左⼦树*/ s->rightChild = NULL;curr->leftChild = s; /*新结点成为curr的左⼦树*/ return curr->leftChild; /*返回新插⼊结点的指针*/}/*若当前结点curr⾮空，在curr的右⼦树插⼊元素值为x的新结点*//*原curr所指结点的右⼦树成为新插⼊结点的右⼦树*//*若插⼊成功返回新插⼊结点的指针，否则返回空指针*/BiTreeNode *InsertRightNode(BiTreeNode *curr, ElemType x){BiTreeNode *s, *t;if(curr == NULL) return NULL;t = curr->rightChild; /*保存原curr所指结点的右⼦树指针*/ s = (BiTreeNode *)malloc(sizeof(BiTreeNode)); s->data = x;s->rightChild = t; /*新插⼊结点的右⼦树为原curr的右⼦树*/ s->leftChild = NULL;curr->rightChild = s; /*新结点成为curr的右⼦树*/return curr->rightChild; /*返回新插⼊结点的指针*/}/*若curr⾮空，删除curr所指结点的左⼦树*//*若删除成功返回删除结点的双亲结点指针，否则返回空指针*/BiTreeNode *DeleteLeftTree(BiTreeNode *curr){if(curr == NULL || curr->leftChild == NULL) return NULL;Destroy(&curr->leftChild);curr->leftChild = NULL;return curr;}/*若curr⾮空，删除curr所指结点的右⼦树*//*若删除成功返回删除结点的双亲结点指针，否则返回空指针*/BiTreeNode *DeleteRightTree(BiTreeNode *curr){if(curr == NULL || curr->rightChild == NULL) return NULL;Destroy(&curr->rightChild);curr->rightChild = NULL;SeqStack.htypedef struct{DataType stack[MaxStackSize];int top;} SeqStack;void StackInitiate(SeqStack *S) /*初始化顺序堆栈S*/ {S->top = 0; /*定义初始栈顶下标值*/ }int StackNotEmpty(SeqStack S)/*判顺序堆栈S⾮空否，⾮空则返回1，否则返回0*/{if(S.top <= 0) return 0;else return 1;}int StackPush(SeqStack *S, DataType x)/*把数据元素值x压⼊顺序堆栈S，⼊栈成功则返回1，否则返回0 */ {if(S->top >= MaxStackSize){printf("堆栈已满⽆法插⼊! \n");return 0;}else{S->stack[S->top] = x;S->top ++;return 1;}}int StackPop(SeqStack *S, DataType *d)/*弹出顺序堆栈S的栈顶数据元素值到参数d ，出栈成功则返回1，否则返回0*/ { if(S->top <= 0){printf("堆栈已空⽆数据元素出栈! \n");else{S->top --;*d = S->stack[S->top];return 1;}}int StackTop(SeqStack S, DataType *d)/*取顺序堆栈S的当前栈顶数据元素值到参数d ，成功则返回1，否则返回0*/ { if(S.top <= 0){printf("堆栈已空! \n");return 0;}else{*d = S.stack[S.top - 1];return 1;}}主程序#include /*该⽂件包含pringtf()等函数*/ #include#define MaxStackSize 100 /*定义MaxSize为100*/ typedef char ElemType ; #include "BiTree.h"typedef BiTreeNode * DataType ;#include "SeqStack.h"Void PreOrderByStack(BiTreeNode *root){//独⽴编写}void main(void){BiTreeNode *root, *p, *pp;Initiate(&root);p = InsertLeftNode(root, 'A');p = InsertLeftNode(p, 'B');p = InsertLeftNode(p, 'D');p = InsertRightNode(p, 'G');p = InsertRightNode(root->leftChild, 'C'); pp = p;InsertLeftNode(p, 'E'); InsertRightNode(pp, 'F'); PreOrderByStack(root->leftChild); Destroy(&root);}2、编写求⼆叉树中叶结点个数的函数三、【实验源代码】四、【实验结果】五、【实验⼼得】。

实现二叉树的各种遍历算法实验报告一实验题目: 实现二叉树的各种遍历算法二实验要求:2.1:（1）输出二叉树 b（2）输出H节点的左右孩子节点值（3）输出二叉树b 的深度（4）输出二叉树 b的宽度（5）输出二叉树 b的节点个数（6）输出二叉树 b的叶子节点个数（7）释放二叉树 b2.2：（1）实现二叉树的先序遍历（2）实现二叉树的中序遍历（3）实现二叉树的后序遍历三实验内容:3.1 树的抽象数据类型:ADT Tree{数据对象D：D是具有相同特性的数据元素的集合。

数据关系R：若D为空集，则称为空树；若D仅含有一个数据元素，则R为空集，否则R={H}，H是如下二元关系：(1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2) 若D-{root}≠NULL，则存在D-{root}的一个划分D1,D2,D3, …,Dm(m>0)，对于任意j≠k(1≤j,k≤m)有Dj∩Dk=NULL,且对任意的i(1≤i≤m)，唯一存在数据元素xi∈Di有<root,xi>∈H;(3) 对应于D-{root}的划分，H-{<root,xi>,…,<root,xm>}有唯一的一个划分H1，H2,…,Hm(m>0)，对任意j≠k(1≤j,k≤m)有Hj∩Hk=NULL，且对任意i(1≤i≤m),Hi是Di上的二元关系，(Di,{Hi})是一棵符合本定义的树，称为根root的子树。

基本操作P：InitTree(&T);操作结果：构造空树T。

DestroyTree(&T);初始条件：树T存在。

操作结果：销毁树T。

CreateTree(&T,definition);初始条件：definition给出树T的定义。

操作结果：按definition构造树T。

ClearTree(&T);初始条件：树T存在。

操作结果：将树T清为空树。

TreeEmpty(T);初始条件：树T存在。

实验七二叉树的建立及遍历操作实验预备知识：1、熟练指针进行数据访问。

2、掌握二叉树的存储结构和处理方法。

3、掌握二叉树三种遍历的算法。

一、实验目的1、熟悉二叉树的存贮结构及遍历方式，掌握有关算法的实现。

2、能够利用二叉树解决具体问题。

二、实验要求1、要求采用二叉树链表作为存贮结构，完成二叉树的建立、先序、中序、和后序遍历的操作。

其中先序遍历和后序遍历采用递归算法，中序遍历采用非递归算法。

2、输入数据：树中每个结点的数据类型设定为字符型。

三、实验内容1、在自己的U盘的“姓名+学号”文件夹中创建“实验6”文件夹，本次实验的所有程序和数据都要求存储本到文件夹中。

2、实验如下二叉树处理函数。

建树子函数先序遍历子函数中序遍历子函数后序遍历子函数#include <stdlib.h>#include <stdio.h>typedef struct BiTNode{ char data;struct BiTNode *lchild,*rchild;}BiTNode,*shenyang;/*定义二叉链表结点结构*/void Createshenyang(shenyang *sy){/* 输入二叉树的先序遍历序列，创建二叉链表*/char ch;if ((ch=getchar())==' ') *sy=NULL;else{ *sy=(BiTNode*)malloc(sizeof(BiTNode));(*sy)->data=ch;printf("当前根结点:%c\n",(*sy)->data);Createshenyang(&(*sy)->lchild);/* 建左子树*/Createshenyang(&(*sy)->rchild);/* 建右子树*/}}void PreOrder(shenyang sy){/* 对二叉树进行先序遍历*/if(sy){ printf("%c",sy->data);PreOrder(sy->lchild);PreOrder(sy->rchild);}}void InOrder(shenyang sy){/* 对二叉树进行中序遍历*/if(sy){ InOrder(sy->lchild);printf("%c",sy->data);InOrder(sy->rchild);}}void PostOrder(shenyang sy){/* 对二叉树进行后序遍历*/if(sy){ PostOrder(sy->lchild);PostOrder(sy->rchild);printf("%c",sy->data);}}void main(){ shenyang sy=NULL;printf("请输入二叉树的结点:\n");Createshenyang(&sy);printf("先序遍历:");PreOrder(sy); /printf("\n");printf("中序遍历:");InOrder(sy);printf("\n后序遍历:");PostOrder(sy);printf("\n");}中序线索化二叉树#include<stdio.h>#include<malloc.h>#define NULL 0#define LEN_T sizeof(shenyang)#define LEN_S 50typedef struct shenyang{ char data;struct shenyang *lchild,*rchild;int lt,rt;}shenyang,*syTree;void CreateTree(syTree *T){ char c;c=getchar();if (c=='#')(*T)=NULL;else{(*T)=(syTree)malloc(LEN_T);(*T)->lt=0;(*T)->rt=0;CreateTree(&(*T)->lchild);(*T)->data=c;CreateTree(&(*T)->rchild);}}syTree XianSuo(syTree *T){ syTree t,pr,p,Stack[LEN_S];int top=0;t=(syTree)malloc(LEN_T);t->rchild=t;if((*T)==NULL)t->lchild=t;else{t->lchild=(*T);p=(*T);pr=t;do{while(p){ Stack[top++]=p;p=p->lchild;}if(top>0){ p=Stack[--top];printf("%2c",p->data);if(p->lchild==NULL){p->lt=1; p->lchild=pr;}if(pr->rchild==NULL){ pr->rt=1;pr->rchild=p;} pr=p;p=p->rchild;}}while(p || top>0);pr->rt=1;pr->rchild=t;t->rchild=pr;}printf("\n");return t;}void main(){ syTree T=NULL;printf("先序输入二叉树:\n");CreateTree(&T);printf("中序遍历二叉树并线索化:\n");T=XianSuo(&T);}。