实验4 树和二叉树

实验4: 树和二叉树基本操作验证

一、预习要求

1.熟悉树的定义及基本性质。

2.熟悉树的各种存储方法及遍历方法。

3.熟悉二叉树的定义及基本性质。

4.熟悉二叉树的各种存储方法及遍历方法。

二、实验目的

1.掌握树的逻辑结构和孩子兄弟存储结构。

2.掌握基于树的孩子兄弟存储结构的遍历方法。

3.掌握二叉树的逻辑结构和二叉链表存储结构。

4.掌握基于二叉链表存储的二叉树的遍历操作的实现。

三、实验内容

1. 二叉树操作验证。

a)建立一棵含有n个结点的二叉树，

问题分析：

已知：二叉树的先序遍历和中序遍历序列（或中序遍历和后序遍历序列），构建二叉树，采用二叉链表存储，并进行后序遍历。

●建立结点的结构体类型；

typedef int TElemType; // TElemType为二叉树结点的数据类型typedef struct BiTNode { // 结点结构

TElemType data;

struct BiTNode *lchild, *rchild; // 左右孩子指针

} BiTNode, *root;// root为指向二叉链表根结点的指针

●动态申请内存空间存储新结点，对新结点进行初始化；

●建立结点间的关系；

b)前序（或中序、后序）遍历该二叉树

2.树操作验证。

c)采用孩子兄弟表示法建立一棵树

d)基于孩子兄弟表示法存储的树实现前序遍历操作

3.编写完整程序完成以上实验内容并调试运行。

4.整理并提交实验报告。

先序序列：ABDGCEF

