数据结构实验报告
知识范畴：树完成日期：2016年04月28日
实验题目：顺序存储完全二叉树先、中、后序遍历
实验内容及要求：
输入一个字符串，存储于一维数组。以该一维数组作为完全二叉树的存储结构，实现先、中、后序遍历，输出遍历结果。
将该完全二叉树转换为二叉链表存储结构，然后基于二叉链表存储结构再次进行先、中、后序遍历并输出遍历结果。
实验目的：掌握完全二叉树的顺序存储与链式存储结构以及遍历算法。
数据结构设计简要描述：
分别以一维数组和二叉链表为存储结构存储二叉树，并实现先序、中序、后序遍历。
算法设计简要描述：
分别以一维数组和二叉链表为存储结构存储二叉树。
以一维数组存储时，假设双亲结点的下标为i，则左儿子、右儿子的下标分别为2*i+1、2*i+2。利用递归算法分别对左子树和右子树进行遍历。
以二叉链表为存储结构时，结点数据域存储结点数据，然后依次递归左子树和右子树。
输入/输出设计简要描述：
本实验中输入和输出分别只有一次。
输入：输入一个字符串，存储到一维数组中
输出：分别以一维数组和二叉链表为存储结构存储二叉树时，先序、中序、后序遍历结果。
编程语言说明：
1.编程软件，Code Blocks 16.0；
2.代码均用C++语言实现；
3.输入输出采用C++语言的cout和cin函数；
4.程序注释采用C/C++规范；
5.动态存储分配采用C++的new和delete操作符实现
主要函数说明：
void preorder_array(char *s,int i,int count) //一维数组作为存储结构的前序遍历void midorder_array(char *s,int i,int count) //一维数组作为存储结构的中序遍历void lasorder_array(char *s,int i,int count) //一维数组作为存储结构的后序遍历void trans_tree(BiT &bt,char *s,int count,int t) //将该完全二叉树存储结构转换void preorder(BiT bt) //以二叉链表前序遍历
void midorder(BiT bt) //以二叉链表中序遍历
void lasorder(BiT bt) //以二叉链表后序遍历
程序测试简要报告：
（1）测试实例1
输入：
Please input：abcde
输出：
Preorder_array: a b d e c
Midorder_array: d b e a c
Lasorder_array: d e b c a
Preorder: a b d e c
Midorder: d b e a c
Lasorder: d e b c a
运行界面：
结论：程序输出结果与期望输出结果相符。（2）测试实例1
输入：
Please input：abcjdhr
输出：
Preorder_array: a b j d c h r
Midorder_array: j b d a h o r
Lasorder_array: j d b h r c a
Preorder: a b j d c h r
Midorder: j b d a h o r
Lasorder: j d b h r c a
运行界面：
结论：程序输出结果与期望输出结果相符。（3）测试实例1
输入：
Please input:abdnjfkrie
输出：
Preorder_array:a b n r i j e d f k
Midorder_array:r n I b e j a f d k
Lasorder_array:r I n e j b f k d a
Preorder:a b n r i j e d f k
Midorder:r n i b e j a f d k
Lasorder:r i n e j b f k d a
运行界面：
结论：程序输出结果与期望输出结果相符。（4）测试实例1
输入：
Please input：abcdefghijk
输出：
Preorder_array:a b d h i e j k c f g
Midorder_array:h d i b j e k a f c g
Lasorder_array:h i d j k e b f g c a
Preorder:a b d h i e j k c f g
Midorder:h d i b j e k a f c g
Lasorder:h i d j k e b f g c a 运行界面：
结论：程序输出结果与期望输出结果相符。
源程序代码：
#include
#include
#include
using namespace std;
typedef struct node
{
char data; //数据域
struct node *lchild; //左指针
struct node *rchild; //右指针
}*BiT,BiTNode;
void preorder_array(char *s,int i,int count) //一维数组作为存储结构的前序遍历{
if(i>count) //遍历结束时，退出
return;
cout< preorder_array(s,2*i+1,count); //递归遍历左儿子 preorder_array(s,2*i+2,count); //递归遍历右儿子 } void midorder_array(char *s,int i,int count) //一维数组作为存储结构的中序遍历{ if(i>count) //遍历结束时，退出 return; midorder_array(s,2*i+1,count); //递归遍历左儿子 cout< midorder_array(s,2*i+2,count); //递归遍历右儿子 } void lasorder_array(char *s,int i,int count) //一维数组作为存储结构的后序遍历{ if(i>count) //遍历结束时，退出 return; lasorder_array(s,2*i+1,count); //递归遍历左儿子 lasorder_array(s,2*i+2,count); //递归遍历右儿子 cout< } void trans_tree(BiT &bt,char *s,int count,int t) //将该完全二叉树存储结构转换为二叉链表 { if(t>count) //遍历结束时，退出 return; bt=new BiTNode(); bt->data=s[t]; //填充结点 bt->lchild=NULL; //左儿子置空 bt->rchild=NULL; //右儿子置空 trans_tree(bt->lchild,s,count,t*2+1); //递归遍历左儿子 trans_tree(bt->rchild,s,count,t*2+2); //递归遍历右儿子} void preorder(BiT bt) //以二叉链表前序遍历 { if(bt) //树非空 { cout< preorder(bt->lchild); //递归遍历左儿子 preorder(bt->rchild); //递归遍历右儿子 } } void midorder(BiT bt) //以二叉链表中序遍历 { if(bt) //树非空 { midorder(bt->lchild); //递归遍历左儿子 cout< midorder(bt->rchild); //递归遍历右儿子 } } void lasorder(BiT bt) //以二叉链表后序遍历 { if(bt) //树非空 { lasorder(bt->lchild); //递归遍历左儿子 lasorder(bt->rchild); //递归遍历右儿子 cout< } } int main() { int count=0,t=0; char *str=new char; cout<<"please input array:"; cin>>str; count=strlen(str); //求数组长度 cout<<"preorder_array:"; preorder_array(str,0,count); cout< cout<<"midorder_array:"; midorder_array(str,0,count); cout< cout<<"lasorder_array:"; lasorder_array(str,0,count); cout< BiT bt; trans_tree(bt,str,count,t); cout< cout<<"preorder:"; preorder(bt); cout< cout<<"midorder:"; midorder(bt); cout< cout<<"lasorder:"; lasorder(bt); cout< return 0; } 树与二叉树复习 一、填空 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个结点的完全二叉树，则该树的最小 树和二叉树 以下问题要求统一在一个大程序里解决。 10、按先序遍历的扩展序列建立二叉树的存储结构 11、二叉树先序、中序、后序遍历的递归算法 12、二叉树中序遍历的非递归算法 13、二叉树层次遍历的非递归算法 14、求二叉树的深度(后序遍历) 15、建立树的存储结构 16、求树的深度 17、 源程序代码： // tree.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include "stdio.h" #include "stdlib.h" #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define OVERFLOW -1 typedef char TElemType; // 元素数据类型 typedef int Status; /* 二叉链表储存结构*/ typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; bool CreateBiTree(BiTree &T) { //先序序列建立二叉树 char ch; scanf("%c",&ch); if (ch=='*') T = NULL; else { if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR; T->data = ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } return OK; } Status PrintElement(TElemType e) { // 访问函数 printf("%c", e); return OK; } Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType)) { //先序遍历二叉树的递归算法 if (T) { if (Visit(T->data)) if (PreOrderTraverse(T->lchild, Visit)) if (PreOrderTraverse(T->rchild, Visit)) return OK; return ERROR; }else return OK; } Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType)) { //中序遍历二叉树的递归算法 if (T) { if (InOrderTraverse(T->lchild, Visit)) if (Visit(T->data)) if (InOrderTraverse(T->rchild, Visit)) return OK; return ERROR; }else return OK; 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); 实验题目：实验九——二叉树实验 算法设计（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 （） 实验三二叉树的遍历 一、实验目的 １、熟悉二叉树的结点类型和二叉树的基本操作。 ２、掌握二叉树的前序、中序和后序遍历的算法。 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); } 实验三二叉树的基本运算 一、实验目的 1、使学生熟练掌握二叉树的逻辑结构和存储结构。 2、熟练掌握二叉树的各种遍历算法。 二、实验内容 题目一：二叉树的基本操作实现（必做题） [问题描述] 建立一棵二叉树，试编程实现二叉树的如下基本操作： 1. 按先序序列构造一棵二叉链表表示的二叉树T； 2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列； 3. 求二叉树的深度/结点数目/叶结点数目；(选做) 4. 将二叉树每个结点的左右子树交换位置。（选做） [基本要求] 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）， [测试数据] 如输入：ABCффDEфGффFффф（其中ф表示空格字符） 则输出结果为 先序：ABCDEGF 中序：CBEGDFA 后序：CGEFDBA 层序：ABCDEFG [选作内容] 采用非递归算法实现二叉树遍历。 三、算法设计 1、主要思想：根据二叉树的图形结构创建出二叉树的数据结构，然后 用指针对树进行操作，重点掌握二叉树的结构和性质。 2、本程序包含四个模块： （1）结构体定义 （2）创建二叉树 （3）对树的几个操作 （4）主函数 四、调试分析 这是一个比较简单程序，调试过程中并没有出现什么问题，思路比较清晰 五、实验结果 六、总结 此次上机实验对二叉树进行了以一次实际操作，让我对二叉树有了更深的了解，对二叉树的特性有了更熟悉的认知，让我知 道了二叉树的重要性和便利性，这对以后的编程有更好的帮助。 七、源程序 #include 实践三：树的应用 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）掌握二叉树的先序、中序和后序遍历算法。 【实验内容】 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)))) 包含二叉树的顺序存储，插入，删除结点，以及设置root结点，和前序、中序、后序、按层次遍历的完成代码。 #include int BTreeAddNode(CBTree *bt,CBTree *node,int n) { if(bt==NULL) { cout<<"no parent!"< return 0; } else bt->right=node; break; default: cout<<"it's wrong!"< #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); //*************************************************** 江南大学通信与控制工程学院标准实验报告 （实验）课程名称：计算机软件技术基础实验名称：二叉树的遍历和应用 班级：自动化 姓名：李玉书 学号：03 指导教师：卢先领 江南大学通信与控制学院 江南大学 实验报告 学生姓名：张晓蔚学号：0704090304 实验地点：信控机房实验时间：90分钟 一、实验室名称：信控学院计算中心 二、实验项目名称：二叉树的遍历和应用 三、实验学时：4学时 四、实验原理： 二叉树的遍历和应用 五、实验目的： 1、掌握二叉树的数据类型描述及特点。 2、掌握二叉树的存储结构（二叉链表）的建立算法。 3、掌握二叉链表上二叉树的基本运算的实现。 六、实验内容： 阅读后面的程序，并将其输入到计算机中，通过调试为下面的二叉树建立二叉链表，并用递归实现二叉树的先序、中序、后序三种遍历。 七、实验器材（设备、元器件）： 计算机 八、实验步骤： 1、输入示例程序 2、构建按序插入函数实现算法 3、用C语言实现该算法 4、与源程序合并，编译，调试 5、测试，查错，修改 6、生成可执行文件，通过综合测试，完成实验 九、实验数据及结果分析： 测试用例 初始数据：ABDH,,I,,EJ,,K,,CFL,,,G,, 测试结果 十、实验结论： 该程序可以完成线性表的常规功能，且增加了异常处理，在异常情况下，例如： 表空，删除结点号不合法或出界，删除数值未找到等，这些情况下都能作出处理。可以通过边界测试。 十一对本实验过程及方法、手段的改进建议： 对书中程序的几点错误做了改正，见源程序。 附：源程序 #include 《数据结构与数据库》 实验报告 实验题目 二叉树的基本操作及运算 学院：化学与材料科学学院 专业班级：09级材料科学与工程系PB0920603 姓名：李维谷 学号：PB09206285 邮箱：liwg@https://www.doczj.com/doc/ed5741403.html, 指导教师：贾伯琪 实验时间：2010年10月17日 一、需要分析 问题描述： 实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目，以及二叉树常用运算。 问题分析： 二叉树树型结构是一类重要的非线性数据结构，对它的熟练掌握是学习数据结构的基本要求。由于二叉树的定义本身就是一种递归定义，所以二叉树的一些基本操作也可采用递归调用的方法。处理本问题，我觉得应该： 1、建立二叉树； 2、通过递归方法来遍历（先序、中序和后序）二叉树； 3、通过队列应用来实现对二叉树的层次遍历； 4、借用递归方法对二叉树进行一些基本操作，如：求叶子数、树的深度宽度等； 5、运用广义表对二叉树进行广义表形式的打印。 算法规定： 输入形式：为了方便操作，规定二叉树的元素类型都为字符型，允许各种字符类型的输入，没有元素的结点以空格输入表示，并且本实验是以先序顺序输入的。 输出形式：通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印，再以广义表形式进行打印。对二叉树的一些运算结果以整型输出。 程序功能：实现对二叉树的先序、中序和后序遍历，层次遍历。计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目。对二叉树的某个元素进行查找，对二叉树的某个结点进行删除。 测试数据：输入一：ABC□□DE□G□□F□□□（以□表示空格）,查找5,删除E 预测结果：先序遍历ABCDEGF 中序遍历CBEGDFA 后序遍历CGEFDBA 层次遍历ABCDEFG #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 在左子树中递归。 实验8 二叉树的遍历与应用 一、实验目的 1.进一步掌握指针变量的含义。 2.掌握二叉树的结构特征，理解并熟悉掌握创建二叉树和实现二叉树的三种遍历。 3.学会编写实现二叉树基本操作的递归算法，领会递归的实质。 二、实验要求 1. 给出程序设计的基本思想、原理和算法描述。 2. 源程序给出注释。 3. 保存和打印出程序的运行结果，并结合程序进行分析。 三、实验题目 1.编写算法，按层输出一棵顺序存储的二叉树所有结点的值。 /**********level.c************/ #include 二叉树实验报告 09信管石旭琳 20091004418 一、实验目的： 1、理解二叉树的遍历算法及应用 2、理解哈夫曼树及其应用。 3、掌握哈夫曼编码思想。 二、实验内容： 1、建立二叉树二叉链表 2、实现二叉树递归遍历算法（中序、前序、后序） 3、求二叉树高度 4、求二叉树结点个数 5、求二叉树叶子个数 6、将序号为偶数的值赋给左子树 三、主要程序： #include 本程序由SOGOF完成 该完整程序主要是递归函数的使用及模板的使用，完成了对二叉树基本的链表操作，主要有二叉树的建立，前序、中序、后序遍历，求树的高度，每层结点数（包含树的最大宽度），左右结点对换，二叉树的内存释放，求解树的叶子数。 #include 二叉树的遍历实验报告 一、需求分析 在二叉树的应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理，这就是二叉树的遍历问题。 对二叉树的数据结构进行定义，建立一棵二叉树，然后进行各种实验操作。 二叉树是一个非线性结构，遍历时要先明确遍历的规则，先访问根结点还时先访问子树，然后先访问左子树还是先访问有右子树，这些要事先定好，因为采用不同的遍历规则会产生不同的结果。本次实验要实现先序、中序、后序三种遍历。 基于二叉树的递归定义，以及遍历规则，本次实验也采用的是先序遍历的规则进行建树的以及用递归的方式进行二叉树的遍历。 二、系统总框图 三、各模块设计分析 （1）建立二叉树结构 建立二叉树时，要先明确是按哪一种遍历规则输入，该二叉树是按你所输入的遍历规则来建立的。本实验用的是先序遍历的规则进行建树。 二叉树用链表存储来实现，因此要先定义一个二叉树链表存储结构。因此要先定义一个结构体。此结构体的每个结点都是由数据域data 、左指针域Lchild 、右指针域Rchild 组成，两个指针域分别指向该结点的左、右孩子，若某结点没有左孩子或者右孩子时，对应的指针域就为空。最后，还需要一个链表的头指针指向根结点。 要注意的是，第一步的时候一定要先定义一个结束标志符号，例如空格键、＃等。当它遇到该标志时，就指向为空。 建立左右子树时，仍然是调用create （）函数，依此递归进行下去， 直到遇到结束标志时停止操作。 （2）输入二叉树元素 输入二叉树时，是按上面所确定的遍历规则输入的。最后，用一个返回值来表示所需要的结果。 （3）先序遍历二叉树 当二叉树为非空时，执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （4）中序遍历二叉树 当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （5）后序遍历二叉树 当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （6）主程序 需列出各个函数，然后进行函数调用。 四、各函数定义及说明 因为此二叉树是用链式存储结构存储的，所以定义一个结构体用以存储。 typedef struct BiTNode { char data; struct BiTNode *Lchild; struct BiTNode *Rchild;已知某二叉树的先序遍历和中序遍历的结果是先序遍历ABDEGCF
求树和二叉树的深度题目及源程序代码
C语言实现二叉树的前序遍历(递归)
二叉树前序或中序或后序遍历
二叉树实验报告
数据结构二叉树实验报告
实验三二叉树的基本操作
二叉树的遍历(先序、中序、后序)
C++二叉树的前序,中序,后序,层序遍历的递归算法55555
二叉树的建立和遍历的实验报告doc
完整二叉树实例程序
二叉树的建立及几种简单的遍历方法
实验四 二叉树的遍历和应用04
《二叉树基本操作实验报告》
遍历二叉树老师的程序(绝对正确,实现先序、中序、后序遍历)
二叉树前序、中序、后序遍历相互求法
实验八：二叉树的遍历与应用
二叉树的遍历算法实验报告
二叉树基本操作经典实例
二叉树的遍历实验报告
相关主题
文本预览