实验六 二叉树的递归遍历及其应用(1)
实验六二叉树的递归遍历及其应用
一、实验目的
1、深入了解二叉树递归的逻辑结构特征及其基本操作。
2、了解二叉树各种存储结构的特点及其适用范围，熟练掌握二叉树的二叉链表结构的定义及其递归遍历算法、按层次遍历算法的c语言实现，能深入了解递归算法的执行过程。
3、熟练掌握二叉树递归遍历算法的应用。
一、实验内容和要求
2、设计并验证如下算法：与“12.7.4参考源程序”类似，按中序序列输入建立两棵二叉树的二叉链表结构，求双分支结点数，判断两棵树是否相等。
3、设计并验证如下算法：按层次遍历二叉树，打印结点所在的层次，并求该二叉树的宽度。
二、实验过程及结果
（第一题）
一、需求分析
1、从键盘输入二叉树的序列，但由于建树是从根结点往下建立的，故只能输入先
序序列，则按照中序建树完成二叉树的创建。
2、从键盘输入一段正确的序列后，按回车键自动生成二叉树，若该序列不能生成
一颗二叉树，则程序无法继续进行，只能退出。
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，
且存在Dr上的的关系Hr包含于H；H={
（4）（D1,{H1}）是一棵符合本定义的二叉树，称为根的左子树，（Dr,{Hr}）是一棵符合本定义的二叉树，称为根的右子树。
基本操作:
InitBiTree(&BT)
操作结果：构造空二叉树
CreateBiTree(&BT)
操作结果：建立二叉树
PreOrder(BT)
初始条件：二叉树BT已存在
操作结果：先序遍历
InOrder(BT)
初始条件：二叉树BT已存在
操作结果：中序遍历
PostOrder(BT)
初始条件：二叉树BT已存在
操作结果：后序遍历
Do_BranNumber(BT)
初始条件：二叉树BT已存在
操作结果：求BT的双分支结点数
Same_CompareTree(BT_a,BT1_b)
初始条件：二叉树BT_a、BT_b已存在
操作结果：比较两棵树是否相等
}ADT BinaryTree；
⒊本程序模块结构
⑴主函数模块
void main(){
初始化两颗二叉树；
创建二叉树BT_a，返回根结点BT_a；
getchar();
创建二叉树BT_b，返回根结点BT_b；
getchar();
先、中、后序遍历BT_a和BT_b；
if(两棵树相等)
printf("相同");
else
printf("不同");
输出BT_a和BT_b的双分支结点数；
｝
三、详细设计
1、基本数据类型操作
⑴二叉链表的存储结构
typedef char TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild; //左右孩子指针}BiTNode,*BiTree;
四、调试分析
1、创建两棵二叉树程序便不能继续运行，只能创建一棵树，加了getchar()后便能操作，原因可能是换行符造成的。
2、进行两棵树的比较时不仅要保证各结点值相等，还要确保结构相同，若结构不同，两棵树则不等，故采用递归算法。
3、求双分支结点数采用递归算法，一定要保证结束条件，此结束条件应为结点为空时返回0。
五、用户说明及测试结果
1、两棵二叉树不相等
2、两颗二叉树相等
七、附录（源代码及部分注释）
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#include "string.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
#define INFEASIBLE -2
#define Max_Tree_SIZE 20//最大结点数
typedef int Status;
typedef char TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild; //左右孩子指针
}BiTNode,*BiTree;
Status InitBiTree(BiTree *BT); //构造空二叉树
Status CreateBiTree(BiTree *BT); //建立二叉树
Status PreOrder(BiTree BT); //先序遍历
Status InOrder(BiTree BT); //中序遍历
Status PostOrder(BiTree BT); //后序遍历
int Do_BranNumber(BiTree BT); //求双分支结点数
Status Same_CompareTree(BiTree BT,BiTree BT1); //比较两棵树是否相等
void main()
{
int flag=1,select;
BiTree BT_a,BT_b;
InitBiTree(&BT_a);
InitBiTree(&BT_b);
printf("To Create Binary Tree, Please Input PreOrder with '#' :\n");//输入二叉树的先序序列，用#代表空结点
printf("Create The First Of Binary Tree(a): ");
CreateBiTree(&BT_a); //创建二叉树，返回根结点BT_a
getchar();
printf("Create The Second Of Binary Tree(b): ");
CreateBiTree(&BT_b); //创建二叉树，返回根结点BT_b
getchar();
printf("The First Of Binary Tree(a) is:\n");
printf("PreOrder Traversal: ");
PreOrder(BT_a); //先序遍历
printf("\nInOrder Traversal: ");
InOrder(BT_a); //中序遍历
printf("\nPostOrder Traversal: ");
PostOrder(BT_a); //后序遍历
printf("\n\nThe Second Of Binary Tree(b) is:\n");
printf("PreOrder Traversal: ");
PreOrder(BT_b); //先序遍历
printf("\nInOrder Traversal: ");
InOrder(BT_b); //中序遍历
printf("\nPostOrder Traversal: ");
PostOrder(BT_b); //后序遍历
if(Same_CompareTree(BT_a,BT_b))
printf("\n\nThe Binary Tree a and B is Same!\n");
else
printf("\n\nThe Binary Tree a and B is Different!\n");
printf("\nThe Binary Tree a's Number of Double Branch is: %d",Do_BranNumber(BT_a));
printf("\nThe Binary Tree b's Number of Double Branch is: %d\n\n",Do_BranNumber(BT_b));
}
/**********************InitBiTree********************/
Status InitBiTree(BiTree *BT){ //构造空二叉树
*BT=NULL;
return OK;
}
/**********************CreateBiTree********************/
Status CreateBiTree(BiTree *BT){//建立二叉树
TElemType ch;
scanf("%c",&ch);
if(ch!='#'){
*BT=(BiTree)malloc(sizeof(BiTNode));
if(!(*BT))
return OVERFLOW;
CreateBiTree(&((*BT)->lchild)); //构造左子树
(*BT)->data=ch;
CreateBiTree(&((*BT)->rchild)); //构造右子树
}
else
*BT=NULL; //读入#，返回空指针
return OK;
}
/*********************PreOrder***********************/
Status PreOrder(BiTree BT){ //先序遍历
if(BT){
if(!(BT->data))
return ERROR;
printf("%c",BT->data); //访问结点
PreOrder(BT->lchild); //先序遍历左子树
PreOrder(BT->rchild); //先序遍历右子树
}
return OK;
}
/*******************InOrder*******************/
Status InOrder(BiTree BT){ //中序遍历
if(BT){
if(!(BT->data))
return ERROR;
InOrder(BT->lchild); //中序遍历左子树
printf("%c",BT->data); //访问结点
InOrder(BT->rchild); //中序遍历右子树
}
return OK;
}
/*******************PostOrder*****************/
Status PostOrder(BiTree BT){ //后序遍历
if(BT){
if(!(BT->data))
return ERROR;
PostOrder(BT->lchild); //后序遍历左子树
PostOrder(BT->rchild); //后序遍历右子树
printf("%c",BT->data); //访问结点
return OK;
}
}
/******************Do_BranNumber*****************/
int Do_BranNumber(BiTree BT){
if(!BT)
return 0;
else{
if(BT->lchild&&BT->rchild)
return Do_BranNumber(BT->lchild)+Do_BranNumber(BT->rchild)+1;
else
return Do_BranNumber(BT->lchild)+Do_BranNumber(BT->rchild);
}
}
/*****************Same_Compare*******************/
Status Same_CompareTree(BiTree BT,BiTree BT1){//递归遍历并比较if(BT==NULL&&BT1==NULL)
return TRUE; //两棵树均为空时认为相等
else if(BT==NULL||BT1==NULL)
return FALSE;
else if(BT!=NULL&&BT1!=NULL)
{
if(BT->data==BT1->data)
{
if(Same_CompareTree(BT->lchild,BT1->lchild)&&Same_CompareTree(BT->rchild,BT1->rchild) ||
Same_CompareTree(BT->lchild,BT1->rchild)&&Same_CompareTree(BT->rchild,BT1->lchild)) {
return TRUE;
}
}
}
return FALSE;
}
二叉树遍历方法技巧
二叉树遍历方法 1.中序遍历的投影法 如果给定一棵二叉树的图形形态，是否能根据此图快速地得出其中序遍历的序列？回答是肯定的。具体做法是：首先按照二叉树的标准绘制二叉树形态，即将所有左子树都严格绘于根结点的左边；将所有右子树都严格绘于根结点的右边。然后假设现在有一个光源从该二叉树的顶部投射下来，那么所有结点在地平线上一定会有相应的投影，从左至右顺序读出投影结点的数据即为该二叉树的中序遍历序列。如图11.10所示。 图示的中序遍历序列： D J G B H E A F I C 2.先序遍历的填空法 如果给定一棵二叉树的图形形态，可在图形基础上，采用填空法迅速写出该二叉树的先序遍历序列。具体做法是：我们知道，对于每个结点都由三个要素组成，即根结点，左子树、右子树；又已知先序遍历顺序是先访问根结点、然后访问左子树、访问右子树。那么，我们按层分别展开，逐层填空即可得到该二叉树的先序遍历序列。 图11.10 中序遍历投影法示意图 如图11.10 中的二叉树采用填空法的步骤如下： (1)根结点左子树右子树 A( )( ) (2)A （根结点（左子树）（右子树））（根结点（左子树）（右子树）） A B C (3)A(B(根结点（左）（右）)(根结点（左）（右）))（C(……)(……)） A B D 无 G E H 无 C F 无 (4)A B D G J E H C F I 此即为该二叉树的先序遍历序列。 注：后序遍历的序列亦可以此方法类推，请读者自己尝试。
3.利用遍历序列构造二叉树 如果已知一棵二叉树的先序遍历序列和中序遍历序列，则可以用这两个遍历序列构造一棵唯一的二叉树形态。我们知道任意一棵二叉树的先序遍历序列和中序遍历序列是唯一的，那么首先从给定的先序遍历序列入手，该先序序列的第一个元素一定是该二叉树的根；再分析这个根结点在中序遍历序列中的位置，中序遍历序列中根结点的左边即为左子树的全部元素，而根结点的右边即为右子树的全部元素；然后据此再将先序遍历序列除根结点以外的其余部分分为左、右子树两部分，并在这两部分中分别找出左、右子树的根结点。依此类推，即可得到完整的二叉树。例11.1 已知一棵二叉树的先序遍历和中序遍历序列分别为： 先序： A B C I D E F H G 中序： C I B E D A H F G 请构造这棵二叉树。 按前述分析，这棵二叉树的构造过程如图11.11所示 图11.11 二叉树的构造过程 树、森林与二叉树的转换(flash演示) 如前所述，树（或森林）的存储结构及其操作算法的实现，由于其“度”的不确定性而导致其存储结构不是较为复杂就是浪费空间，因而，定义在其存储结构上的算法也相应地较难兼顾全面。如果我们设定一定的规则，用二叉树来表示树和森林的话，就可以方便地解决树、森林的存储结构及其相关算法问题。 1.树、森林转换为二叉树 我们知道，一棵树中每个结点的孩子是无序的，而二叉树中各结点的孩子必须有左右之分。在此，为避免概念混淆，首先约定树中每个结点的孩子按从左至右的顺序升序编号，即将树中同一层上的兄弟分出大小。那么将一棵树转换成二叉树的方法是： （1）在树中同层兄弟间加一连线； （2）对树中每个结点仅保留其与长兄（左边第一个孩子）的连线，擦去其与其它孩子的连线； （3）以树（或子树）的根作为轴心，将所有的水平连线顺时针旋转45度，即可得到与该树完全等价的一棵二叉树。
数据结构实验六二叉树操作代码实现
#include
if (treeNode->data == data) { return treeNode; } else//分别向左右子树查找 { if (ptr = TreeFindNode(treeNode->left, data))//左子树递归查找 { return ptr; } else if (ptr = TreeFindNode(treeNode->right, data))//右子树递归查找 { return ptr; } else { return NULL; } } } } /**********************添加结点*************************/ void AddTreeNode(CBTType *treeNode) { CBTType *pnode, *parent; DATA data; char menusel; if (pnode = new CBTType) //分配内存 { cout << "输入添加的二叉树结点数据：" << endl; cin >> pnode->data; pnode->left = NULL; //设置左子树为空 pnode->right = NULL; //设置左子树为空 cout << "输入该结点的父结点数据:" << endl; cin >> data; parent = TreeFindNode(treeNode, data); //查找父结点，获得结点指针 if (!parent) //没找到 { cout << "没有找到父结点!" << endl; delete pnode; return; } cout << "**********************" << endl;
二叉树遍历所有代码
#include
数据结构二叉树实验报告
实验三二叉树的遍历 一、实验目的 １、熟悉二叉树的结点类型和二叉树的基本操作。 ２、掌握二叉树的前序、中序和后序遍历的算法。 3、加深对二叉树的理解，逐步培养解决实际问题的编程能力。 二、实验环境 运行Ｃ或VC++的微机。 三、实验内容 1、依次输入元素值，以链表方式建立二叉树，并输出结点的值。 2、分别以前序、中序和后序遍历二叉树的方式输出结点内容。 四、设计思路 1. 对于这道题，我的设计思路是先做好各个分部函数，然后在主函数中进行顺序排列，以此完成实验要求 2．二叉树采用动态数组 3.二叉树运用9个函数，主要有主函数、构建空二叉树函数、建立二叉树函数、访问节点函数、销毁二叉树函数、先序函数、中序函数、后序函数、范例函数，关键在于访问节点 五、程序代码 #include
int data; //数据域 struct TNode *lchild,*rchild; // 指针域包括左右孩子指针 }TNode,*Tree; void CreateT(Tree *T)//创建二叉树按,依次输入二叉树中结点的值 { int a; scanf("%d",&a); if(a==00) // 结点的值为空 *T=NULL; else // 结点的值不为空 { *T=(Tree)malloc(sizeof(TNode)); if(!T) { printf("分配空间失败！！TAT"); exit(ERROR); } (*T)->data=a; CreateT(&((*T)->lchild)); // 递归调用函数，构造左子树 CreateT(&((*T)->rchild)); // 递归调用函数，构造右子树 } } void InitT(Tree *T)//构建空二叉树 { T=NULL; } void DestroyT(Tree *T)//销毁二叉树 { if(*T) // 二叉树非空 { DestroyT(&((*T)->lchild)); // 递归调用函数，销毁左子树 DestroyT(&((*T)->rchild)); // 递归调用函数，销毁右子树 free(T); T=NULL; } } void visit(int e)//访问结点 { printf("%d ",e); }
二叉树实验报告
实验题目：实验九——二叉树实验 算法设计（3） 问题分析： 1、题目要求：编写算法交换二叉树中所有结点的左右子树 2、设计思路：首先定义一个二叉树的数据类型，使用先序遍历建立该二叉树，遍历二叉树，设计左右子树交换的函数，再次遍历交换之后的二叉树，与先前二叉树进行比较。遍历算法与交换算法使用递归设计更加简洁。 3、测试数据： A、输入：1 2 4 0 0 5 0 0 3 0 0 交换前中序遍历：4 2 5 1 3 交换后中序遍历：3 1 5 2 4 交换前：交换后： B、输入：3 7 11 0 0 18 17 0 0 19 0 0 6 13 0 0 16 0 0 交换前中序遍历：11 7 17 18 19 3 13 6 16 交换后中序遍历：16 6 13 3 19 18 17 7 11 概要设计： 1、为了实现上述功能：①构造一个空的二叉树；②应用先序遍历输入，建立二叉树；③中序遍历二叉树；④调用左右子树交换函数；⑤中序遍历交换过后的二叉树。 2、本程序包括4个函数： ①主函数main（） ②先序遍历二叉树建立函数creat_bt（） ③中序遍历二叉树函数inorder（） ④左右子树交换函数 exchange（）
各函数间关系如下： 详细设计： 1、结点类型 typedef struct binode //定义二叉树 { int data; //数据域 struct binode *lchild,*rchild; //左孩子、右孩子 }binode,*bitree; 2、各函数操作 ① 先序遍历建二叉树函数 bitree creat_bt() { 输入结点数据； 判断是否为0{ 若是，为空； 不是，递归；} 返回二叉树； } ② 左右子树交换函数 void exchange(bitree t) { 判断结点是否为空{ 否，交换左右子树； 递归；} } ③ 中序遍历函数 void inorder(bitree bt) { 判断是否为空{ 递归左子树； 输出； 递归右子树；} } main （） creat_bt （） inorder （） exchange （）
实验三 二叉树的基本操作实现及其应用
二叉树的基本操作实现及其应用 一、实验目的 1．熟悉二叉树结点的结构和对二叉树的基本操作。 2．掌握对二叉树每一种操作的具体实现。 3．学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。 4.会用二叉树解决简单的实际问题。 二、实验内容 设计程序实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。 1 按先序次序建立一个二叉树， 2按（A:先序 B:中序 C:后序）遍历输出二叉树的所有结点 以上比做，以下选做 3求二叉树中所有结点数 4求二叉树的深度 三、实验步骤 ㈠、数据结构与核心算法的设计描述 /* 定义DataType为char类型 */ typedef char DataType; /* 二叉树的结点类型 */ typedef struct BitNode { DataType data; struct BitNode *lchild,*rchild; }*BitTree; 相关函数声明： 1、/* 初始化二叉树，即把树根指针置空 */ void BinTreeInit(BitTree *BT) { BT=(BitTree)malloc(sizeof(BitNode)); BT->data=NULL; cout<<"二叉树初始化成功!"<
二叉树遍历C语言(递归,非递归)六种算法
数据结构（双语） ——项目文档报告用两种方式实现表达式自动计算 专业： 班级： 指导教师： 姓名： 学号：
目录 一、设计思想 (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，且栈为空，则遍历结束。若指针指向了左子，则将左子作为当前结点，判断其左右子情况，按上述方法处理，直至遍历结束。
数据结构实验二叉树
实验六：二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。 二、问题描述 首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：a+b*(c-d)-e/f 三、实验要求 如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算统计叶子结点的个数。求二叉树的深度。十进制的四则运算的计算器可以接收用户来自键盘的输入。由输入的表达式字符串动态生成算术表达式所对应的二叉树。自动完成求值运算和输出结果。四、实验环境 PC微机 DOS操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 五、实验步骤 1、根据二叉树的各种存储结构建立二叉树； 2、设计求叶子结点个数算法和树的深度算法； 3、根据表达式建立相应的二叉树，生成表达式树的模块； 4、根据表达式树，求出表达式值，生成求值模块； 5、程序运行效果，测试数据分析算法。 六、测试数据 1、输入数据：*（+）3 正确结果： 2、输入数据：(1+2)*3+(5+6*7);
正确输出：56 七、表达式求值 由于表达式求值算法较为复杂，所以单独列出来加以分析： 1、主要思路：由于操作数是任意的实数，所以必须将原始的中缀表达式中的操作数、操作符以及括号分解出来，并以字符串的形式保存；然后再将其转换为后缀表达式的顺序，后缀表达式可以很容易地利用堆栈计算出表达式的值。 例如有如下的中缀表达式： a+b-c 转换成后缀表达式为： ab+c- 然后分别按从左到右放入栈中，如果碰到操作符就从栈中弹出两个操作数进行运算，最后再将运算结果放入栈中，依次进行直到表达式结束。如上述的后缀表达式先将a 和b 放入栈中，然后碰到操作符“+”，则从栈中弹出a 和b 进行a+b 的运算，并将其结果d（假设为d）放入栈中，然后再将c 放入栈中，最后是操作符“-”，所以再弹出d和c 进行d-c 运算，并将其结果再次放入栈中，此时表达式结束，则栈中的元素值就是该表达式最后的运算结果。当然将原始的中缀表达式转换为后缀表达式比较关键，要同时考虑操作符的优先级以及对有括号的情况下的处理，相关内容会在算法具体实现中详细讨论。 2、求值过程 一、将原始的中缀表达式中的操作数、操作符以及括号按顺序分解出来，并以字符串的 形式保存。 二、将分解的中缀表达式转换为后缀表达式的形式，即调整各项字符串的顺序，并将括 号处理掉。 三、计算后缀表达式的值。 3、中缀表达式分解 DivideExpressionToItem()函数。分解出原始中缀表达式中的操作数、操作符以及括号，保存在队列中，以本实验中的数据为例，分解完成后队列中的保存顺序如下图所示：
二叉树的建立和遍历的实验报告doc
二叉树的建立和遍历的实验报告 篇一：二叉树的建立及遍历实验报告 实验三：二叉树的建立及遍历 【实验目的】 （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 -2 typedef 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))))
二叉树遍历课程设计】汇编
数据结构程序设计报告 学院： 班级： 学号： 姓名：
实验名称：二叉树的建立与遍历 一、实验目的： 1.掌握二叉树的二叉链表存储结构； 2.掌握二叉树创建方法； 3.掌握二叉树的先序、中序、后序的递归实现方法。 二、实验内容和要求： 创建二叉树，分别对该二叉树进行先序、中序、后序遍历，并输出遍历结果。 三、叉树的建立与遍历代码如下： #include
int front=0,rear=-1,counter=0;//初始队列中需要的变量front、rear和计数器counter char ch; printf("建立二叉树，请输入结点:（#表示虚节点,!表示结束)\n"); ch=getchar(); while(ch!='!') { if(ch!='#') { p=(TNODE *)malloc(sizeof(TNODE)); p->data=ch; p->lchild=NULL; p->rchild=NULL; rear++; queue[rear]=p;//把非#的元素入队 if(rear==0)//如果是第一个元素，则作为根节点 { root=p; counter++; } else { if(counter%2==1)//奇数时与其双亲的左子树连接 { queue[front]->lchild=p; } if(counter%2==0)//偶数时与其双亲的右子树连接 { queue[front]->rchild=p;
实验四 二叉树的遍历和应用04
江南大学通信与控制工程学院标准实验报告 （实验）课程名称：计算机软件技术基础实验名称：二叉树的遍历和应用 班级：自动化 姓名：李玉书 学号：03 指导教师：卢先领 江南大学通信与控制学院
江南大学 实验报告 学生姓名：张晓蔚学号：0704090304 实验地点：信控机房实验时间：90分钟 一、实验室名称：信控学院计算中心 二、实验项目名称：二叉树的遍历和应用 三、实验学时：4学时 四、实验原理： 二叉树的遍历和应用 五、实验目的： 1、掌握二叉树的数据类型描述及特点。 2、掌握二叉树的存储结构（二叉链表）的建立算法。 3、掌握二叉链表上二叉树的基本运算的实现。 六、实验内容： 阅读后面的程序，并将其输入到计算机中，通过调试为下面的二叉树建立二叉链表，并用递归实现二叉树的先序、中序、后序三种遍历。 七、实验器材（设备、元器件）： 计算机 八、实验步骤： 1、输入示例程序 2、构建按序插入函数实现算法 3、用C语言实现该算法 4、与源程序合并，编译，调试 5、测试，查错，修改
6、生成可执行文件，通过综合测试，完成实验 九、实验数据及结果分析： 测试用例 初始数据：ABDH,,I,,EJ,,K,,CFL,,,G,, 测试结果 十、实验结论： 该程序可以完成线性表的常规功能，且增加了异常处理，在异常情况下，例如： 表空，删除结点号不合法或出界，删除数值未找到等，这些情况下都能作出处理。可以通过边界测试。 十一对本实验过程及方法、手段的改进建议： 对书中程序的几点错误做了改正，见源程序。 附：源程序 #include
实验八：二叉树的遍历与应用
实验8 二叉树的遍历与应用 一、实验目的 1.进一步掌握指针变量的含义。 2.掌握二叉树的结构特征，理解并熟悉掌握创建二叉树和实现二叉树的三种遍历。 3.学会编写实现二叉树基本操作的递归算法，领会递归的实质。 二、实验要求 1. 给出程序设计的基本思想、原理和算法描述。 2. 源程序给出注释。 3. 保存和打印出程序的运行结果，并结合程序进行分析。 三、实验题目 1.编写算法，按层输出一棵顺序存储的二叉树所有结点的值。 /**********level.c************/ #include
二叉树的基本操作实验
实验三二叉树的基本运算 一、实验目的 1、使学生熟练掌握二叉树的逻辑结构和存储结构。 2、熟练掌握二叉树的各种遍历算法。 二、实验内容 [问题描述] 建立一棵二叉树，试编程实现二叉树的如下基本操作： 1. 按先序序列构造一棵二叉链表表示的二叉树T； 2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列； 3. 求二叉树的深度/结点数目/叶结点数目；(选做) 4. 将二叉树每个结点的左右子树交换位置。（选做） [基本要求] 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）， [测试数据] 如输入：ABCффDEфGффFффф（其中ф表示空格字符） 则输出结果为 先序：ABCDEGF 中序：CBEGDFA 后序：CGEFDBA 层序：ABCDEFG [选作内容] 采用非递归算法实现二叉树遍历。 三、实验前的准备工作 1、掌握树的逻辑结构。 2、掌握二叉树的逻辑结构和存储结构。 3、掌握二叉树的各种遍历算法的实现。 一实验分析 本次试验是关于二叉树的常见操作，主要是二叉树的建立和遍历。二叉树的遍历有多种方法，本次试验我采用递归法，递归法比较简单。 二概要设计 功能实现
1.int CreatBiTree(BiTree &T) 用递归的方法先序建立二叉树, 并用链表储存该二叉树 2.int PreTravel(BiTree &T) 前序遍历 3. int MidTravel(BiTree &T) 中序遍历 4.int PostTravel(BiTree &T) 后序遍历 5.int Depth(BiTree &T) //计算树的深度 6.int howmuch(BiTree T,int h) 采用树节点指针数组，用于存放遍历到的元素地址，如果有左孩子，存入地址，j加一，否则没操作，通过访问数组输出层次遍历的结果。k计算叶子数，j为总节点。 7. int exchang(BiTree &T) 交换左右子树，利用递归，当有左右孩子时才交换 三详细设计 #include
基于二叉树遍历系统设计与实现
长春建筑学院《数据结构》课程设计（论文） 基于二叉树遍历系统设计与实现Binary tree traversal System Design and Implementation 年级: 学号: 姓名: 专业: 指导老师: 二零一三年十二月
摘要 针对现实世界中许多关系复杂的数据，如人类社会的家谱，各种社会组织机构,博弈交通等复杂事物或过程以及客观世界中广泛存在的具有分支关系或层次特性的对象．如操作系统的文件构成、人工智能和算法分析的模型表示以及数据库系统的信息组织形式等，用线性结构难以把其中的逻辑关系表达出来，必须借助于数和图这样的非线性结构，因此在以模拟客观世界问题，解决客观世界问题为主要任务的计算机领域中树型结构是信息的一种重要组织形式，树有着广泛应用。在树型结构的应用中又以二叉树最为常用。 二叉树是一种非常重要的非线性结构，所描述的数据有明显的层次关系，其中的每个元素只有一个前驱，二叉树是最为常用的数据结构，它的实际应用非常广泛，二叉树的遍历方式有三种，前序遍历，中序遍历，后序遍历，先序遍历的顺序为：NLR 先根结点，然后左子树，右子树；中序遍历顺序为；LNR先左子树，然后根结点，右子树；后序遍历顺序为：LRN先左子树，然后右子树，根结点。由前序和中序遍历，有中序和后序遍历序列可以唯一确定一棵二叉树。 对于给几个数据的排序或在已知的几个数据中进行查找，二叉树均能提供一种十分有效的方法，比如在查找问题上，任何借助于比较法查找长度为Ⅳ的一个序表的算法，都可以表示成一株二叉树。反之，任何二叉树都对应一个查找有序表的有效方法根据树的数学理论，对于算法分析的某些最有启发性的应用，是与给出用于计算各种类型中不同树的数目的公式有关的。 本文对二叉树以及二叉树的各种功能做介绍以及写出一些基本的程序，让读者对二叉树的理解有更好的效果。 关键词：二叉树；左子树；右子树
实验六 最优二叉树的应用
实验六最优二叉树的应用 【实验目的】 掌握求最优二叉树的方法。 【实验内容】 最优二叉树在通信编码中的应用。要求输入一组通信符号的使用频率 {2,3,5,7,11,13,17,19,23,29,31,37,41}，求各通信符号对应的前缀码。 【实验原理和方法】 （1）用一维数组f[N]存贮通信符号的使用频率，用求最优二叉树的方法求得每个通信符号的前缀码。 （2）用链表保存最优二叉树，输出前缀码时可用树的遍历方法。 #include
struct tree *temp; for(i=N-n;i
二叉树的遍历算法实验报告
二叉树实验报告 09信管石旭琳 20091004418 一、实验目的： 1、理解二叉树的遍历算法及应用 2、理解哈夫曼树及其应用。 3、掌握哈夫曼编码思想。 二、实验内容： 1、建立二叉树二叉链表 2、实现二叉树递归遍历算法（中序、前序、后序） 3、求二叉树高度 4、求二叉树结点个数 5、求二叉树叶子个数 6、将序号为偶数的值赋给左子树 三、主要程序： #include
实验六二叉树
实验六二叉树
#include
while (a[i]) { switch(a[i]) { case ' ': break; case '(': if (top==MaxSize-1) { cout<<""< top--; break; case ',': k=2; break; default: p=new BTreeNode; p->data=a[i]; p->left=p->right=NULL; if(BT==NULL) BT=p; else { if(k==1) s[top]->left=p; else s[top]->right=p; } } i++; } } 南昌大学实验报告 学生姓名：李木子学号：专业班级：软工 实验类型：□验证□综合□设计□创新实验日期：实验成绩：一、实验项目名称 二叉树的遍历 二、实验目的 学会链式二叉树的结构体定义，创建与前序中序后序遍历三、实验基本原理 四、主要仪器设备及耗材 电脑， 五、实验步骤 ************************************** * 链式二叉树的创建与遍历 * ************************************** ************************************** * 链式二叉树的结构体定义 * ************************************** <> <> ; { ; *; *; }; ************************************** * 链式二叉树函数声明 * ************************************** *(); (*); (*); (*); ************************************** * 链式二叉树创建函数 * ************************************** *() { ; *; (); ('') ; ('\'); { (*)(()); >; >(); >(); } ; } ************************************** * 链式二叉树递归前序遍历函数 * ************************************** (*) { () { ("\">); 实验四二叉树的基本操作 一、实验目的 1. 通过实验，掌握二叉树的建立与存储 2. 通过实验，掌握二叉树的遍历方法 二、实验内容 1. 练习二叉树的建立与存储 2. 练习二叉树的遍历 三、实验步骤 1. 建立自己的头文件BT.H，内容包括二叉链表的结构描述、二叉树存储结构（二叉链表）的建立、二叉树的先序、中序与后序遍历算法。 2. 建立二叉树,并通过调用函数, 建立二叉树的存储结构（二叉链表）、输出先序遍历、中序遍历与后序遍历的结果。 四、实现提示 建立二叉树存储结构时采用的二叉树的定义方法（即课上讲的第一种方法，参看课件）：以字符串形式“根左子树右子树”定义一颗二叉树。 五、测试数据 1、AB#C##D## 2、ABC##DE#G##F##H## 实验六图 一、实验目的 1. 掌握图的基本存储方法； 2. 掌握有关图的操作算法并用高级语言实现； 3. 熟练掌握图的两种搜索路径的遍历方法。 二、实验内容 假设以一个带权有向图表示某一区域的公交线路网，图中顶点代表一些区域中的重要场所，弧代表已有的公交线路，弧上的权表示该线路上的票价（或搭乘所需时间），试设计一个交通指南系统，指导前来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。 三、实验步骤 1. 定义结点结构，定义图结构。 2.存储图信息； 3. 定义求任意两点最短路径函数； 4. 写出主函数。 四、实现提示 typedef struct node { int no; float wgt; struct node *next; }edgenode; typedef struct { char vtx; edgenode *link; }vexnode; typedef vexnode Graph[n]; void Floyd(Graph G, float A[n][n], int p[n][n]) {数据结构实验二叉树的遍历
二叉树实验要求