数据结构试验报告用先序中序建立二叉树后序遍历非递归

树和图的遍历实验报告2011-4-9实验题目：树和图的遍历实验目的：1.实现二叉树的建立与先序，中序，后序，层次遍历2.选择建立图的类型；根据所选择的类型用邻接矩阵的存储结构构建图；对图进行深度优先搜索和广度优先搜索；实验内容:一、算法描述：（1）二叉树的建立要建立一棵树就要有根节点和两棵子树。

两棵子树的建立同样需要这样的过程。

建立二叉树的过程也是遍历树的过程，实验要求以前序遍历的方式输入数据，因此我们也应按前序遍历的顺序，动态申请存储空间的方式建立这棵树并返回根节点的指针。

BiTNode *CreateBiTree(BiTNode *T){char ch;if((ch=getchar())==' ') T=NULL;else if(ch!='\n'){if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))exit(1);T->data=ch;T->lchild=CreateBiTree(T->lchild);T->rchild=CreateBiTree(T->rchild);}return T;}（2）二叉树的遍历遍历作为二叉树所有操作的基础，因此我把它放在二叉树建立的前面。

前序遍历：即按照根节点，左子树，右子树的顺序访问。

具体操作：遇到节点，立即打印根节点的值，然后访问左子树，再访问右子树。

对左子树和右子树的访问也进行相同的操作。