中序序列:DGBAECF Pos(int m,char pin[],int k) {

Pin[]=”DGBAECF”;

For(i=k;i

{if(m==pin[i])

Return i;

}

}

实验三 二叉树的操作及应用

实验三二叉树的操作及应用 实验课程名：数据结构与算法 专业班级：15计科1班学号：201540410109 姓名：刘江 实验时间：2016.10.24-10.31 实验地点：K4-102 指导教师：冯珊 成绩: 一、实验目的及要求 1、进一步掌握指针变量、动态变量的含义。 2、掌握二叉树的结构特性，以及各种存储结构的特点和适用范围。 3、掌握用指针类型描述、访问和处理二叉树的运算。 二、实验内容 任务一：完成下列程序，该程序以二叉链表作存储结构，构建如图1所示的二叉树， 并依次进行二叉树的前序、中序、后序及层次遍历。 图1 解答： （1）源代码：#include #include #define OK 1 #define ERROR 0 typedef char DataType; /* 二叉树节点的存储类型 */ typedef struct Node //define stricture BiTree { DataType data; struct Node *lchild,*rchild; }Node, *BiTree; /*按先序序列建立一棵二叉树*/ BiTree CreatBiTree(BiTree &T) { DataType ch; scanf("%c",&ch); if(ch==' ') {T=NULL;}

else { if(!(T=(Node*)malloc(sizeof(Node)))){printf("Overflow.\n") ;exit(0);} T->data =ch; CreatBiTree(T->lchild ); CreatBiTree(T->rchild ); } return T; } void PrintData(DataType x) { printf("%c",x); } void PreOrder(BiTree T, void (*Visit)( DataType item)) /*前序遍历二叉树T，访问操作为Visit()函数*/ { if(T!= NULL) { Visit(T->data); PreOrder(T->lchild, Visit); PreOrder(T->rchild, Visit); } } void InOrder(BiTree T, void (*Visit)( DataType item)) /*中序t */ { if(T!= NULL) { InOrder(T->lchild, Visit); Visit(T->data); InOrder(T->rchild, Visit); } } void PostOrder(BiTree T, void (*Visit)( DataType item)) /*后序 */ { if(T!= NULL) { PostOrder(T->lchild, Visit); PostOrder(T->rchild, Visit); Visit(T->data); }

数据结构二叉树实验报告

实验三二叉树的遍历 一、实验目的 １、熟悉二叉树的结点类型和二叉树的基本操作。 ２、掌握二叉树的前序、中序和后序遍历的算法。 3、加深对二叉树的理解，逐步培养解决实际问题的编程能力。 二、实验环境 运行Ｃ或VC++的微机。 三、实验内容 1、依次输入元素值，以链表方式建立二叉树，并输出结点的值。 2、分别以前序、中序和后序遍历二叉树的方式输出结点内容。 四、设计思路 1. 对于这道题，我的设计思路是先做好各个分部函数，然后在主函数中进行顺序排列，以此完成实验要求 2．二叉树采用动态数组 3.二叉树运用9个函数，主要有主函数、构建空二叉树函数、建立二叉树函数、访问节点函数、销毁二叉树函数、先序函数、中序函数、后序函数、范例函数，关键在于访问节点 五、程序代码 #include #include #include #define OK 1 #define ERROR 0 typedef struct TNode//结构体定义 {

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．掌握对二叉树每一种操作的具体实现。 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<<"二叉树初始化成功!"<>ch; if(ch=='#') BT=NULL; else { if(!(BT=(BitTree)malloc(sizeof(BitNode)))) exit(0);

树和二叉树实验报告

树和二叉树 一、实验目的 1.掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。 2.掌握用指针类型描述、访问和处理二叉树的运算。 二、实验要求 1.认真阅读和掌握本实验的程序。 2.上机运行本程序。 3.保存和打印出程序的运行结果，并结合程序进行分析。 4.按照二叉树的操作需要，重新改写主程序并运行，打印出文件清单和运 行结果。 三、实验内容 1.输入字符序列，建立二叉链表。 2.按先序、中序和后序遍历二叉树（递归算法）。 3.按某种形式输出整棵二叉树。 4.求二叉树的高度。 5.求二叉树的叶节点个数。 6.交换二叉树的左右子树。 7.借助队列实现二叉树的层次遍历。 8.在主函数中设计一个简单的菜单，分别调试上述算法。 为了实现对二叉树的有关操作，首先要在计算机中建立所需的二叉树。建立二叉树有各种不同的方法。一种方法是利用二叉树的性质5来建立二叉树，输入数据时要将节点的序号（按满二叉树编号）和数据同时给出：（序号，数据元素0）。另一种方法是主教材中介绍的方法，这是一个递归方法，与先序遍历有点相似。数据的组织是先序的顺序，但是另有特点，当某结点的某孩子为空时以字符“#”来充当，也要输入。若当前数据不为“#”，则申请一个结点存入当前数据。递归调用建立函数，建立当前结点的左右子树。 四、解题思路 1、先序遍历：○1访问根结点，○2先序遍历左子树，○3先序遍历右子树 2、中序遍历：○1中序遍历左子树，○2访问根结点，○3中序遍历右子树 3、后序遍历：○1后序遍历左子树，○2后序遍历右子树，○3访问根结点 4、层次遍历算法：采用一个队列q，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进后出，所以能够达到按层次遍历二叉树的目的。 五、程序清单 #include #include #define M 100

二叉树的基本操作实验

实验三二叉树的基本运算 一、实验目的 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 #include typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;

数据结构实验二叉树

实验六：二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。 二、问题描述 首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：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))))

二叉树实验报告及代码

重庆交通大学综合性设计性实验报告 姓名姚远学号 631106060113 班级：计信息一班 实验项目名称：二叉树 实验项目性质：设计性实验 实验所属课程：数据结构 实验室(中心)： 407机房 指导教师：鲁云平 实验完成时间： 2013 年 5 月 10 日

一、实验目的 1. 建立二叉树 2. 计算结点所在的层次 3.统计结点数量和叶结点数量 4.计算二叉树的高度 5.计算结点的度 6.找结点的双亲和子女 7.二叉树的遍历 8.二叉树的输出等等 二、实验内容及要求 1.二叉树的结点结构,二叉树的存储结构由学生自由选择和设定 2.实验完成后上交打印的实验报告,报告内容与前面所给定的实验模板相同 3.将实验报告电子版和源代码在网络教学平台提交 三、实验设备及软件 VISUAL C++软件 四、设计方案 ㈠题目（老师给定或学生自定） 二叉树的应用 ㈡设计的主要思路 在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在出度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，出度为2的结点数为n2，则n0 =n2 + 1。 ㈢主要功能

