数据结构二叉树前中后序非递归遍历
数据结构《实验2》实验报告
实验项目2：二叉树前序、中序非递归遍历
回答问题完整、
实验结果（运行结果界面及源程序，运行结果界面放在前面）：依次是前序，中序，后序遍历的截屏
#define STUDENT EType
#include
#include
#include
#include
#include
//二叉树链式结构定义
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 { 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; else return 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"); else strcpy(outputInformation,"0"); strcat(outputInformation,element[k].ptr->https://www.sodocs.net/doc/1112166144.html,); if(element[k].ptr->Rflag) strcat(outputInformation,"1"); else strcat(outputInformation,"0"); break; }*/ case 1: { strcat(outputInformation,element[k].ptr->data.number); break; } case 2: { strcat(outputInformation,element[k].ptr->https://www.sodocs.net/doc/1112166144.html,); 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="< // cout<<"IntervalOfData="< // cout<<"BinaryTreeHigh="< int position_of_central[6][17]; //存放每一元素输出位置中心（距离屏幕左边界的字符数） int row,col; //二维数组的行列下标变量 for(i=0;i<=BinaryTreeHigh;i++) //存放每一元素输出位置中心（距离屏幕左边界的字符数），初值为0 for(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]中的row col=(int)(i-(pow(2,(row-1))-1)); //计算中心点值存放在position_of_central[row][col]中的col if(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< 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; //同一行前一个输出的元素值长度的一半,同一行第一个输出的元素值前没有值输出，初值为0 int 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的字符串OutputString OutputString=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< cout< half_len_pre_value=WidthOfData/2; //调整同一行前一个输出的元素值长度为WidthOfData的一半 kk++; }// if (position_of_central[i][j]) }//for(j=1;j<=pow(2,i-1);j++) cout< }//for(int item=1;item<=5;item++) char line[3]="─"; char OutputLine[80]; char midspace[80]; int nodenumber; if(i==1) //对深度为BinaryTreeHigh的满二叉树从上至下，从左至右的编号，计算第i层上起始结点的编号nodenumber nodenumber=1; else nodenumber=(int)((pow(2,i)-1)-(pow(2,i-1)-1)); //第i(i!=1)层上的第1个结点编号nodenumber for(j=1;j<=pow(2,i-1);j++) //输出同一层次上的线条 { if(i==BinaryTreeHigh) break; //最底层下面没有线条，所以break //生成两个数据元素之前的前导空格串prespace strcpy(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要除4 strcpy(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。由m形成左右两个孩子之间的空格串midspace strcpy(midspace,""); m=(position_of_central[i+1][j+1]-position_of_central[i+1][j]-1)/2; for(k=1;k<=m;k++) strcat(midspace," "); if ((element[2*nodenumber].ptr) && (element[2*nodenumber+1].ptr))//左右子树都存在时，左右两个孩子上的连接线┌─┴─┐ cout< <<"┌"< if ((element[2*nodenumber].ptr) && (!element[2*nodenumber+1].ptr))//左子树存在，右子树不存在时，左右两个孩子上的连接线┌─┘ cout< <<"┌"< if ((!element[2*nodenumber].ptr) && (element[2*nodenumber+1].ptr))//左子树不存在，右子树存在时左右两个孩子上的连接线└─┐ cout< < if ((!element[2*nodenumber].ptr) && (!element[2*nodenumber+1].ptr))//左子树不存在，右子树不存在时，没有连接线，是空格串 cout< < nodenumber=nodenumber+1; //结点编号加1 } cout< }//for(i=1;i<=BinaryTreeHigh;i++) delete element; //释放工作空间 } //三种非递归的遍历方式 void PreOrderNoRecursive(BinaryTree *BT) {//二叉树的前序遍历非递归算法 Stack S; SType temp; BinaryTree *p=BT;//一般约定BT指向一颗二叉树的根节点 int MaxStackSize=50;//其值是假设的一个足够大的数 CreatStack(S,MaxStackSize);//产生一个空栈，这一过程函数可以不在这里进行 cout<<"************** "< while(p||!IsEmpty(S)) { if(p) { cout<<" "< Push(S,temp);//根节点指针进栈，以后回溯时候退栈 p=p->LChild;//指针指向访问过的根节点的左子树 } else //左子树为空时，利用堆栈回溯 if(!IsEmpty(S)) { Pop(S,temp);//从堆栈中弹出回溯节点指针（该节点已经访问过） p=temp.ptr; p=p->RChild;//指针指向回溯节点的右子树 } } } void InOrderNoRecursive(BinaryTree *BT) {//二叉树的中序遍历非递归算法 Stack S; SType temp; BinaryTree *p=BT;//一般约定BT指向一颗二叉树的根节点 int MaxStackSize=50;//其值是假设的一个足够大的数 CreatStack(S,MaxStackSize);//产生一个空栈，这一过程函数可以不在这里进行 cout<<"************** "< while(p||!IsEmpty(S)) { while(p)//找最左子树 { temp.ptr=p; Push(S,temp);//根节点（未访问）指针进栈，以后回溯时候退栈 p=p->LChild;//指针指向该根节点的左子树 } if(!IsEmpty(S))//左子树为空时，利用堆栈回溯 { Pop(S,temp);//从堆栈中弹出回溯节点指针（该节点未访问过） p=temp.ptr; cout<<" "< } } } void PostOrderNoRecursive(BinaryTree *BT) {//二叉树的后序遍历非递归算法 Stack S; SType temp; BinaryTree *p=BT;//一般约定BT指向一颗二叉树的根节点 int MaxStackSize=50;//其值是假设的一个足够大的数 CreatStack(S,MaxStackSize);//产生一个空栈，这一过程函数可以不在这里进行 cout<<"************** "< while(p||!IsEmpty(S)) { if(p)//找最左子树 { temp.status=false;//准备进站的节点进栈标志设为第一次进栈 temp.ptr=p; Push(S,temp);//根节点（未访问）指针进栈，以后回溯时候退栈 p=p->LChild;//指针指向该根节点的左子树 } else { if(!IsEmpty(S))//左子树为空时，利用堆栈回溯 { Pop(S,temp);//从堆栈中弹出回溯节点指针（该节点未访问过） p=temp.ptr; if(temp.status) { cout<<" "< p=NULL; } else { temp.status=true;//改变进栈标志，重新准备进栈 Push(S,temp); p=p->RChild;//指针指向根的右子树 } } } } } int BinaryNodeCount(BinaryTreeNode *BT) { Stack S; SType temp; int index=0; BinaryTreeNode *p=BT; int MaxStackSize=50; CreatStack(S,MaxStackSize); while(p||!IsEmpty(S)) { if(p) { index++; temp.ptr=p; Push(S,temp); p=p->LChild; } else if(!IsEmpty(S)) { Pop(S,temp); p=temp.ptr; p=p->RChild; } } return index; } int BinaryHeight(BinaryTreeNode *BT) { if(!BT) return 0; int HightL=BinaryHeight(BT->LChild); int HightR=BinaryHeight(BT->RChild); if(HightL>HightR) return ++HightL; else return ++HightR; } void main() { Stack S; BinaryTree *BT; BinaryTreeNode *p[11]; int choice,MaxStackSize; EType result,x; char number[][10]={" ","101","102","103","104","105","106","107","108","109","110"}; char sex [][10]={" ","女","男","男","女","男","女","男","女","女","女",}; char name [][10]={" ","小猫","小狗","小鸡","小妞","小孩","小鸟","小白","小花","小丑","小小"}; char place[][10]={" ","湖北","湖南","山西","陕西","河北","河南","江西","江苏","广东","广西"}; //初始化 for(int i=1;i<11;i++) { x.age=15+i; strcpy(https://www.sodocs.net/doc/1112166144.html,,name[i]); strcpy(x.number,number[i]); strcpy(x.place,place[i]); strcpy(x.sex,sex[i]); p[i]=MakeNode(x); } BT=p[1]; //构造二叉树 MakeBinaryTree(p[1],p[2],p[3]); MakeBinaryTree(p[2],p[4],p[5]); MakeBinaryTree(p[3],p[6],p[7]); MakeBinaryTree(p[4],p[8],p[9]); MakeBinaryTree(p[8],NULL,NULL); MakeBinaryTree(p[9],NULL,NULL); MakeBinaryTree(p[5],NULL,NULL); MakeBinaryTree(p[6],p[10],NULL); MakeBinaryTree(p[7],NULL,NULL); MakeBinaryTree(p[10],NULL,NULL); while (true) { cout< cout<<"************************二叉树的前序，中序，后序非递归遍历****************"< cout<<"* 1--------通过二叉树的前序遍历非递归算法输出二叉树中的所有元素*"< cout<<"* 2--------通过二叉树的中序遍历非递归算法输出二叉树中的所有元素*"< cout<<"* 3--------通过二叉树的后序遍历非递归算法输出二叉树中的所有元素*"< cout<<"* 4--------统计二叉树中节点的个数*"< cout<<"* 5--------二叉树的删除*"< cout<<"* 6--------计算二叉树的高度 *"< cout<<"* 7--------输出二叉树的树形结构*"< cout<<"* 0--------退出*"< cout<<"******************************************************************** ******"< cout<<"请选择处理功能："; cin>>choice; cout< system("cls"); switch(choice) { case 1: {//1---------通过二叉树的前序遍历非递归算法输出二叉树中的所有元素 cout<<"二叉树的树形结构:"< OutputBinaryTree(BT); cout<<" #########通过二叉树的前序遍历非递归算法输出二叉树中的所有元素########"< PreOrderNoRecursive(BT); break; } case 2: {//2---------通过二叉树的中序遍历非递归算法输出二叉树中的所有元素 cout<<"二叉树的树形结构:"< OutputBinaryTree(BT); cout<<" #########通过二叉树的中序遍历非递归算法输出二叉树中的所有元素########"< InOrderNoRecursive(BT); break; } case 3: {//3---------通过二叉树的后序遍历非递归算法输出二叉树中的所有元素 cout<<"二叉树的树形结构"< OutputBinaryTree(BT); cout<<" ########通过二叉树的后序遍历非递归算法输出二叉树中的所有元素########"< PostOrderNoRecursive(BT); break; } case 4: {//4--------统计二叉树中节点的个数 cout<<"统计二叉树中节点的个数"< cout<<"此二叉树的节点个数为："< break; } case 5: {//5--------计算二叉树的高度 cout<<"计算二叉树的高度"< cout<<"该二叉树的高度为："< break; } case 6: {//6--------删除二叉树 cout<<"删除二叉树"< BinaryDelete(BT); break; } case 7: {//7------输出二叉树的树形结构 cout<<"输出二叉树"< OutputBinaryTree(BT); break; } case 0: {//0-------退出 cout<<"退出操作"< BinaryDelete(BT); // delete BT; } } system("pause"); system("cls"); } } 树与二叉树复习 一、填空 1、由二叉树的（中）序和（前、后）序遍历序列可以唯一确定一棵二叉树。 2、任意一棵二叉树，若度为0的结点个数为n0，度为2的结点个数为n2，则n0等于（n0=n2+1 ）。 3、一棵二叉树的第i（i≥1）层最多有（2i-1 ）个结点。 4、一棵有n个结点的二叉树，若它有n0个叶子结点，则该二叉树上度为1的结点个数n1=（n-2n0+1 ）。 5、在一棵高度为5的完全二叉树中，最少含有（ 16 ）个结点。 6、 2．有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当折半查找值为82的结点时，（ C ）次比较后查找成功。 A． 11 B 5 C 4 D 8 7、在有n个叶结点的哈夫曼树中，总结点数（ 2n-1 ）。 8、若一个问题的求解既可以用递归算法，也可以用递推算法，则往往用（递推）算法，因为（递推算法效率高）。 9、设一棵完全二叉树有700个结点，则共有（ 350 ）叶子结点。 10、设一棵完全二叉树具有1000个结点，该树有（500）个叶子结点，有（499 ）个度为2的结点，有（ 1 ）个结点只有非空左子树。 二、判断 1、( × )在哈夫曼树中，权值最小的结点离根结点最近。 2、( √ ) 完全二叉树中，若一个结点没有左孩子，则它必是叶子结点。 3、( √ )二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。 4、( × ) 若一搜索树（查找树）是一个有n个结点的完全二叉树，则该树的最大值一定在叶结点上。 5、( √ )若以二叉链表作为树和二叉树的存储结构，则给定任一棵树都可以找到唯一的一棵二叉树与之对应。 6、( √ )若一搜索树（查找树）是一个有n个结点的完全二叉树，则该树的最小 二叉树的遍历 一、设计思想 二叉树的遍历分为三种方式，分别是先序遍历，中序遍历和后序遍历。先序遍历实现的顺序是：根左右，中序遍历实现的是：左根右，后续遍历实现的是：左右根。根据不同的算法分，又分为递归遍历和非递归遍历。 递归算法： 1．先序遍历：先序遍历就是首先判断根结点是否为空，为空则停止遍历，不为空则将左子作为新的根结点重新进行上述判断，左子遍历结束后，再将右子作为根结点判断，直至结束。到达每一个结点时，打印该结点数据，即得先序遍历结果。 2.中序遍历：中序遍历是首先判断该结点是否为空，为空则结束，不为空则将左子作为根结点再进行判断，打印左子，然后打印二叉树的根结点，最后再将右子作为参数进行判断，打印右子，直至结束。 3.后续遍历：指针到达一个结点时，判断该结点是否为空，为空则停止遍历，不为空则将左子作为新的结点参数进行判断，打印左子。左子判断完成后，将右子作为结点参数传入判断，打印右子。左右子判断完成后打印根结点。 非递归算法： 1.先序遍历：首先建立一个栈，当指针到达根结点时，打印根结点，判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈，将左子作为新的根结点进行判断，方法同上。若当前结点没有左子，则直接将右子打印，同时将右子作为新的根结点判断。若当前结点没有右子，则打印左子，同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子，则当前结点为叶子结点，此时将从栈中出栈一个元素，作为当前的根结点，打印结点元素，同时将当前结点同样按上述方法判断，依次进行。直至当前结点的左右子都为 空，且栈为空时，遍历结束。 2.中序遍历：首先建立一个栈，定义一个常量flag（flag为0或者1），用flag记录结点的左子是否去过，没有去过为0，去过为1，默认为0.首先将指针指向根结点，将根结点入栈，然后将指针指向左子，左子作为新的结点，将新结点入栈，然后再将指针指向当前结点的左子，直至左子为空，则指针返回，flag置1，出栈一个元素，作为当前结点，打印该结点，然后判断flag，flag为1则将指针指向当前结点右子，将右子作为新的结点，结点入栈，再次进行上面的判断，直至当前结点右子也为空，则再出栈一个元素作为当前结点，一直到结束，使得当前结点右子为空，且栈空，遍历结束。 3.后续遍历：首先建立两个栈，然后定义两个常量。第一个为status，取值为0，1，2.0代表左右子都没有去过，1代表去过左子，2，代表左右子都去过，默认为0。第二个常量为flag，取值为0或者1，0代表进左栈，1代表进右栈。初始时指针指向根结点，判断根结点是否有左子，有左子则，将根结点入左栈，status置0，flag置0，若没有左子则判断结点有没有右子，有右子就把结点入右栈，status置0，flag置1，若左右子都没有，则打印该结点，并将指针指向空，此时判断flag，若flag为0，则从左栈出栈一个元素作为当前结点，重新判断；若flag为1则从右栈出栈一个元素作为当前结点，重新判断左右子是否去过，若status为1，则判断该结点有没有右子，若有右子，则将该结点入右栈，status置1，flag置1，若没有右子，则打印当前结点，并将指针置空，然后再次判断flag。若当前结点status为2，且栈为空，则遍历结束。若指针指向了左子，则将左子作为当前结点，判断其左右子情况，按上述方法处理，直至遍历结束。 二、算法流程图 C语言实现二叉树的前序遍历算法实现一： #include #include 数学与计算机学院计算机系实验报告 课程名称： 数据结构 年级：2010 实验成绩： 指导教师： 黄襄念 姓名： 实验教室：6A-413 实验名称：二叉树前序或中序或后序遍历 学号： 实验日期：2012/6/10 实验序号：实验3 实验时间：8:00—11:40 实验学时：4 一、实验目的 1. 熟悉的掌握树的创建，和树的前序、中序、后序遍历。 二、实验环境 1. 操作系统：Windows7 2. 开发软件：Microsoft Visual C++ 6.0 三、实验内容 ● 程序功能 本程序完成了以下功能： 1. 前序遍历 2. 中序遍历 3. 后序遍历 ● 数据结构 本程序中使用的数据结构（若有多个，逐个说明）： 1. 它的优缺点 1） 可以快速的查找数据。 2） 让数据层次更加清晰。 2. 逻辑结构图 3. 存储结构图 、、、、、、、、、、、、、、、、、、、、 4.存储结构的C/C++ 语言描述 typedef struct node { DataType data; struct node *lchild; struct node *rchild; } BiTNode, *BiTree; typedef BiTree type; ●算法描述 本程序中采用的算法 1.算法名称：递归 2.算法原理或思想 是通过访问结点的左右孩子来进行循环查找的方法，拿中序遍历来说明：先从头结点开始，再去访问头结点的右孩子如果为空就访问头结点的左孩子，依次进行访问当结点的左右孩子都为空时，就访问上一级，到了最后。 3.算法特点 它能将查找进行2分，体现出了更高效快捷的特点，并且层次很清晰。 ●程序说明 1. 2. 1）前序遍历模块：将树进行从头结点开始再左孩子再右孩子。 代码：void InOrder(BiTree root) { Stack S(100); initStack(S); BiTNode *p = root; do { while(p != NULL) { Push(S, p); 数据结构（双语） ——项目文档报告用两种方式实现表达式自动计算 专业： 班级： 指导教师： 姓名： 学号： 目录 一、设计思想 (01) 二、算法流程图 (02) 三、源代码 (04) 四、运行结果 (11) 五、遇到的问题及解决 (11) 六、心得体会 (12) 一、设计思想 二叉树的遍历分为三种方式，分别是先序遍历，中序遍历和后序遍历。先序遍历实现的顺序是：根左右，中序遍历实现的是：左根右，后续遍历实现的是：左右根。根据不同的算法分，又分为递归遍历和非递归遍历。 递归算法： 1．先序遍历：先序遍历就是首先判断根结点是否为空，为空则停止遍历，不为空则将左子作为新的根结点重新进行上述判断，左子遍历结束后，再将右子作为根结点判断，直至结束。到达每一个结点时，打印该结点数据，即得先序遍历结果。 2.中序遍历：中序遍历是首先判断该结点是否为空，为空则结束，不为空则将左子作为根结点再进行判断，打印左子，然后打印二叉树的根结点，最后再将右子作为参数进行判断，打印右子，直至结束。 3.后续遍历：指针到达一个结点时，判断该结点是否为空，为空则停止遍历，不为空则将左子作为新的结点参数进行判断，打印左子。左子判断完成后，将右子作为结点参数传入判断，打印右子。左右子判断完成后打印根结点。 非递归算法： 1.先序遍历：首先建立一个栈，当指针到达根结点时，打印根结点，判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈，将左子作为新的根结点进行判断，方法同上。若当前结点没有左子，则直接将右子打印，同时将右子作为新的根结点判断。若当前结点没有右子，则打印左子，同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子，则当前结点为叶子结点，此时将从栈中出栈一个元素，作为当前的根结点，打印结点元素，同时将当前结点同样按上述方法判断，依次进行。直至当前结点的左右子都为空，且栈为空时，遍历结束。 2.中序遍历：首先建立一个栈，定义一个常量flag（flag为0或者1），用flag记录结点的左子是否去过，没有去过为0，去过为1，默认为0.首先将指针指向根结点，将根结点入栈，然后将指针指向左子，左子作为新的结点，将新结点入栈，然后再将指针指向当前结点的左子，直至左子为空，则指针返回，flag置1，出栈一个元素，作为当前结点，打印该结点，然后判断flag，flag为1则将指针指向当前结点右子，将右子作为新的结点，结点入栈，再次进行上面的判断，直至当前结点右子也为空，则再出栈一个元素作为当前结点，一直到结束，使得当前结点右子为空，且栈空，遍历结束。 3.后续遍历：首先建立两个栈，然后定义两个常量。第一个为status，取值为0，1，2.0代表左右子都没有去过，1代表去过左子，2，代表左右子都去过，默认为0。第二个常量为flag，取值为0或者1，0代表进左栈，1代表进右栈。初始时指针指向根结点，判断根结点是否有左子，有左子则，将根结点入左栈，status置0，flag置0，若没有左子则判断结点有没有右子，有右子就把结点入右栈，status置0，flag置1，若左右子都没有，则打印该结点，并将指针指向空，此时判断flag，若flag为0，则从左栈出栈一个元素作为当前结点，重新判断；若flag为1则从右栈出栈一个元素作为当前结点，重新判断左右子是否去过，若status 为1，则判断该结点有没有右子，若有右子，则将该结点入右栈，status置1，flag置1，若没有右子，则打印当前结点，并将指针置空，然后再次判断flag。若当前结点status为2，且栈为空，则遍历结束。若指针指向了左子，则将左子作为当前结点，判断其左右子情况，按上述方法处理，直至遍历结束。 #include <> #include <> #include <> #define MAX_TREE_SIZE 100 typedef struct { int data; int parent; ata,[i].parent); printf("\n"); } } /*用双亲表示法创建树*/ PTree CreatTree(PTree T) { int i=1; int fa,ch; PTNode p; for(i=1;ch!=-1;i++) { printf("输入第%d结点:\n",i); scanf("%d,%d",&fa,&ch); printf("\n"); =ch; =fa; ++; [].data = ; [].parent = ; } printf("\n"); printf("创建的树具体情况如下:\n"); print_ptree(T); return T; } /*一般树转换成二叉树*/ BTNode *change(PTree T) { int i,j=0; BTNode p[MAX_TREE_SIZE]; BTNode *ip,*is,*ir,*Tree; ip=(BTNode *)malloc(sizeof(BTNode)); is=(BTNode *)malloc(sizeof(BTNode)); ir=(BTNode *)malloc(sizeof(BTNode)); Tree=(BTNode *)malloc(sizeof(BTNode)); for(i=0;i<;i++) { p[i]=GetTreeNode[i].data); } for(i=1;i<;i++) { ip=&p[i]; is=&p[j]; while[i].parent!=is->data) { j++; is=&p[j]; } if(!(is->firstchild)) { is->firstchild=ip; ir=ip; } else { ir->rightsib=ip; ir=ip; } } Tree=&p[0]; return Tree; } /*主菜单*/ void Menu() { printf("=================主菜单=======================\n"); printf("***输入-以双亲法创建一棵一般树***\n"); printf("***输入2-------------树的前序遍历(递归)*******\n"); printf("***输入3-------------树的后序遍历(递归)*******\n"); printf("***输入4-------------树的前序遍历(非递归)*****\n"); printf("***输入5-------------树的后序遍历(非递归)*****\n"); printf("***输入6-------------层次序的非递归遍历*******\n"); printf("***输入0-------------退出程序*****************\n"); printf("==============================================\n"); 实践三：树的应用 1.实验目的要求 通过本实验使学生深刻理解二叉树的性质和存储结构，熟练掌握二叉树的遍历算法。认识哈夫曼树、哈夫曼编码的作用和意义。 实验要求：建一个二叉树并按照前序、中序、后序三种方法遍历此二叉树，正确调试本程序。 能够建立一个哈夫曼树，并输出哈夫曼编码，正确调程序。写出实验报告。 2.实验主要内容 2.1 对二叉树进行先序、中序、后序递归遍历，中序非递归遍历。 2.2 根据已知的字符及其权值，建立哈夫曼树，并输出哈夫曼编码。 3．实验步骤 2.1实验步骤 ●输入p127二叉链表的定义 ●录入调试p131算法6.4，实现二叉树的构造函数 ●编写二叉树打印函数，可以通过递归算法将二叉树输出为广义表的 形式，以方便观察树的结构。 ●参考算法6.1，实现二叉树的前序、中序和后序的递归遍历算法。 为简化编程，可以将visit函数直接使用printf函数输出结点内容来 代替。 #include 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,否则返回FALSE if(S.top==S.base) return 1; else return 0; } #include 二叉树前序、中序、后序遍历相互求法今天来总结下二叉树前序、中序、后序遍历相互求法，即如果知道两个的遍历，如何求第三种遍历方法，比较笨的方法是画出来二叉树，然后根据各种遍历不同的特性来求，也可以编程求出，下面我们分别说明。 首先，我们看看前序、中序、后序遍历的特性： 前序遍历： 1.访问根节点 2.前序遍历左子树 3.前序遍历右子树 中序遍历： 1.中序遍历左子树 2.访问根节点 3.中序遍历右子树 后序遍历： 1.后序遍历左子树 2.后序遍历右子树 3.访问根节点 一、已知前序、中序遍历，求后序遍历 例： 前序遍历: GDAFEMHZ 中序遍历: ADEFGHMZ 画树求法： 第一步，根据前序遍历的特点，我们知道根结点为G 第二步，观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树，G右侧的HMZ必然是root的右子树。 第三步，观察左子树ADEF，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的root的leftchild位于root之后，所以左子树的根节点为D。 第四步，同样的道理，root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点。同理，遍历的右子树的第一个节点就是右子树的根节点。 第五步，观察发现，上面的过程是递归的。先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了。该步递归的过程可以简洁表达如下： 1 确定根,确定左子树，确定右子树。 2 在左子树中递归。 数据结构（双语） ——项目文档报告 用递归、非递归两种方法遍历二叉树 专业：计算机科学与技术 班级： 指导教师： 姓名： 学号： 目录 一、设计思想 (03) 二、算法流程图 (04) 三、源代码 (06) 四、运行结果 (12) 五、遇到的问题及解决 (14) 六、心得体会 (15) 一、设计思想 1．递归： （1）主函数main（）主程序要包括：定义的二叉树T、建树函数、先序遍历函数、中序遍历函数、后序遍历函数。 （2）建树函数定义一个输入的数是字符型的，当ch为空时，T就为空值，否则的话就分配空间给T，T就指向它的结点，然后左指针域指向左孩子，右指针指向右孩子，若还有，继续调用,依次循环下去，直到ch遇到空时，结束。最后要返回建立的二叉树T。 （3）先序遍历函数根据先序遍历规则，当T为非空时，先输出结点处的数据，指针指向左、右孩子，依次进行下去。 (4) 中序遍历函数根据中序遍历规则，当T为非空时，先左指针指向左孩子数据，然后输出结点处的数据，再右指针指向右孩子，依次进行下去。 (5）后序遍历函数根据后序遍历规则，当T为非空时，先右指针指向右孩子，然后左指针指向左孩子，最后输出结点处的数据，依次进行下去。 2.非递归： （1）跟递归遍历二叉树的前提一样，首先应该创建一个二叉树，同样使用先序递归的方式创建二叉树。 （2）然后是中序，先序，后序非递归遍历二叉树。 （3）中序非递归遍历二叉树的思想是：首先是根节点压栈，当根节点的左子树不是空的时候，左子树压栈。直到左子树为空的时候，不再压栈。将栈顶元素出栈，访问栈顶元素，并将栈顶的右子树进栈。当右子树的左子树不是空的时候，左子树一直进栈，直到左子树为空，则不再进栈。重复上面的操作，直到栈空的时候。 (4)先序非递归遍历二叉树的思想是：首先是根节点进栈，然后当栈不为空的时候，将栈顶元素出栈，然后访问。同时将出栈元素的右子树进栈，左子树进栈。重复上面的操作，直到栈为空。 (5）后序非递归遍历二叉树的思想：首先是根节点进栈，当根节点的左子树不为空的时候，左子树进栈，直到左为空的时候，左子树不再进栈。指针指向的是右子树，当右子树为空的时候，直接访问根节点。当右子树不为空的时候，则右子树的指针进栈，当右子树的左子树不为空的时候，则左也进栈，直到左为空。重复上面的操作，直到栈为空的时候，则遍历树完成。 #include "stdio.h" #include "stdlib.h" #define STACK_INIT_SIZE 100 //栈存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配增量 //------二叉树的存储结构表示------// typedef struct BiTNode{ int data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //-----顺序栈的存储结构表示------// typedef struct{ BiTree *top; BiTree *base; int stacksize; }SqStack; //*************************************************** //构造一个空栈s SqStack *InitStack(); //创建一颗二叉树 BiTree CreatBiTree(); //判断栈空 int StackEmpty(SqStack *S); //插入元素e为新的栈顶元素 void Push(SqStack *S,BiTree p); //若栈不为空，则删除s栈顶的元素e，将e插入到链表L中void Pop(SqStack *S,BiTree *q); //非递归先序遍历二叉树 void PreOrderTraverse(BiTree L); //非递归中序遍历二叉树 void InOrderTraverse(BiTree L); //非递归后序遍历二叉树 void PostOrderTraverse(BiTree L); //递归后序遍历二叉树 void PostOrder(BiTree bt); //递归中序遍历二叉树 void InOrder(BiTree bt); //递归先序遍历二叉树 void PreOrder(BiTree bt); //*************************************************** 用递归、非递归两种方法遍历二叉树 一、设计思想 1. 用递归算法遍历 设计思想：主要是通过不同程序顺序，从而实现递归的顺序遍历 前序遍历：先判断节点是否为空，如果不为空，则输出。再判断左节点是否为空，如果不为空，则递归调用，直到遍历到最左边。接着再遍历最左边的右子树，如果此时右子树不为空，则递归遍历左子树的操作，直到遍历到叶子节点。如果右子树为空，则回溯上次的递归调用，重复输出和遍历右子树的操作。 中序遍历：先遍历左节点是否为空，如果不为空，则递归调用，直到遍历到最左边或者叶子节点，然后输出，接着再遍历最左边的右子树，如果此时右子树不为空，则递归重复遍历左子树的操作，直到遍历到叶子节点。如果右子树为空，则回溯到上次递归调用，重复输出和遍历右子树的操作。 后序遍历：先判断左节点是否为空，如果不为空则一直递归直到遍历到最左边，然后遍历右节点，再接着遍历到左子树的最右边，直到遍历到叶子节点。此时输出，回溯到上次递归，继续执行后面的操作，重复，直到将整个树遍历完毕。 2. 用非递归算法遍历 设计思想：主要是通过栈的存取，判空，从而实现树的遍历 前序遍历：通过一个循环实现。先输出节点的数值，因为栈的特性，则需要先判断右子树是否为空，如果不为空，则将右子树压栈。然后判断左子树是否为空，如果不为空，则将左子树压栈。接着再将栈里面的子树弹出赋给给当前节点变量，重复上述操作，直到栈为空后退出循环。 中序遍历：通过循环实现。将树一直遍历到最左端，并将中间所经过的节点保存在栈中，当遍历到最左边的时候，则弹出栈里面的子树。输出数值，将当前节点赋值为当前节点的右子树，遍历右子树，即重复上述操作，直到当前节点为空，并且栈内元素为0。 后序遍历：通过循环和标记栈实现。将数一直遍历到最左端，并将中间的节点保存在树栈中，同时同步的添加一个标记栈。当遍历到最左边的时候，弹栈并赋值给当前栈，然后判断标记栈的数值，如果数值为0的话则代表当前树没有遍历过，遍历右子树。然后重复上面的操作，如果数值为1的话则代表此时数已经遍历过了，可以开始输出了，为了避免重复输出，将当前栈赋为空。重复循环操作，直到栈内没有元素，且当前节点为空（因为一直左的操作并没有将右子树压栈）。 #include 二叉树的前序遍历、中序遍历、后续遍历 （递归法） 1、前序遍历（递归）： 算法实现一： #include 算法实现二： #include ○A ○C ○D ○B ○E○F G 《数据结构与算法》实验报告三 ——二叉树的操作与应用 一.实验目的 熟悉二叉链表存储结构的特征，掌握二叉树遍历操作及其应用 二. 实验要求（题目） 说明：以下题目中（一）为全体必做，（二）（三）任选其一完成 （一）从键盘输入二叉树的扩展先序遍历序列，建立二叉树的二叉链表存储结构；（二）分别用递归和非递归算法实现二叉树的三种遍历； （三）模拟WindowsXP资源管理器中的目录管理方式,模拟实际创建目录结构,并以二叉链表形式存储,按照凹入表形式打印目录结构（以扩展先序遍历序列输入建立二叉链表结构），如下图所示: (基本要求:限定目录名为单字符;扩展:允许目录名是多字符组合) 三. 分工说明 一起编写、探讨流程图，根据流程图分工编写算法，共同讨论修改，最后上机调试修改。 四. 概要设计 实现算法，需要链表的抽象数据类型： ADT Binarytree { 数据对象：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， 实验二叉树及其先序遍历 一、实验目的： 1．明确了解二叉树的链表存储结构。 2．熟练掌握二叉树的先序遍历算法。 一、实验内容： 1．树型结构是一种非常重要的非线性结构。树在客观世界是广泛存在的，在计算 机领域里也得到了广泛的应用。在编译程序里，也可用树来表示源程序的 语法结构，在数据库系统中，数形结构也是信息的重要组织形式。 2．节点的有限集合（N大于等于0）。在一棵非空数里：（1）、有且仅 有 一个特定的根节点；（2）、当N大于1时，其余结点可分为M（M大于0） 个互不相交的子集，其中每一个集合又是一棵树，并且称为根的子树。树 的定义是以递归形式给出的。 3．二叉树是另一种树形结构。它的特点是每个结点最多有两棵子树，并且，二叉 树的子树有左右之分，其次序不能颠倒。 4．二叉树的结点存储结果示意图如下： 二叉树的存储（以五个结点为例）： 三、实验步骤 1．理解实验原理，读懂实验参考程序。 2． （1）在纸上画出一棵二叉树。 A B E C D G F (2) 输入各个结点的数据。 (3) 验证结果的正确性。 四、程序流程图 先序遍历 五、参考程序 # define bitreptr struct type1 /*二叉树及其先序边历*/ # define null 0 # define len sizeof(bitreptr) bitreptr *bt; int f,g; bitreptr /*二叉树结点类型说明*/ { char data; bitreptr *lchild,*rchild; }; preorder(bitreptr *bt) /*先序遍历二叉树*/ { if(g==1) printf("先序遍历序列为：\n"); g=g+1; if(bt) { printf("%6c",bt->data); preorder(bt->lchild); preorder(bt->rchild); } else if(g==2) printf("空树\n"); import java.util.Stack; public class MyTree{ public static void main(String[] s){ new MyTree(); } public MyTree(){ TreeNode root = init();//初始化二叉树并返回根节点 System.out.println("递归先序遍历"); preorder(root); System.out.println(); System.out.println("递归中序遍历"); inorder(root); System.out.println(); System.out.println("递归后续遍历"); posorder(root); System.out.println(); System.out.println("非递归先序遍历"); preorder(root); System.out.println(); System.out.println("非递归中序遍历"); _inorder(root); System.out.println(); System.out.println("非递归后续遍历"); _posorder(root); System.out.println(); } public void preorder(TreeNode root){//递归二叉树的前序遍历 if(root != null){ System.out.print(root.getValue());//访问节点值 preorder(root.getLeft()); preorder(root.getRight()); } } public void _preorder(TreeNode p){ Stack已知某二叉树的先序遍历和中序遍历的结果是先序遍历ABDEGCF
树的遍历(递归和非递归)
C语言实现二叉树的前序遍历(递归)
二叉树前序或中序或后序遍历
二叉树遍历C语言(递归,非递归)六种算法
树转换成二叉树-树的前序、后序的递归、非递归和层次序的非递归
二叉树的遍历(先序、中序、后序)
C++二叉树的前序,中序,后序,层序遍历的递归算法55555
二叉树前序、中序、后序遍历相互求法
用递归非递归两种方法遍历二叉树
二叉树的建立及几种简单的遍历方法
递归非递归两种算法遍历二叉树讲解
遍历二叉树老师的程序(绝对正确,实现先序、中序、后序遍历)
C语言实现二叉树的前序、中序、后续遍历(递归法)
用递归和非递归算法实现二叉树的三种遍历
二叉树及其先序遍历
java二叉树的遍历(递归非递归)
相关文档
- 二叉树非递归遍历代码
- 二叉树前序、中序、后序三种遍历的非递归算法
- 数据结构试验报告用先序中序建立二叉树后序遍历非递归
- 二叉树的非递归遍历
- 二叉树非递归遍历代码(前、中序)
- 用递归和非递归算法实现二叉树的三种遍历
- 用递归,非递归两种方法遍历二叉树
- 有序二叉树,遍历(递归,非递归)
- 二叉树非递归遍历
- 二叉树的建立及几种简单的遍历方法
- 二叉树后序遍历的非递归算法
- 二叉树后序遍历的非递归算法。
- 二叉树的递归、非递归的先序、中序、后序遍历以及层次遍历和求叶子节点数
- 后序遍历的非递归算法.doc
- 递归非递归两种算法遍历二叉树
- 非递归后序遍历二叉树
- 用递归、非递归两种方法遍历二叉树.
- 树转换成二叉树-树的前序、后序的递归、非递归和层次序的非递归
- 数据结构试验报告用先序中序建立二叉树后序遍历非递归
- 遍历二叉树(递归+非递归)实验报告