实验项目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 #include #include #include #include //二叉树链式结构定义 struct STUDENT { }; struct BinaryTreeNode { }; typedef BinaryTreeNode BinaryTree; //堆栈结构定义 struct SType { }; struct Stack { }; struct Node_Ptr *ptr; void DigitalToString(char str[],int n) temp; k=1; 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的堆栈 } bool IsEmpty(Stack &S) {//判断堆栈是否为空 } bool IsFull(Stack &S) {//判断堆栈是否为满 return true; return false; } bool GetTop(Stack &S,SType &result) {//返回堆栈S中栈顶元素 } bool Pop(Stack &S,SType &result) {//将S栈顶的值取至result中，返回出栈后的状态 } bool Push(Stack &S,SType &result) {//result进s栈，返回进栈后的状态值 } //构造一棵二 叉树 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所指的节点指针为二叉树 } void BinaryDelete(BinaryTree *BT) {//二叉树的删除 BinaryDelete(BT->LChild); BinaryDelete(BT->RChild); delete BT; } char char *outputstring) {//将一个元素的字符串OutputInformation转换为宽度为WidthOfData的等长字符串outputstring //例如，姓名是由四个字符组成，而WidthOfData为8，则在姓名字符串的两边分别连接两个字符，形成8个长度的字符串 left_space,right_space; i; left_space_string[16]={""}; right_space_string[16]={""}; add_space; 计算OutputInformation的字符个数 计算需要补充的字符个数 计算OutputInformation左边需要补充的字符个数 计算OutputInformation右边需要补充的字符个数 形成OutputInformation左边需要补充的空格字符串 strcat(left_space_string," "); 形成OutputInformation右边需要补充的空格字符串 strcat(right_space_string," "); 在OutputInformation左边和右边连接需要补充的空格字符串 返回WidthOfData宽度的outputstring } char Node_Ptr *element) { 线索树特有的处理与一般二叉树不同之处，在姓名的两边连接线索标志 { if(element[k].ptr->Lflag) strcpy(outputInformation,"1"); else strcpy(outputInformation,"0"); strcat(outputInformation,element[k].ptr->data.name); 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->data.name); break; } case 3: { strcat(outputInformation,element[k].ptr->data.sex); break; } case 4: { DigitalToString(outputInformation,element[k].ptr->data.age); break; } { strcat(outputInformation,element[k].ptr->data.place); break; } break; outputInformation; } void OutputBinaryTree(BinaryTreeNode *BT) { temp,*element; *p; MaxSize; BinaryTreeHigh; //BinaryHeight(BT); 定义一个用于存放二叉树结点指针的数组 对指针数组初始化，初值设为NULL element[i].ptr=NULL; 将二叉树中的每个结点指针以顺序存储结构存放到数组中 p=element[i].ptr; if (p) { { temp.ptr = p->LChild; element[2*i]=temp; } if (p->RChild) { temp.ptr = p->RChild; element[2*i+1]=temp; } } WidthOfData=5; IntervalOfData=3; // cout<<"WidthOfData="< 二维数组的行列下标变量 存放每一元素输出位置中心（距离屏幕左边界的字符数），初值为0 for(j=0;j<=pow(2,BinaryTreeHigh-1);j++) position_of_central[i][j]=0; 对深度为BinaryTreeHigh的满二叉树的所有结点计算每个结点输出的中心点位置 指向i的左子树根结点 不断推进到i编号的结点左子树中最右子孙结点 k=2*k+1; 的值就是i编号的结点左子树中最右子孙结点的编号 由k编号的结点换算出该结点是底层中从左至右第j个结点右上方 即编号为k的结点中心点垂直线左边最底层上有j个结点 计算中心点值存放在position_of_central[row][col]中的row 计算中心点值存放在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); prespace[100]; m; kk; kkk; item_max=5; 是满二叉树中每一层第1个结点的编号 输出每个数据元素多个item成员的值 { 同一行前一个输出的元素值长度的一半,同一行第一个输出的元素值前没有值输出，初值为0 同一行当前输出的元素值长度的一半，其值始终为WidthOfData的一半 是满二叉树中每一层结点的编号变化，从某层的最左边第一个结点编号kkk开始 输出满二叉树中同一层次上的每个数据元素的同一个成员的值 { outputInformation[20]={""}; *OutputInformation; if (element[kk].ptr) 获取每个数据元素的一个成员的值OutputInformation，如姓名、年龄等 OutputInformation=GetOuputInformation(item,kk,outputInformation,element); if (position_of_central[i][j]) 输出数据中点值存在时，position_of_central[i][j]非0 { outputstring[80]={""}; *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< kk++; if (position_of_central[i][j]) }//for(j=1;j<=pow(2,i-1);j++) cout< line[3]="─"; OutputLine[80]; midspace[80]; nodenumber; 对深度为BinaryTreeHigh的满二叉树从上至下，从左至右的编号，计算第i层上起始结点的编号nodenumber nodenumber=1; else 第i(i!=1)层上的第1个结点编号nodenumber 输出同一层次上的线条 { 最底层下面没有线条，所以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< cout< cout< cout< 结点编号加1 } 释放工作空间 } //三种非递归的遍历方式 void PreOrderNoRecursive(BinaryTree *BT) {//二叉树的前序遍历非递归算法 一般约定BT指向一颗二叉树的根节点 其值是假设的一个足够大的数 产生一个空栈，这一过程函数可以不在这里进行 姓名"< { 访问根节点 temp.ptr=p; 根节点指针进栈，以后回溯时候退栈 指针指向访问过的根节点的左子树 } 左子树为空时，利用堆栈回溯 if(!IsEmpty(S)) { 从堆栈中弹出回溯节点指针（该节点已经访问过） p=temp.ptr; 指针指向回溯节点的右子树 } } void InOrderNoRecursive(BinaryTree *BT) {//二叉树的中序遍历非递归算法 一般约定BT指向一颗二叉树的根节点 其值是假设的一个足够大的数 产生一个空栈，这一过程函数可以不在这里进行 姓名"< { temp.ptr=p; 根节点（未访问）指针进栈，以后回溯时候退栈 指针指向该根节点的左子树 } 左子树为空时，利用堆栈回溯 { 从堆栈中弹出回溯节点指针（该节点未访问过） p=temp.ptr; 访问根节点 指针指向回溯节点的右子树 } } void PostOrderNoRecursive(BinaryTree *BT) {//二叉树的后序遍历非递归算法 一般约定BT指向一颗二叉树的根节点 其值是假设的一个足够大的数 产生一个空栈，这一过程函数可以不在这里进行 姓名"< { 准备进站的节点进栈标志设为第一次进栈 temp.ptr=p; 根节点（未访问）指针进栈，以后回溯时候退栈 指针指向该根节点的左子树 } else { 左子树为空时，利用堆栈回溯 { 从堆栈中弹出回溯节点指针（该节点未访问过） p=temp.ptr; if(temp.status) { 访问根节点 p=NULL; } else { 改变进栈标志，重新准备进栈 Push(S,temp); 指针指向根的右子树 } } } } int BinaryNodeCount(BinaryTreeNode *BT) { S; temp; index=0; *p=BT; 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; } index; } int BinaryHeight(BinaryTreeNode *BT) { return 0; return ++HightL; return ++HightR; } void main() { S; *BT; *p[11]; choice,MaxStackSize; result,x; number[][10]={" [][10]={" 女男男女男女男女女女",}; name [][10]={" 小猫小狗小鸡小妞小孩小鸟小白小花小丑小小"}; char place[][10]={" 湖北湖南山西陕西河北河南江西江苏广东广西"}; 初始化 x.age=15+i; strcpy(x.name,name[i]); strcpy(x.number,number[i]); strcpy(x.sex,sex[i]); p[i]=MakeNode(x); 构造二叉树 while (true) cout< cout< switch(choice) { case 1: 通过二叉树的前序遍历非递归算法输出二叉树中的所有元素 二叉树的树形结构:"< 通过二叉树的前序遍历非递归算法输出二叉树中的所有元素########"< break; } 通过二叉树的中序遍历非递归算法输出二叉树中的所有元素 二叉树的树形结构:"< 通过二叉树的中序遍历非递归算法输出二叉树中的所有元素########"< break; } case 3: 通过二叉树的后序遍历非递归算法输出二叉树中的所有元素 二叉树的树形结构"< 通过二叉树的后序遍历非递归算法输出二叉树中的所有元素########"< break; } case 4: 统计二叉树中节点的个数 统计二叉树中节点的个数"< } case 5: 计算二叉树的高度 计算二叉树的高度"< 删除二叉树 删除二叉树"< break; } case 7: 输出二叉树的树形结构 输出二叉树"< break; } 退出 退出操作"< delete BT; } } system("pause"); system("cls"); }
Copyright © 2019-2025 51dongshi.net 版权所有
违法及侵权请联系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市万商天勤律师事务所王兴未律师提供法律服务