实现二叉树的各项操作。 五、主要代码 #include #include #include typedef struct BinTreeNode //二叉树结点类定义 { char data; //数据域 BinTreeNode *leftChild, *rightChild; //左子女、右子女链域 }*BTree; BinTreeNode *p,*q,*f; int NodeNum,Leaf; int NodeDu,nodeloc=1; void CreateBinTree(BTree &T); void preOrder(BTree T); void inOrder(BTree T); void postOrder(BTree T); int TreeNodes(BTree T); int LeafNodes(BTree T); int TreeNodedu(BTree T,char ch); void NodeLoc(BTree T,char c,int nodeloc); int Height(BTree T); BTree Parent(BTree T,char c); BTree NodeRC(BTree T,char c); BTree NodeLC(BTree T,char c); void CreateBinTree(BTree &T) {

二叉树实验报告

重庆交通大学综合性设计性实验报告 班级：软件开发专业 2010级一班 实验项目名称：二叉树 实验项目性质：设计性实验 实验所属课程：数据结构 实验室(中心)： 6教 指导教师：鲁云平 实验完成时间： 2012 年 4 月 29 日

一、实验目的 主要完成以下功能: 1. 建立二叉树 2. 计算结点所在的层次 3 .统计结点数量和叶结点数量 4. 计算二叉树的高度 5. 计算结点的度 6. 找结点的双亲和子女 7. 二叉树的遍历 8. 二叉树的输出等等 二、实验内容及要求 1.二叉树的结点结构,二叉树的存储结构由学生自由选择和设定 2.实验完成后上交打印的实验报告,报告内容与前面所给定的实验模板相同 3.将实验报告电子版和源代码在网络教学平台提交 三、实验设备及软件 Visual studio 2010