void PreOrderTraverse(BiTree T){if(T){putchar(T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}同理，易得中序遍历，后序遍历的操作。

//中序遍历二叉树void InOrderTraverse(BiTree T){if(T){InOrderTraverse(T->lchild);putchar(T->data);InOrderTraverse(T->rchild);}}//后序遍历二叉树void PostOrderTraverse(BiTree T){if(T){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);putchar(T->data);}}层次遍历：先访问的节点，其孩子节点也必然优先访问，这就用到了队列的思想。

二叉树创建、前序遍历、中序遍历、后序遍历的递归与非递归实现以及层次遍历二叉树的创建：#include"stdio.h"typedef char ElemType;#define MAXNUM 150/* 二叉树结点定义 */typedef struct BTNode{ElemType data;/* data field */struct BTNode *lchild;struct BTNode *rchild;} BTNode;/* 辅助的二叉树索引数组 */BTNode *p[MAXNUM+1];/* 根据用户输入创建二叉树 *//* 二叉树结点信息：数据域，以及在完全二叉树中的索引值 */BTNode *Create_BiTree(void){BTNode* t =NULL;int i;int j;char ch;printf("\n enter i, ch :");scanf("%d,%c",&i,&ch);while(i != 0 && ch !='#'){BTNode* s =(BTNode*)malloc(sizeof(BTNode)); s->data = ch;s->lchild = s->rchild =NULL;p[i]= s;if( i == 1 )t = s;else{j = i/2;if( i%2 == 0 )p[j]->lchild = s;elsep[j]->rchild = s;}printf("\n enter i, ch :");scanf("%d,%c",&i,&ch);}return t;}int main(void){BTNode* t;t = Create_BiTree();/*preorder(t);printf(" preorder\n");preorder_recursive(t);printf(" preorder_recursive\n");Inorder(t);printf(" Inorder\n");Inorder_recursive1(t);printf(" Inorder_recursive1\n"); Inorder_recursive2(t);printf(" Inorder_recursive2\n");Postorder(t);printf(" Postorder\n");Postorder_recursive(t);printf(" Postorder_recursive\n");LevelOrder(t);printf(" LevelOrder\n");*/getchar();getchar();return 0;}二叉树的前序遍历，递归、非递归的实现：/* 前序遍历的递归实现 */void preorder(BTNode *bt){if(bt){printf("%c ",bt->data);preorder(bt->lchild);preorder(bt->rchild);}}/* 前序遍历的非递归实现 */void preorder_recursive(BTNode *bt){BTNode* p;BTNode* s[MAXNUM+1];/* 辅助的模拟栈 */ int top;p=bt;top=-1;while(p||top !=-1){if(p){printf("%c ",p->data);++top;二叉树的中序遍历，递归、非递归的实现：BTNode* p,*s[MAXNUM+1];int top;p=bt;top=-1;while(p||top !=-1){if(p){++top;s[top]=p;p=p->lchild ;}/*p移向左孩子*/else/*栈非空*/{p=s[top];--top;printf("%c ",p->data); p=p->rchild;}}}/* 中序遍历的非递归实现 */void Inorder_recursive2(BTNode *bt){BTNode* p,*s[MAXNUM+1];int top;p=bt;top=-1;while(p||top !=-1){if(p && p->lchild){++top;s[top]= p;p = p->lchild;}else{if(p)printf("%c ", p->data);if(p && p->rchild ){p = p->rchild;}else if( top >= 0){p = s[top];top--;printf("%c ", p->data); p = p->rchild;}elsebreak;}}}二叉树的后序遍历，递归、非递归的实现：/* 后序遍历的递归实现 */void Postorder(BTNode *bt){if(bt){Postorder(bt->lchild);Postorder(bt->rchild);printf("%c ",bt->data);}}/* 后序遍历的非递归实现 */void Postorder_recursive(BTNode *pt) {BTNode *s[MAXNUM+1];int top =-1;BTNode *p = pt;BTNode *pre =NULL;while( p || top !=-1 ){if(p ){++top;s[top]= p;p = p->lchild;pre = p;}else{p = s[top];// --top;if( p->rchild ==NULL|| p->rchild == pre ){p = s[top];--top;printf("%c ", p->data);pre =p;p =NULL;}else{p = p->rchild;pre = p;}}}}层次遍历：{BTNode*queue[100];int front=0,rear=0;if(bt==NULL)return;queue[rear]=bt;rear++;do{printf("%c ",queue[front]->data);/*访问队首结点的数据域*/if(queue[front]->lchild!=NULL)/*将队首结点的左孩子结点入队列*/{queue[rear]=queue[front]->lchild; rear++;}if(queue[front]->rchild!=NULL)/*将队首结点的右孩子结点入队列*/{queue[rear]=queue[front]->rchild; rear++;}front++;。

实践三：树的应用1.实验目的要求通过本实验使学生深刻理解二叉树的性质和存储结构，熟练掌握二叉树的遍历算法。

认识哈夫曼树、哈夫曼编码的作用和意义。

实验要求：建一个二叉树并按照前序、中序、后序三种方法遍历此二叉树，正确调试本程序。

能够建立一个哈夫曼树，并输出哈夫曼编码，正确调程序。

写出实验报告。

2.实验主要内容2.1 对二叉树进行先序、中序、后序递归遍历，中序非递归遍历。

2.2 根据已知的字符及其权值，建立哈夫曼树，并输出哈夫曼编码。

3．实验步骤2.1实验步骤●输入p127二叉链表的定义●录入调试p131算法6.4，实现二叉树的构造函数●编写二叉树打印函数，可以通过递归算法将二叉树输出为广义表的形式，以方便观察树的结构。

●参考算法6.1，实现二叉树的前序、中序和后序的递归遍历算法。

为简化编程，可以将visit函数直接使用printf函数输出结点内容来代替。

#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define OK 1#define ERROR 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef char TElemType;typedef char Status;// 构造书的结构体typedef struct BiTNode{TElemType data;struct BiTNode *lchild, *rchild;}BiTNode, *BiTree;// 构造栈的结构体typedef BiTree SElemType;typedef struct{SElemType *base;SElemType *top;int stacksize;}SqStack;Status InitStack(SqStack &S){//构造一个空栈S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); if(!S.base)exit(-2);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;}Status StackEmpty(SqStack S){//若栈S为空栈，则返回TRUE,否则返回FALSEif(S.top==S.base)return 1;elsereturn 0;}Status Push(SqStack &S,SElemType e){//插入元素e为新的栈顶元素if(S.top - S.base >= S.stacksize){S.base = (SElemType *)realloc(S.base,(S.stacksize + STACKINCREMENT) * sizeof(SElemType));if(!S.base)exit(-2);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;}*S.top++ = e;return OK;}Status Pop(SqStack &S,SElemType &e){//若栈不空，则删除S的栈顶元素，用e返回其值并返回OK,否则返回ERRORif(S.top == S.base) return ERROR;e = * --S.top;return OK;}Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){//非递归中序遍历二叉树SqStack S;BiTNode * p;InitStack(S);p = T;while(p||!StackEmpty(S)){if(p){Push(S,p); p=p->lchild; }else {Pop(S,p); if(!Visit(p->data)) return 0;p=p->rchild;}}return 1;}//以下是递归遍历Status CreateBiTree(BiTree &T){//构造二叉树Tchar ch;scanf("%c",&ch);if(ch == ' ') T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(-2);T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}return 1;}Status PreOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){ //递归先序遍历if(T){if(Visit(T->data))if(PreOrderTraverse(T->lchild,Visit))if(PreOrderTraverse(T->rchild,Visit)) return 1;return 0;}else return 1;}Status MinOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){ //递归中序遍历if(T){if(MinOrderTraverse(T->lchild,Visit))if(Visit(T->data))if(MinOrderTraverse(T->rchild,Visit)) return 1;return 0;}else return 1;}Status PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){ //递归后续遍历if(T){if(PostOrderTraverse(T->lchild,Visit))if(PostOrderTraverse(T->rchild,Visit))if(Visit(T->data)) return 1;return 0;}else return 1;}Status PrintElement(TElemType e){//Visit函数，输出元素printf("%c ",e);return 1;}//主函数void main(){BiTNode* p;printf("Enter Node:\n");CreateBiTree(p);printf("递归先序遍历：");PreOrderTraverse(p,PrintElement);printf("\n递归中序遍历：");MinOrderTraverse(p,PrintElement);printf("\n递归后序遍历：");PostOrderTraverse(p,PrintElement);printf("\n");printf("\n非递归中序遍历：");InOrderTraverse(p,PrintElement);printf("\n");}输入：ABCE000DF00G00HJ00K0L00 (“0”表示空格) 输出：。

⼆叉树的遍历：先序中序后序遍历的递归与⾮递归实现及层序遍历 对于⼀种数据结构⽽⾔，遍历是常见操作。

⼆叉树是⼀种基本的数据结构，是⼀种每个节点的⼉⼦数⽬都不多于2的树。

⼆叉树的节点声明如下：1 typedef struct TreeNode *PtrToNode;2 typedef struct TreeNode *BinTree;34struct TreeNode5{6int Data; //为简单起见，不妨假设树节点的元素为int型7 BinTree Left;8 BinTree Right;9 }; ⼆叉树的遍历主要有先序遍历，中序遍历，后序遍历，层序遍历四种⽅式，下⾯⼀⼀介绍。

1. 先序遍历 在先序遍历中，对节点的访问⼯作是在它的左右⼉⼦被访问之前进⾏的。

换⾔之，先序遍历访问节点的顺序是根节点-左⼉⼦-右⼉⼦。

由于树可以通过递归来定义，所以树的常见操作⽤递归实现常常是⽅便清晰的。

递归实现的代码如下：1void PreOrderTraversal(BinTree BT)2{3if( BT )4 {5 printf(“%d\n”, BT->Data); //对节点做些访问⽐如打印6 PreOrderTraversal(BT->Left); //访问左⼉⼦7 PreOrderTraversal(BT->Right); //访问右⼉⼦8 }9 } 由递归代码可以看出，该递归为尾递归（即递归形式在函数末尾或者说在函数即将返回前）。

尾递归的递归调⽤需要⽤栈存储调⽤的信息，当数据规模较⼤时容易越出栈空间。

虽然现在⼤部分的编译器能够⾃动去除尾递归，但是即使如此，我们不妨⾃⼰去除。

⾮递归先序遍历算法基本思路：使⽤堆栈 a. 遇到⼀个节点，访问它，然后把它压栈，并去遍历它的左⼦树； b. 当左⼦树遍历结束后，从栈顶弹出该节点并将其指向右⼉⼦，继续a步骤； c. 当所有节点访问完即最后访问的树节点为空且栈空时，停⽌。

数据结构实验报告二叉树《数据结构与算法》实验报告专业班级姓名学号实验项目实验三二叉树。

实验目的1、掌握用递归方法实现二叉树的遍历。

2、加深对二叉树的理解，逐步培养解决实际问题的编程能力。

题目：(1)编写二叉树的遍历操作函数。

①先序遍历，递归方法re_preOrder(TREE *tree)②中序遍历，递归方法re_midOrder(TREE *tree)③后序遍历，递归方法re_postOrder(TREE *tree)(2)调用上述函数实现先序、中序和后序遍历二叉树操作。

算法设计分析（一）数据结构的定义要求用c语言编写一个演示程序，首先建立一个二叉树，让用户输入一个二叉树，实现该二叉树的便利操作。

二叉树型存储结构定义为：typedef struct TNode{ char data;//字符型数据struct TNode *lchild,*rchild;//左右孩子指针}TNode,* Tree;（二）总体设计程序由主函数、二叉树建立函数、先序遍历函数、中序遍历函数、后序遍历函数五个函数组成。

其功能描述如下：（1）主函数：统筹调用各个函数以实现相应功能。

int main()（2）二叉树建立函数：根据用户意愿运用先序遍历建立一个二叉树。

int CreateBiTree(Tree &T)（3）先序遍历函数：将所建立的二叉树先序遍历输出。

void PreOrder(Tree T)（4）中序遍历函数：将所建立的二叉树中序遍历输出。

void InOrder(Tree T)（5）后序遍历函数：将所建立的二叉树后序遍历输出。

void PostOrder(Tree T)（三）各函数的详细设计：（1）建立一个二叉树，按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树。

对T动态分配存储空间，生成根节点，构造左、右子树（2）编写先序遍历函数，依次访问根节点、左子结点、右子节点（3）编写中序遍历函数，依次访问左子结点、根节点、右子节点（4）编写后序遍历函数，依次访问左子结点、右子节点、根节点（5）编写主函数，调用各个函数，以实现二叉树遍历的基本操作。

⼆叉树的先序、中序、后序递归与⾮递归实现遍历//定义⼆叉树结点struct BiTreeNode{int data;BiTreeNode* left;BiTreeNode* right;};⼀、递归实现//先序void preOrder(BiTreeNode *root){cout<<root->data;preOrder(root->left);preOder(root->right);}//中序void inOrder(BiTreeNode *root){preOrder(root->left);cout<<root->data;preOder(root->right);}//后序void postOrder(BiTreeNode *root){preOrder(root->left);preOder(root->right);cout<<root->data;}以上的cout<<root->data;是对结点的⼀种操作，这⾥可以对结点做任意想做的操作。

⼆、⾮递归实现//先序void preOrderS(Node *root){stack<Node*> s;Node *p=root;while(p!=NULL||!s.empty()){//沿着左⽀⾛到底//⽤栈记录⾛过的路径while(p!=NULL){cout<<p->data<<"";s.push(p);p=p->left;}//当左⽀⾛到尽头时，若栈⾥边还有结点//则退栈，后退到跟结点，并且向右⽀前进//此时p!=NULL,会进⼊以上while循环if(!s.empty()){p=s.top();s.pop();p=p->right;}}}//注：在 if(!s.empty())中，获取根结点只是为了得到往右⽀的中转，//当获得右⽀指针后，将根结点从栈中弹出，以便返回的时候直接//回到爷爷结点//中序void inOrderS(Node *root){stack<Node*> s;Node *p=root;while(p!=NULL||!s.empty()){while(p!=NULL)){s.push(p);p=p->left;}if(!s.empty()){p=s.top();s.pop();cout<<p->data;p=p->right;}}}//中序遍历和先序遍历的代码⼏乎⼀致，除了访问点的位置不⼀样//中序遍历是在退栈的时候访问根结点//后序void PostOrderS(Node *root) {Node *p = root, *r = NULL;stack<Node*> s;while (p!=NULL || !s.empty()) {if (p!=NULL) {//⾛到最左边s.push(p);p = p->left;}else {p = s.top();if (p->right!=NULL && p->right != r)//右⼦树存在，未被访问p = p->right;else {s.pop();visit(p->val);r = p;//记录最近访问过的节点p = NULL;//节点访问完后，重置p指针}}//else}//while}//因为后序⾮递归遍历⼆叉树的顺序是先访问左⼦树，再访问右⼦树，最后访问根节点。

数据结构《实验2》实验报告实验项目2：二叉树前序、中序非递归遍历学号姓名课程号实验地点指导教师时间评语：按时完成实验；实验内容和过程记录完整；回答问题完整、正确；实验报告的撰写认真、格式符合要求；无抄袭的行为。

成绩教师签字二叉树中序、后序非递归遍历1、预习要求：二叉树结构定义。

2、实验目的：（1）了解二叉树结构遍历概念；（2）理解二叉树二种不同遍历过程；（3）掌握二叉树遍历算法程序。

3、实验内容及要求：（1）建立包含10个结点的二叉树（树结构和数据元素的值由自己设定）；（2）完成二叉树非递归遍历程序；（3）给出程序和每种遍历程序的结果。

4、实验设备（环境）及要求硬件：支持 Intel Pentium Ⅱ及其以上 CPU ，内存 128MB 以上、硬盘 1GB 以上容量的微机。

软件：配有 Windows98/2000/XP 操作系统，安装 Visual C++ 。

5、实验时间：10学时6、该文档的文件名不要修改，存入<学号> <姓名> 命名的文件夹中7、该表中的数据只需填空，已有内容不要修改实验结果（运行结果界面及源程序，运行结果界面放在前面）：依次是前序，中序，后序遍历的截屏#define STUDENT EType#include<iostream.h>#include <stdlib.h>#include<string.h>#include<math.h>#include<iomanip.h>//二叉树链式结构定义struct STUDENT{char name[10];char number[12];char place[10];char sex[3];int age;};struct BinaryTreeNode{EType data;BinaryTreeNode *LChild;BinaryTreeNode *RChild;};typedef BinaryTreeNode BinaryTree; //堆栈结构定义struct SType{BinaryTreeNode *ptr;bool status;};struct Stack{SType *element;int top;int Maxsize;};struct Node_Ptr{BinaryTreeNode *ptr;} ;void DigitalToString(char str[],int n){char temp;char k=1;int i=0;while (n && i<80){k=n%10+48;n=n/10;str[i]=k;i++;}str[i]='\0';int len=strlen(str);for (i=0;i<len/2;i++){temp=str[i];str[i]=str[len-i-1];str[len-i-1]=temp;}}void CreatStack(Stack &S,int MaxStackSize) {//构造一个最大容量为MaxStackSize的堆栈S.Maxsize=MaxStackSize;S.element=new SType[S.Maxsize];S.top=-1;}bool IsEmpty(Stack &S){//判断堆栈是否为空if(S.top==-1)return true;return false;}bool IsFull(Stack &S){//判断堆栈是否为满if(S.top>= S.Maxsize-1)return true;elsereturn false;}bool GetTop(Stack &S,SType &result){//返回堆栈S中栈顶元素if(IsEmpty(S))return false;result=S.element[S.top];return true;}bool Pop(Stack &S,SType &result){//将S栈顶的值取至result中，返回出栈后的状态if(IsEmpty(S))return false;result.ptr=S.element[S.top].ptr;result.status=S.element[S.top].status;S.top--;return true;}bool Push(Stack &S,SType &result){//result进s栈，返回进栈后的状态值if(IsFull(S))return false;S.top++;S.element[S.top]=result;//S.element[S.top].status=result.status;return true;}//构造一棵二叉树BinaryTree * MakeNode(EType &x){//构造节点BinaryTree *ptr;ptr=new BinaryTreeNode;if(!ptr) return NULL;ptr->data=x;ptr->LChild=NULL;ptr->RChild=NULL;return ptr;}void MakeBinaryTree(BinaryTree *root,BinaryTree *left,BinaryTree *right){//链接root,left,right所指的节点指针为二叉树root->LChild=left;root->RChild=right;}void BinaryDelete(BinaryTree *BT){//二叉树的删除if(BT){BinaryDelete(BT->LChild);BinaryDelete(BT->RChild);delete BT;}}char *GetOuputInformationString(int WidthOfData, char *OutputInformation, char*outputstring){//将一个元素的字符串OutputInformation转换为宽度为WidthOfData的等长字符串outputstring//例如，姓名是由四个字符组成，而WidthOfData为8，则在姓名字符串的两边分别连接两个字符，形成8个长度的字符串int left_space,right_space;int i;char left_space_string[16]={""};char right_space_string[16]={""};int add_space;int len_OutputInformation=strlen(OutputInformation); //计算OutputInformation的字符个数add_space=WidthOfData - len_OutputInformation; //计算需要补充的字符个数left_space=add_space/2; //计算OutputInformation左边需要补充的字符个数right_space=add_space-left_space; //计算OutputInformation右边需要补充的字符个数for(i=1;i<=left_space;i++) //形成OutputInformation左边需要补充的空格字符串strcat(left_space_string," ");for(i=1;i<=right_space;i++) //形成OutputInformation右边需要补充的空格字符串strcat(right_space_string," ");//在OutputInformation左边和右边连接需要补充的空格字符串strcpy(outputstring,left_space_string);strcat(outputstring,OutputInformation);strcat(outputstring,right_space_string);return outputstring; //返回WidthOfData宽度的outputstring}char *GetOuputInformation(int item, int k, char *outputInformation, Node_Ptr*element){switch(item){/*case 1: //线索树特有的处理与一般二叉树不同之处，在姓名的两边连接线索标志{if(element[k].ptr->Lflag)strcpy(outputInformation,"1");elsestrcpy(outputInformation,"0");strcat(outputInformation,element[k].ptr->);if(element[k].ptr->Rflag)strcat(outputInformation,"1");elsestrcat(outputInformation,"0");break;}*/case 1:{strcat(outputInformation,element[k].ptr->data.number);break;}case 2:{strcat(outputInformation,element[k].ptr->);break;}case 3:{strcat(outputInformation,element[k].ptr->data.sex);break;}case 4:{DigitalToString(outputInformation,element[k].ptr->data.age);break;}case 5:{strcat(outputInformation,element[k].ptr->data.place);break;}default: break;}return outputInformation;}void OutputBinaryTree(BinaryTreeNode *BT){Node_Ptr temp,*element;BinaryTreeNode *p;int MaxSize;int BinaryTreeHigh;int i,j,k;BinaryTreeHigh=5; //BinaryHeight(BT);MaxSize=(int) pow(2,BinaryTreeHigh);element = new Node_Ptr [MaxSize+1]; //定义一个用于存放二叉树结点指针的数组for (i=1;i<=MaxSize;i++) //对指针数组初始化，初值设为NULL element[i].ptr=NULL;p = BT;temp.ptr = p;if (p) element[1]=temp;for (i=1;i<=MaxSize;i++) //将二叉树中的每个结点指针以顺序存储结构存放到数组中{p=element[i].ptr;if (p){if (p->LChild){temp.ptr = p->LChild;element[2*i]=temp;}if (p->RChild){temp.ptr = p->RChild;element[2*i+1]=temp;}}}int WidthOfData=5;int IntervalOfData=3;// cout<<"WidthOfData="<<WidthOfData<<endl;// cout<<"IntervalOfData="<<IntervalOfData<<endl;// cout<<"BinaryTreeHigh="<<BinaryTreeHigh<<endl;int position_of_central[6][17]; //存放每一元素输出位置中心（距离屏幕左边界的字符数）int row,col; //二维数组的行列下标变量for(i=0;i<=BinaryTreeHigh;i++) //存放每一元素输出位置中心（距离屏幕左边界的字符数），初值为0for(j=0;j<=pow(2,BinaryTreeHigh-1);j++)position_of_central[i][j]=0;for(i=1;i<=pow(2,BinaryTreeHigh)-1;i++) //对深度为BinaryTreeHigh的满二叉树的所有结点计算每个结点输出的中心点位置{k=i*2; //k指向i的左子树根结点while (k<=pow(2,BinaryTreeHigh)-1) //k不断推进到i编号的结点左子树中最右子孙结点k=2*k+1;k=k/2; //k的值就是i编号的结点左子树中最右子孙结点的编号j=(int)(k-(pow(2,(BinaryTreeHigh-1))-1)); //由k编号的结点换算出该结点是底层中从左至右第j个结点右上方//即编号为k的结点中心点垂直线左边最底层上有j个结点row=(int)(log10(i)/log10(2)+1); //计算中心点值存放在position_of_central[row][col]中的rowcol=(int)(i-(pow(2,(row-1))-1)); //计算中心点值存放在position_of_central[row][col]中的colif(row==BinaryTreeHigh)//计算底层i结点距离左边界的字符数，左边无间隙position_of_central[row][col]= (j-1)*WidthOfData + (j-1)*IntervalOfData + (WidthOfData/2 +1);else//计算非底层i结点距离左边界的字符数，position_of_central[row][col]=j*WidthOfData + (j-1)*IntervalOfData + (IntervalOfData/2 +1);}char prespace[100];int m;int kk;int kkk;int item_max=5;cout<<endl;for(i=1;i<=BinaryTreeHigh;i++){kkk=(int)pow(2,i-1); //kkk是满二叉树中每一层第1个结点的编号for(int item=1;item<=item_max;item++) //输出每个数据元素多个item成员的值{int half_len_pre_value=0; //同一行前一个输出的元素值长度的一半,同一行第一个输出的元素值前没有值输出，初值为0int half_len_now_value=WidthOfData/2;//同一行当前输出的元素值长度的一半，其值始终为WidthOfData的一半kk=kkk; //kk是满二叉树中每一层结点的编号变化，从某层的最左边第一个结点编号kkk开始for(j=1;j<=pow(2,i-1);j++) //输出满二叉树中同一层次上的每个数据元素的同一个成员的值{char outputInformation[20]={""};char *OutputInformation;if (element[kk].ptr) //获取每个数据元素的一个成员的值OutputInformation，如姓名、年龄等OutputInformation=GetOuputInformation(item,kk,outputInformation,element);if (position_of_central[i][j]) //输出数据中点值存在时，position_of_central[i][j]非0{char outputstring[80]={""};char *OutputString;//下面语句将每个数据元素的一个成员的值OutputInformation，如姓名、年龄等，转换为等长WidthOfData的字符串OutputStringOutputString=GetOuputInformationString(WidthOfData,OutputInformation,outputstring);//生成两个孩子之前的空格串prespace//构成：<前导空格串>=<两个输出数据中心点之差> - <前一个输出元素值长度一半> - <当前输出元素值长度的一半>strcpy(prespace,"");m=(position_of_central[i][j]-position_of_central[i][j-1]-1-half_len_pre_value-half_len_now_ value);for(k=1;k<=m;k++)strcat(prespace," ");cout<<prespace;cout<<OutputString;half_len_pre_value=WidthOfData/2; //调整同一行前一个输出的元素值长度为WidthOfData的一半kk++;}// if (position_of_central[i][j])}//for(j=1;j<=pow(2,i-1);j++)cout<<endl;}//for(int item=1;item<=5;item++)char line[3]="─";char OutputLine[80];char midspace[80];int nodenumber;if(i==1) //对深度为BinaryTreeHigh的满二叉树从上至下，从左至右的编号，计算第i层上起始结点的编号nodenumbernodenumber=1;elsenodenumber=(int)((pow(2,i)-1)-(pow(2,i-1)-1)); //第i(i!=1)层上的第1个结点编号nodenumberfor(j=1;j<=pow(2,i-1);j++) //输出同一层次上的线条{if(i==BinaryTreeHigh) break; //最底层下面没有线条，所以break//生成两个数据元素之前的前导空格串prespacestrcpy(prespace,"");m=(position_of_central[i+1][j]-position_of_central[i+1][j-1]-1);for(k=1;k<=m;k++)strcat(prespace," ");//计算左右两个孩子之间一半的连线OutLine，由若干个line"─"构成//注意line是汉字字符，一个占两个字符位，m是左右两个孩子之间的line"─"数，所以m要除4strcpy(OutputLine,"");m=(position_of_central[i+1][j+1]-position_of_central[i+1][j]-1)/4;for(k=1;k<=m;k++)strcat(OutputLine,line);//计算左右两个孩子之间一半的空格字符的个数m,，所以要除2。

二叉树的前序、中序和后序遍历是二叉树的基本遍历方式。

前序遍历的顺序是根-左-右，中序遍历的顺序是左-根-右，后序遍历的顺序是左-右-根。

以下是在Java 中实现非递归版本的二叉树遍历：前序遍历（根-左-右）前序遍历可以直接使用栈实现。

首先将根节点入栈，然后进入一个循环，每次循环中，先弹出栈顶元素并访问，然后将其右子节点和左子节点依次入栈（注意顺序）。

javapublic void preOrderTraversal(TreeNode root) {if (root == null) {return;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();System.out.print(node.val + " ");if (node.right != null) {stack.push(node.right);}if (node.left != null) {stack.push(node.left);}}}中序遍历（左-根-右）中序遍历稍微复杂一些，因为我们需要保持正确的左右子节点的访问顺序。

这可以通过使用两个栈来实现。

首先将根节点入栈1，然后进入循环。

在每次循环中，先判断栈1是否为空，如果不为空，则弹出栈顶元素并访问，然后将其右子节点入栈1。

如果栈1为空，则将栈2中的元素依次弹出并访问，然后将其左子节点入栈1。

javapublic void inOrderTraversal(TreeNode root) {if (root == null) {return;}Stack<TreeNode> stack1 = new Stack<>();Stack<TreeNode> stack2 = new Stack<>();stack1.push(root);while (!stack1.isEmpty()) {TreeNode node = stack1.pop();stack2.push(node);if (node.right != null) {stack1.push(node.right);}}while (!stack2.isEmpty()) {TreeNode node = stack2.pop();System.out.print(node.val + " ");if (node.left != null) {stack1.push(node.left);}}}后序遍历（左-右-根）后序遍历是最复杂的，因为我们需要先访问左右子节点，再访问根节点。

数据结构实习报告---二叉树二叉树一、需求分析1、设计任务建立一棵二叉树，数据以字符串形式从键盘输入。

在此二叉树上完成：（1）前序、中序、后序遍历（2）求出叶子数（3）求树高（4）左右子树交换，输出交换后的前序、中序遍历序列选做：（1）给出非递归的后序遍历（2）扩充为中序线索树，写出非递归的中序遍历（3）在两个数组中分别有前序和中序遍历序列，试建立该二叉树2、输入的形式和输出值的范围二叉树的建立：本程序的二叉树的建立函数时根据二叉树的前序排列生成的，但是其中子树为空地方用特殊符号“＊”代替。

二叉树的输出值的范围：二叉树的输出是把二叉树各节点的值按遍历顺序输出的，本程序各节点的数据类型为字符型(可以在编译预处理修改)。

3、输出的形式二叉树的输出是根据二叉树的遍历顺序输出的（包括前序、中序和后序三种）把各节点地值输出。

4、程序所能达到的功能本程序能够实现对二叉树的一些简单操作，例如二叉树的各种遍历(包括二叉树的前序、中序和后序的递归遍历以及非递归遍历)、求二叉树的叶子数和高以及二叉树的左右子树交换。

5、测试数据(1)当为二叉树一时：(2)当为二叉树二时：二、概要设计1、树结点结构体typedef char DataType; struct TreeNode{DataType data;TreeNode *lchild,*rchild;};2、棧结点结构体struct StackNode{TreeNode* T_N;int Flag;};3、主程序流程主程序开始；调用CreateBiTree(TreeNode *&Tree)函数建立二叉树；依次调用前序、中序和后序递归及非递归遍历二叉树；计算二叉树的树叶和树高；交换二叉树的左右子树；依次用前序、中序和后序的递归和非递归方法遍历二叉树；主程序结束；三、详细设计(1)递归遍历的实现(以前序为例)；算法为：先访问根结点，然后递归的访问左子树和右子树。

齐鲁工业大学实验报告成绩课程名称数据结构指导教师单健芳实验日期院（系）信息学院专业班级计科（嵌入）14-1 实验地点学生姓名高晨悦学号 201403071007 同组人无实验项目名称二叉树的递归算法一、实验目的和要求1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。

2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。

二、实验环境微型计算机vc 6.0三、实验内容1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。

2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。

四、实验步骤一．实验内容1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。

2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。

二．程序的设计思想1实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。

先构造二叉树，根据先序遍历的思想，输入根后，再输入左子树，直至左子树为空则输入上一层右字树。

（1）二叉树的非递归遍历是用显示栈来存储二叉树的结点指针，先序遍历时，按二叉树前序遍历的顺序访问结点，并将结点的指针入栈，直到栈顶指针指向结点的左指针域为空时取出栈顶指针并删除栈顶指针，访问刚取出的指针指向的结点的右指针指向的结点并将其指针入栈，如此反复执行则为非递归操作。

（2）二叉树的递归遍历：若二叉树为空，则空操作先序遍历：（a）访问根结点；（b）先序遍历左子树；（c）先序遍历右子树。

中序遍历：（a）中序遍历左子树；（b）访问根结点；（c）中序遍历右子树后序遍历：（a）后序遍历左子树；（b）后序遍历右子树；（c）访问根结点。

2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。

（1）求二叉树的叶子结点个数：先分别求得左右子树中个叶子结点的个数，再计算出两者之和即为二叉树的叶子结点数。

（2）二叉树的结点个数之和：先分别求得左子树右子树中结点之和，再计算两者之和即为所求。

数据结构二叉树遍历实验报告数据结构二叉树遍历实验报告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. 若二叉树为空，则返回空列表。

二叉树的先序,中序,后序遍历非递归c语言二叉树是一种常见的数据结构，它的每个节点最多只能有两个子节点。

遍历二叉树是指按照一定的顺序访问二叉树中的所有节点，常见的遍历方式有先序遍历、中序遍历和后序遍历。

在二叉树的遍历过程中，递归是一种常见的解决方法。

但是递归实现有一些缺点，比如需要使用函数调用栈，对于大型二叉树可能导致栈溢出。

为了解决这个问题，我们可以使用非递归的方式来实现二叉树的遍历。

在C语言中，二叉树通常使用指针来表示。

每个节点包含一个数据元素和指向左右子节点的指针。

我们可以使用栈来模拟递归的过程，将需要访问的节点入栈，并在访问完节点后将其出栈，以此来实现非递归的遍历。

首先，我们来看一下二叉树的结构定义：```struct TreeNode {int val; //节点的值struct TreeNode* left; //左子节点struct TreeNode* right; //右子节点};```根据这个定义，我们可以实现先序、中序和后序遍历。

下面分别给出这三种遍历的实现过程：1.先序遍历：先序遍历的顺序是根节点、左子树、右子树。

我们可以使用一个栈来模拟递归的过程，具体步骤如下：-首先，创建一个空栈和一个指向根节点的指针cur。

-将cur指针指向的节点入栈，并将其值打印出来。

-如果栈不为空，将栈顶节点出栈，将cur指针指向出栈节点的右子节点。

-如果cur指针不为空，则将cur指针指向的节点入栈，并将其值打印出来。

-如果cur指针为空且栈不为空，将栈顶节点出栈，将cur指针指向出栈节点的右子节点。

-重复上述步骤，直到cur指针为空且栈为空。

下面是先序遍历的非递归实现代码：```cvoid preOrderTraversal(struct TreeNode* root) {if (root == NULL) {return;}//创建一个栈struct TreeNode* stack[STACK_SIZE];int top = -1;struct TreeNode* cur = root;while (cur != NULL || top != -1) { while (cur != NULL) {printf("%d ", cur->val);stack[++top] = cur;cur = cur->left;}if (top != -1) {cur = stack[top--];cur = cur->right;}}}```2.中序遍历：中序遍历的顺序是左子树、根节点、右子树。

数据结构》实验报告◎实验题目: 创建并遍历二叉树◎实验目的：熟悉二叉树存储结构，熟悉二叉树的三种遍历方法，并能用非递归的方法建立并且遍历二叉树。

◎实验内容：用先序和中序建立二叉树，用后序遍历并输出二叉树，要求算法非递归。

一、需求分析该程序用非递归的方法，利用先序和中序建立二叉树，然后用后序遍历的方法输出二叉树的1、输入的形式和输入值的范围；程序运行时输入二叉树的先序和中序序列，为字符型元素。

2、输出的形式；运行结果为输出二叉树的后序序列，亦为字符型元素。

3、程序所能达到的功能；本程序可以建立一个二叉树存储结构，并且访问其结点元素。

4、测试数据：输入：先序：abcde中序：edcba 输出：后序：edcba二概要设计1. 本程序中首先需定义二叉树的节点类型，节点为一个含有数据与和指针域的结构体。

2. 其次，本程序中需要用两个栈，一个用来存放指针，一个用来存放数组元素的下标。

3. 主程序中，分别输入两个字符串，作为二叉树的先序和中序序列；两个子函数分别实现创建二叉树和后序遍历输出二叉树的功能。

而在子函数中还调用了例如出栈入栈等子函数。

三详细设计1. 定义二叉树节点类型struct node{char data;struct node *lchild;struct node *rchild;}BTree;2. 定义两个栈的类型struct snode{int top;int a[MAX];};struct snode1int top;struct node *c[MAX];};3．主函数void main(){char a[MAX]={0};char b[MAX]={0};char c=0,d=0; int i=0,j=0; struct node *g;snode s; snode1 s4,s1; Initstack(&s);Initstack1(&s4);Initstack1(&s1);printf(" 请输入先序序列:\n"); while(c!='\n'){ c=getchar(); a[i]=c;i++;}printf(" 请输入中序序列:\n"); while(d!='\n'){ d=getchar(); b[j]=d; j++;} g=create(&s,&s1,a,b);printf(" 遍历输出后序序列:\n"); visit(&s4,g);printf("\n");}4. 子函数一，创建二叉树struct node * create(snode *s,snode1 *s1,char a[MAX],char b[MAX]) {int i=1,num,x; struct node *p,*q,*r,*root;p=(struct node *)malloc(sizeof(BTree));p->lchild=NULL;p->rchild=NULL; p->data=a[0];root=p; x=seek(a[0],b); push(s,x); push1(s1,p); while(a[i]!='\n') { num=seek(a[i],b); p=(struct node *)malloc(sizeof(BTree)); p->lchild=NULL;p->rchild=NULL;p->data=a[i];if(num<gettop(s)){q=get(s1);q->lchild=p;push(s,num); push1(s1,p);}else if(num>gettop(s)){ while(s->top!=-1&&num>gettop(s)) {r=pop1(s1); pop(s);}r->rchild=p; push(s,num); push1(s1,p);}i++;}return root;}5. 子函数二，后序遍历输出二叉树void visit(snode1 *s,struct node *root) {struct node *p;p=root;do{while(p!=NULL){push1(s,p);p=p->lchild;}while(s->top!=-1&&give(s)->rchild==p){p=pop1(s);printf("%c",p->data);}if(s->top!=-1)p=give(s)->rchild;}while(s->top!=-1);}四使用说明、测试分析及结果1、说明如何使用你编写的程序；程序名为4.exe,运行环境为visual C++。

.先序遍历非递归算法void PreOrderUnrec(Bitree *t){Stack s;StackInit(s);Bitree *p=t;while (p!=NULL || !StackEmpty(s)){while (p!=NULL)//遍历左子树{visite(p->data);push(s,p);p=p->lchild;}if (!StackEmpty(s))//经过下一次循环中的内嵌while 实现右子树遍历{p=pop(s);p=p->rchild;}//endif}//endwhile}2.中序遍历非递归算法void InOrderUnrec(Bitree *t){Stack s;StackInit(s);Bitree *p=t;while (p!=NULL || !StackEmpty(s)){while (p!=NULL)//遍历左子树{push(s,p);p=p->lchild;}if (!StackEmpty(s)){p=pop(s);visite(p->data);//接见根结点p=p->rchild;//经过下一次循环实现右子树遍历}//endif}//endwhile}3.后序遍历非递归算法typedef enum{L,R} tagtype;typedef struct{Bitree ptr;tagtype tag;}stacknode;typedef struct{stacknode Elem[maxsize];int top;}SqStack;void PostOrderUnrec(Bitree t){SqStack s;stacknode x;StackInit(s);p=t;do{while (p!=null)//遍历左子树{x.ptr = p;x.tag = L;//标志为左子树push(s,x);p=p->lchild;}while (!StackEmpty(s) && s.Elem[s.top].tag==R){x = pop(s);p = x.ptr;visite(p->data); //tag为R，表示右子树接见完成，故接见根结点}if (!StackEmpty(s)){s.Elem[s.top].tag =R;//遍历右子树p=s.Elem[s.top].ptr->rchild;}}while (!StackEmpty(s));}//PostOrderUnrec。

⼆叉树先序、中序、后序遍历递归与⾮递归Python实现1.先序遍历：根节点->左⼦树->右⼦树1# 先序打印⼆叉树（递归）2def preOrderTraverse(node):3if node is None:4return None5print(node.val)6 preOrderTraverse(node.left)7 preOrderTraverse(node.right)1# 先序打印⼆叉树（⾮递归）2def preOrderTravese(node):3 stack = [node]4while len(stack) > 0:5print(node.val)6if node.right is not None:7 stack.append(node.right)8if node.left is not None:9 stack.append(node.left)10 node = stack.pop()2.中序遍历：左⼦树->根节点->右⼦树1# 中序打印⼆叉树（递归）2def inOrderTraverse(node):3if node is None:4return None5 inOrderTraverse(node.left)6print(node.val)7 inOrderTraverse(node.right)1# 中序打印⼆叉树（⾮递归）2def inOrderTraverse(node):3 stack = []4 pos = node5while pos is not None or len(stack) > 0:6if pos is not None:7 stack.append(pos)8 pos = pos.left9else:10 pos = stack.pop()11print(pos.val)12 pos = pos.right3.后序遍历：左⼦树->右⼦树->根节点1# 后序打印⼆叉树（递归）2def postOrderTraverse(node):3if node is None:4return None5 postOrderTraverse(node.left)6 postOrderTraverse(node.right)7print(node.val)1# 后序打印⼆叉树（⾮递归）2# 使⽤两个栈结构3# 第⼀个栈进栈顺序：左节点->右节点->跟节点4# 第⼀个栈弹出顺序：跟节点->右节点->左节点(先序遍历栈弹出顺序：跟->左->右)5# 第⼆个栈存储为第⼀个栈的每个弹出依次进栈6# 最后第⼆个栈依次出栈7def postOrderTraverse(node):8 stack = [node]9 stack2 = []10while len(stack) > 0:11 node = stack.pop()12 stack2.append(node)13if node.left is not None:14 stack.append(node.left)15if node.right is not None:16 stack.append(node.right)17while len(stack2) > 0:18print(stack2.pop().val)4.按层遍历：从上到下、从左到右按层遍历1# 先进先出选⽤队列结构2import queue3def layerTraverse(head):4if not head:5return None6 que = queue.Queue() # 创建先进先出队列7 que.put(head)8while not que.empty():9 head = que.get() # 弹出第⼀个元素并打印10print(head.val)11if head.left: # 若该节点存在左⼦节点,则加⼊队列（先push左节点）12 que.put(head.left)13if head.right: # 若该节点存在右⼦节点,则加⼊队列（再push右节点）14 que.put(head.right)5.⼆叉树节点个数1# 求⼆叉树节点个数2def treeNodenums(node):3if node is None:4return 05 nums = treeNodenums(node.left)6 nums += treeNodenums(node.right)7return nums + 16.⼆叉树的最⼤深度1# ⼆叉树的最⼤深度2def bTreeDepth(node):3if node is None:4return 05 ldepth = bTreeDepth(node.left)6 rdepth = bTreeDepth(node.right)7return (max(ldepth, rdepth) + 1)。