四、设计方案 ㈠题目（老师给定或学生自定） 二叉树的简单应用 ㈡设计的主要思路 通过递归原理实现大部分遍历二叉树功能 ㈢主要功能 1. 建立二叉树 2. 计算结点所在的层次 3 .统计结点数量和叶结点数量 4. 计算二叉树的高度 5. 计算结点的度 6. 找结点的双亲和子女 7. 二叉树的遍历 8. 二叉树的输出 五、主要代码 栈头文件：stack.h class Stack { public: Stack(int sz=100); ~Stack(){delete[]elements;} void Push(const T &x); bool Pop(T &x); bool getTop(T &x); bool IsEmpty()const{return(top==-1)?true:false;} bool IsFull()const{return(top==maxSize-1)?true:false;} private: T *elements; int top;

二叉树实验报告

题目： 编程实现二叉查找树的建立、中序遍历、元素查找等功能，要求解释实现过程及演示实际例子的运行结果。 算法描述： 首先创建二叉树结点类，其主要包括：二叉树结点数据域，指向左、右子树的指针，构造函数，设置当前结点左、右子树、数据域以及判断当前结点是否为叶子结点等。然后进行二叉树类定义，其私有部分为定义二叉树根结点指针，公有部分主要包括：构造函数、析构函数、判断二叉树是否为空树、先，中，后序遍历的递归与非递归、二叉树删除、层序遍历以及二叉树搜索等。接下来将对一些重要函数算法进行描述： 1、isLeaf函数：若该结点的左子树和右子树都为空，则为叶子结点。 2、isEmpty函数：根结点为空则为空树。 3、Parent函数：首先判断给定结点是否有双亲，根结点和空结点一定无双亲，初始化一个临时变量，用于跟进查找双亲结点，查找到后其保存的便是双亲结点。先递归在左子树中查找，如果找到，便结束递归且返回双亲结点指针；如果没有找到，再递归在右子树中查找。如果都没有找到，说明给定结点的双亲结点不在该二叉树中。 4、LeftSibling（RightSibling）函数：首先找到当前结点的双亲，然后判断双亲结点左右子树是否为空，其中必然有一个不为空，返回另一个子树指针即可。 5、DeleteBinaryTree函数：首先判断是否为空树，若为空，则返回，然后递归删除左子树，递归删除右子树，最后删除根结点。 6、PreOrder函数：首先判断是否为空树，若为空，则返回，然后访问根结点，递归遍历左子树，递归遍历右子树，结束。 7、PreOrderWithoutRecusion函数：使用栈来模拟递归过程，首先申请栈，用于保存结点指针序列，申请指针pointer保存当前根指针，然后判断栈是否为空，若栈为空且pointer为空，跳出函数，否则若pointer不为空，访问pointer所指结点，pointer入栈，pointer指向其左子树；若pointer为空，弹出栈顶元素赋给pointer，pointer指向其右子树，结束。 8、CreateTree函数：采用先序遍历序列构造二叉树，设‘0’为空结点，输入非‘0’数，生成新结点，递归创建左子树和右子树。 9、Search函数：采用先序遍历查找给定元素是否在二叉树中，首先判断树是否是空树，若是空树，则返回空指针。然后初始化临时指针temp，查找成功后temp即为所给元素所在

实验3 树和二叉树

实验3 树和二叉树 实验性质：验证性 实验学时：4学时 一、实验目的 1.掌握二叉树的特点、在计算机中的存储表示方法及其基本操作的实现； 2.能够利用二叉树求解一些常见问题。 二、实验预备知识 1.阅读并掌握二叉树二叉链表存储方法的类型定义及其创建、遍历等基本操作。 2.阅读并掌握赫夫曼树的创建、赫夫曼编码的求得等基本操作。 三、实验内容 1.理解并用二叉链表的操作运行下列程序： #include using namespace std; #include "Status.h" typedef char ElemType; #include "BiTree.h" void main() { BiTree T; CreateBiTree(T); cout<<"二叉树的深度为："<

数据结构实验报告之树与二叉树

学生实验报告 学院：软通学院 课程名称：数据结构与算法 专业班级：软件142 班 姓名：邹洁蒙 学号： 0143990

学生实验报告 （二） 一、实验综述 1、实验目的及要求 目的：1）掌握树与二叉树的基本概念； 2）掌握二叉树的顺序存储，二叉链表的先序遍历中序遍历和后序遍历算法； 3）掌握树的双亲表示法。 要求：1）编程：二叉树的顺序存储实现； 2）编程：二叉链表的先序遍历中序遍历和后序遍历实现； 3）编程：树的双亲表示法实现。 2、实验仪器、设备或软件 设备：PC 软件：VC6 二、实验过程(编程，调试，运行；请写上源码，要求要有注释) 1.编程：二叉树的顺序存储实现 代码： BiTree::BiTree()//建立存储空间 { data = new int[MAXSIZE]; count = 0; } void BiTree::AddNode(int e)//加结点 { int temp = 0; data[count] = e; count++;//从编号0开始保存 }

运行截图： 2.编程：二叉链表的先序遍历中序遍历和后序遍历实现代码： void InOrderTraverse(BiTree* Head)//中序遍历 { if (Head) { InOrderTraverse(Head->LeftChild); cout << Head->data<<" "; InOrderTraverse(Head->RightChild); } } void PreOrderTraverse(BiTree* Head)//先序遍历 { if (Head) { cout << Head->data << " "; PreOrderTraverse(Head->LeftChild); PreOrderTraverse(Head->RightChild); } } void PostOrderTraverse(BiTree* Head)//后序遍历 { if (Head) { PostOrderTraverse(Head->LeftChild); PostOrderTraverse(Head->RightChild); cout << Head->data << " "; } } 运行截图：

实验三树和二叉树

《数据结构》实验报告三 学院：班级： 学号：姓名： 日期：2010.04.29 程序名：L61.CPP,L62.CPP 一、上机实验的问题和要求： 要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。具体实现要求： 1.基于先序遍历的构造算法：输入是二叉树的先序序列，但必须在其中加入虚结点以示空 指针的位置。假设虚结点输入时用空格字符表示。 2.用广义表表示所建二叉树。 3.用凹入表表示所建二叉树。 4.分别利用前序遍历、中序遍历、后序遍历所建二叉树。 5.求二叉树结点总数，观察输出结果。 6.求二叉树叶子总数，观察输出结果。 7.交换各结点的左右子树，用广义表表示法显示新的二叉树。 8.（★）二叉树采用链接存储结构，其根结点指针为T，设计一个算法对这棵二叉树的每 个结点赋值：（注意要修改DataType类型） ?叶结点的值为3 ?只有左孩子或右孩子的结点则其值分别等于左孩子或右孩子的值 ?左、右孩子均有的结点，则其值等于左、右孩子结点的值之和 ?用广义表表示法显示所建二叉树 阅读理解建立Huffman树的算法，对该算法进行运行及调试。具体实现要求： 1.调试并运行Huffman算法，验算《回家作业六》的第3题。 2.（★）求Huffman树的带权路径长度WPL。 二、程序设计的基本思想，原理和算法描述： （包括程序的结构，数据结构，输入/输出设计，符号名说明等） 三、源程序及注释： #include #include

//二叉树的链式存储表示 typedef char DataType; //应由用户定义DataType的实际类型typedef struct node { DataType data; struct node *lchild, *rchild; //左右孩子指针 } BinTNode; //结点类型 typedef BinTNode *BinTree; void main() { void ListBinTree(BinTree T); //用广义表表示二叉树 void DisplayBinTree(BinTree T); //用凹入表表示二叉树 void CreateBinTree(BinTree *T); //构造二叉链表 void Preorder(BinTree T); //前序遍历二叉树 void Inorder(BinTree T); //中序遍历二叉树 void Postorder(BinTree T); //后序遍历二叉树 int nodes(BinTree T); //计算总结点数 int leafs(BinTree T); //计算总叶子数 BinTree swap(BinTree T); //交换左右子树 BinTree T; printf("请输入先序序列（虚结点用空格表示）：\n"); CreateBinTree(&T); ListBinTree(T); printf("\n"); DisplayBinTree(T); printf("前序遍历：\n"); Preorder(T); printf("\n"); printf("中序遍历：\n"); Inorder(T); printf("\n"); printf("后序遍历：\n"); Postorder(T); printf("\n"); printf("二叉树的总结点数为%d\n",nodes(T)); printf("二叉树的总叶子结点数为%d\n",leafs(T)); T=swap(T); ListBinTree(T); printf("\n"); } /*构造二叉链表*/ void CreateBinTree(BinTree *T) {

数据结构实验报告—二叉树

算法与数据结构》课程实验报告

一、实验目的 1、实现二叉树的存储结构 2、熟悉二叉树基本术语的含义 3、掌握二叉树相关操作的具体实现方法 二、实验内容及要求 1. 建立二叉树 2. 计算结点所在的层次 3. 统计结点数量和叶结点数量 4. 计算二叉树的高度 5. 计算结点的度 6. 找结点的双亲和子女 7. 二叉树前序、中序、后序遍历的递归实现和非递归实现及层次遍历 8. 二叉树的复制 9. 二叉树的输出等 三、系统分析 （1）数据方面：该二叉树数据元素采用字符char 型，并且约定“ #”作为二叉树输入结束标识符。并在此基础上进行二叉树相关操作。 （2）功能方面：能够实现二叉树的一些基本操作，主要包括： 1. 采用广义表建立二叉树。 2. 计算二叉树高度、统计结点数量、叶节点数量、计算每个结点的度、结点所在层次。 3. 判断结点是否存在二叉树中。 4. 寻找结点父结点、子女结点。 5. 递归、非递归两种方式输出二叉树前序、中序、后序遍历。 6. 进行二叉树的复制。 四、系统设计 （1）设计的主要思路 二叉树是的结点是一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树、互不相交的二叉树组成。根据实验要求，以及课上老师对于二叉树存储结构、基本应用的讲解，同时课后研究书中涉及二叉树代码完成二叉树模板类，并将所需实现各个功能代码编写完成，在建立菜单对功能进行调试。 （2）数据结构的设计 二叉树的存储结构有数组方式和链表方式。但用数组来存储二叉树有可能会消耗大量的存储空间，故在此选用链表存储，提高存储空间的利用率。根据二叉树的定义，二叉

实验10 二叉树的基本操作

浙江大学城市学院实验报告 课程名称数据结构基础 实验项目名称实验十二叉树的基本操作 学生姓名专业班级学号 实验成绩指导老师（签名）日期2014-12-18 一.实验目的和要求 1、掌握二叉树的链式存储结构。 2、掌握在二叉链表上的二叉树操作的实现原理与方法。 3、进一步掌握递归算法的设计方法。 二.实验内容 1、按照下面二叉树二叉链表的存储表示，编写头文件binary_tree.h，实现二叉链表的定义与基本操作实现函数；编写主函数文件test4_1.cpp，验证头文件中各个操作。 二叉树二叉链表存储表示如下： struct BTreeNode { ElemType data; // 结点值域 BTreeNode *lchild , *rchild ; // 定义左右孩子指针 } ; 基本操作如下： ①void InitBTree( BTreeNode *&BT ); //初始化二叉树BT ②void CreateBTree( BTreeNode *&BT, char *a ); //根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构 ③int EmptyBTree( BTreeNode *BT); //检查二叉树BT是否为空，空返回1，否则返回0 ④int DepthBTree( BTreeNode *BT); //求二叉树BT的深度并返回该值 ⑤int FindBTree( BTreeNode *BT, ElemType x); //查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0 ⑥void PreOrder( BTreeNode *BT); //先序遍历二叉树BT ⑦void InOrder( BTreeNode *BT); //中序遍历二叉树BT ⑧void PostOrder( BTreeNode *BT); //后序遍历二叉树BT

数据结构二叉树的实验报告

数据结构 实 验 报 告

1. 实验目的和内容： 掌握二叉树基本操作的实现方法2. 程序分析 2.1存储结构 链式存储 2．程序流程

2.3关键算法分析 算法一：Create(BiNode* &R,T data[],int i,int n) 【1】算法功能：创建二叉树 【2】算法基本思想：利用顺序存储结构为输入，采用先建立根结点，再建立左右孩子的方法来递归建立二叉链表的二叉树 【3】算法空间时间复杂度分析：O(n) 【4】代码逻辑： 如果位置小于数组的长度则 {创建根结点 将数组的值赋给刚才创建的结点的数据域 创建左子树，如果当前结点位置为i,则左孩子位置为2i 创建右子树，如果当前结点位置为i,则右孩子位置为2i+1 } 否则R为空 算法二：CopyTree(BiNode*sR,BiNode* &dR) ） 【1】算法功能：复制构造函数 【2】算法基本思想：按照先创建根结点，再递归创建左右子树的方法来实现。 【3】算法空间时间复杂度分析：O（n) 【4】代码逻辑: 如果源二叉树根结点不为空 则{ 创建根结点 调用函数自身，创建左子树 调用函数自身，创建右子树 } 将该函数放在复制构造函数中调用，就可以实现复制构造函数

算法三：PreOrder(BiNode*R) 【1】算法功能：二叉树的前序遍历 【2】算法基本思想：这个代码用的是优化算法，提前让当前结点出栈。【3】算法空间时间复杂度分析：O（n） 【4】代码逻辑（伪代码） 如果当前结点为非空，则 { 访问当前结点 当前结点入栈 将当前结点的左孩子作为当前结点} 如果为空 { 则栈顶结点出栈 则将该结点的右孩子作为当前结点 } 反复执行这两个过程，直到结点为空并且栈空 算法四：InOrder(BiNode*R) 【1】算法功能：二叉树的中序遍历 【2】算法基本思想：递归 【3】算法空间时间复杂度分析：未知 【4】代码逻辑： 如果R为非空： 则调用函数自身遍历左孩子 访问该结点 再调用自身访问该结点的右孩子 算法五：LevelOrder(BiNode*R) 【1】算法功能：二叉树的层序遍历 【2】算法基本思想： 【3】算法空间时间复杂度分析：O（n） 【4】代码逻辑（伪代码）： 若根结点非空，入队

实验五-二叉树基本操作的编程实现实验分析报告

实验五-二叉树基本操作的编程实现实验报告

————————————————————————————————作者：————————————————————————————————日期：

HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY 数据结构 实验报告 这里一定填 写清楚自己 实验项目实验五实验类别基础篇 学生姓名朱忠栋学生学号20120231515 完成日期2014-12-16 指导教师付勇智 实验成绩评阅日期 评阅教师

实验五二叉树基本操作的编程实现 【实验目的】 内容：二叉树基本操作的编程实现 要求： 二叉树基本操作的编程实现（2学时，验证型），掌握二叉树的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找等操作，存储结构主要采用顺序或链接结构。也鼓励学生利用基本操作进行一些应用的程序设计。 【实验性质】 验证性实验（学时数：2H） 【实验内容】 以下的选题都可以作为本次实验的推荐题目 1.建立二叉树，并以前序遍历的方式将结点内容输出。 2.将一个表示二叉树的数组结构转换成链表结构。 3.将表达式二叉树方式存入数组，以递归方式建立表达式之二叉树状结构，再分别输出前序、中序 及后序遍历结果，并计算出表达式之结果。 【注意事项】 1.开发语言：使用C。 2.可以自己增加其他功能。 【实验分析、说明过程】

页面不够，可续页。 根据自己选择的层次不同的实验内容，完善程序代码，调试通过后，分析说明该问题处理的详细算法过程。不需要写出详细的代码，只表达清楚详细的处理算法即可。可以采用流程图、形式语言或者其他数学表达方式来说明。 这次实验考查的主要是：递归建立二叉树，递归输出先序，中序和后序遍历的结果；非递归建立二叉树，再以非递归方式分别输出先序，中序和后序遍历的结果。 而对于基础篇考查的主要是：递归建立二叉树，递归输出先序，中序和后序遍历的结果，是以填空的方式进行考查的。 对于第一空：递归实现的先序遍历，其实现方法是： printf("%d",p->data); if(p->lchild!=NULL) preorder(p->lchild); if(p->rchild!=NULL) preorder(p->rchild); 对于第二空：递归实现的中序遍历，其实现方法是： if(p->lchild!=NULL) inorder(p->lchild); printf("%d",p->data); if(p->rchild!=NULL) inorder(p->rchild); 对于第三空：递归实现的后序遍历，其实现方法是： if(p->lchild!=NULL) postorder(p->lchild); if(p->rchild!=NULL) postorder(p->rchild); printf("%d",p->data); 【思考问题】 页面不够，可续页。 1.二叉树是树吗？它的定义为什么是递归的？ 答：最多有两棵子树的有序树，称为二叉树。二叉树是一种特殊的树。具有n个结点的完全二叉树的深度为log2n +1 ！！！二叉树的计算方法：若一棵二叉树为空,则其深度为0,否则其深度等于左子树和右子树的最大深度加1 2.三种根序遍历主要思路是什么？ 答：大体思路差不多，但节点访问位置不一样，先序的话，是先访问，然后节点压栈，移到左子树，至节点空退栈，移到右子树。而中序的话，是先节点压栈，移到左子树，至节点空退栈，访问节点，然后移到右子树。另外，所谓前序、中序、后序遍历，全称是前根序遍历，中根序遍历，后根序遍历，不管哪种遍历，访问左子树一定在访问右子树之前，不同的就是根的访问时机。 所以三种递归/或非递归，程序思路都是一样的。 3.如果不用遍历算法一般启用什么数据结构实现后序遍历？ 答：用栈实现后序遍历。 4.举出二叉树的应用范例？ 答：一个集合的幂集、排列问题、组合问题

数据结构实验报告-树与二叉树

福建农林大学计算机与信息学院实验报告 树与二叉树 一、实验目的和要求 1)进一步掌握指针变量、动态变量的含义。 2)掌握二叉树的结构特性及各种存储结构的特点及适用范围。 3)掌握用指针类型描述、访问和处理二叉树的运算。 4)熟悉各种存储结构的特征及如何应用树结构解决具体问题。 二、实验内容和原理 实验内容： 编写程序实现交换二叉树中所有结点的左右子树的算法。 实验原理： 【问题描述】建立一棵二叉树，按层次遍历该二叉树，并实现将二叉树中所有结点的左右子树交换，显示其结果。 【基本要求】从键盘接受输入点（按层次遍历顺序），以“#”号结束，以二叉链表作为存储结构，将其二叉树中所有结点的左右子树交换，并将结果输出。 【实现】交换二叉树中所有结点的左右子树的具体步骤如下: ①将根结点进指针栈seqstack; ②当指针栈不空时，从栈顶取结点，如果此结点的左右孩子不为 空，则把其左右孩子交换，然后再分别将其左右孩子进栈； ③反复执行步骤②，直至指针栈为空时止。

三、实验环境 Windows XP系统 visual c++6.0 四、算法描述及实验步骤 #include "stdio.h" #include"stdlib.h" #define MAXSIZE 100 typedef char elemtype; typedef struct btnode {elemtype data; struct btnode *lchild, *rchild; }bitnode ,*bitree; typedef struct nodd {bitree addr; int parent; }sequre; bitree ins_node (bitree s,bitree t); void print_tree(bitree t); bitree creat_ordbt(); sequre seq[MAXSIZE]; void swap(bitree tree); int n=0; void main() {bitree tree; tree=creat_ordbt(); swap(tree); printf("输出交换后的二叉树\n"); print_tree(tree); } bitree creat_ordbt() {bitree t,s; elemtype x; t=NULL; printf("请按层次输入结点1的值(以#号结束，0号为空的结点)："); scanf("%c",&x); getchar(); while(x!='#') {n++;