实验四 二叉树基本操作的实现

实验四二叉树基本操作的实现

专业：计算机科学与技术班级：10计本1班学号：姓名：

实验地点：B102 实验时间：2011-11-23 指导教师：王润鸿

实验目的

1 理解二叉树概念及其存储结构；

2掌握采用二叉链储存结构的二叉树基本操作；

3学会设计实验数据验证程序。

实验环境

计算机，window xp操作系统，VC++6.0

实验内容

1. 存储结构定义：

typedef struct BiTNode { //结点定义

TElemType data;

struct BiTNode * lchild, * rchild;

} BiTNode,*BiTree;

2. 实现的基本操作：

InitBiTree(&T);

操作结果：构造空二叉树T。

CreateBiTree(&T, definition);

初始条件：definition 给出二叉树T 的定义。

操作结果：按definition 构造二叉树T。

DestroyBiTree(&T);

初始条件：二叉树T 存在。

操作结果：销毁二叉树T。

BiTreeEmpty(T);

初始条件：二叉树T 存在。

操作结果：若T为空二叉树，则返回TRUE，否则返回FALSE。

BiTreeDepth(T);

初始条件：二叉树T 存在。

操作结果：返回T 的深度。

Root(T);

初始条件：二叉树T 存在。

操作结果：返回T 的根。

Value(T, e);

初始条件：二叉树T 存在，e 是T 中某个结点。

操作结果：返回e 的值。

Parent(T, e);

初始条件：二叉树T 存在，e 是T 中某个结点。

操作结果：若e是T的非根结点，则返回它的双亲，否则返回"空"。

LeftChild(T, e);

初始条件：二叉树T 存在，e 是T 中某个结点。

操作结果：返回e 的左孩子。若e 无左孩子，则返回"空"。

RightChild(T, e);

初始条件：二叉树T 存在，e 是T 中某个结点。

操作结果：返回e 的右孩子。若e 无右孩子，则返回"空"。

LeftSibling(T, e);

初始条件：二叉树T 存在，e 是T 中某个结点。

操作结果：返回e 的左兄弟。若e 是其双亲的左孩子或无左兄弟，则返回"空"。

RightSibling(T, e);

初始条件：二叉树T 存在，e 是T 的结点。

操作结果：返回e 的右兄弟。若e 是其双亲的右孩子或无右兄弟，则返回"空"。

PreOrderTraverse(T, visit());

初始条件：二叉树T 存在，visit 是对结点操作的应用函数。

操作结果：先序遍历T，对每个结点调用函数visit 一次且仅一次。一旦visit() 失败，则操作失败。

InOrderTraverse(T, vsit());

初始条件：二叉树T 存在，visit 是对结点操作的应用函数。

操作结果：中序遍历T，对每个结点调用函数Visit 一次且仅一次。一旦visit() 失败，则操作失败。

PostOrderTraverse(T, visit());

初始条件：二叉树T存在，visit 是对结点操作的应用函数。

操作结果：后序遍历T，对每个结点调用函数visit 一次且仅一次。一旦visit() 失败，则操作失败。

LevelOrderTraverse(T, visit());

初始条件：二叉树T 存在，visit 是对结点操作的应用函数。

操作结果：层序遍历T，对每个结点调用函数visit 一次且仅一次。一旦visit() 失败，则操作失败。

ClearBiTree(&T);

初始条件：二叉树T 存在。

操作结果：将二叉树T 清为空树。

Assign(&T, &e, value);

初始条件：二叉树T 存在，e 是T 中某个结点。

操作结果：结点e 赋值为value。

InsertChild(&T, p, LR, c);

初始条件：二叉树T 存在，p 指向T 中某个结点，LR 为0 或1，非空二叉树c 与T 不相交且右子树为空。

操作结果：根据LR 为0 或1，插入c 为T 中p 所指结点的左或右子树。p 所指结点原有左或右子树成为c 的右子树。

DeleteChild(&T, p, LR);

初始条件：二叉树T 存在，p 指向T 中某个结点，LR 为0 或1。

操作结果：根据LR 为0 或1，删除T 中p 所指结点的左或右子树。

3. 测试数据及实验结果

#include"iostream"

using namespace std;

#define NULL 0

#define FALSE 0

#define TRUE 1

typedef int TElemType;

typedef int Status;

typedef struct BiTNode { //结点定义

TElemType data;

struct BiTNode * lchild, * rchild;

} BiTNode,*BiTree;

void InitBiTree(BiTNode &T){

memset(&T,0,sizeof(BiTNode));

}

void Assign(BiTNode &e,int value){

e.data=value;

}

void InsertChild(BiTNode &e,int LR){

if(LR==0)

e.lchild=(BiTree)malloc(sizeof(BiTNode));

else

e.rchild=(BiTree)malloc(sizeof(BiTNode));

}

void CreateBiTree(BiTNode &T,int a[]){

static i=0;

Assign(T,a[i]);

i++;

if(a[i]==0){

T.lchild=NULL;

T.rchild=NULL;

i++;

}

else{

InsertChild(T,0);

InsertChild(T,1);

CreateBiTree(*T.lchild,a);

CreateBiTree(*T.rchild,a);

}

}

int Value(BiTNode e){

return e.data;

}

void visit(BiTNode b){

cout<

}

void PreOrderTraverse(BiTNode T, void visit(BiTNode)){

visit(T);

if(T.lchild!=NULL)

PreOrderTraverse(*T.lchild,visit);

if(T.rchild!=NULL)

PreOrderTraverse(*T.rchild,visit);

}

void InOrderTraverse(BiTNode T, void visit(BiTNode)){

if(T.lchild!=NULL)

InOrderTraverse(*T.lchild,visit);

visit(T);

if(T.rchild!=NULL)

InOrderTraverse(*T.rchild,visit);

}

void PostOrderTraverse(BiTNode T, void visit(BiTNode)){

if(T.lchild!=NULL)

PostOrderTraverse(*T.lchild,visit);

if(T.rchild!=NULL)

PostOrderTraverse(*T.rchild,visit);

visit(T);

}

void LayerOrderTraverse(BiTNode T,int (*t)[10],int n[],int layer){ *(*(t+layer-1)+n[layer-1])=Value(T);

n[layer-1]++;

layer++;

if(T.lchild)

LayerOrderTraverse(*T.lchild,t,n,layer);

if(T.rchild)

LayerOrderTraverse(*T.rchild,t,n,layer);

}

Status BiTreeEmpty(BiTNode T){

if(T.data ==0&&T.lchild==NULL&&T.rchild==NULL) return TRUE;

return FALSE;

}

int Parent(BiTNode T,BiTNode now,int parent,int e){

int result;

if(e==now.data)

return parent;

if(now.lchild!=NULL){

result=Parent(T,*now.lchild,now.data,e);

if(result!=NULL)

return result;

}

if(now.rchild!=NULL){

result=Parent(T,*now.rchild,now.data,e);

if(result!=NULL)

return result;

}

return NULL;

}

void DeleteChild(BiTNode &e){

if(e.lchild)

DeleteChild(*e.lchild);

if(e.rchild)

DeleteChild(*e.rchild);

free(&e);

}

void ClearBiTree(BiTNode &T){

DeleteChild(*T.lchild);

DeleteChild(*T.rchild);

T.lchild=NULL;

T.rchild=NULL;

T.data=0;

}

int depth(int a[]){

int dep=0;

for(int i=0;i<5;i++){

if(a[i]==0)

break;

dep++;

}

return dep;

}

int main(){

int e;

int parent;

BiTNode bn1;

int num[5];

int table[5][10];

memset(num,0,5*sizeof(int));

memset(table,0,50*sizeof(int));

InitBiTree(bn1);

Int a[23]={1,2,3,4,0,5,0,6,7,0,8,0,9,10,11,0,12,0,13,14,0,15,0};

CreateBiTree(bn1,a);

cout<<"PreOrderTraverse:";

PreOrderTraverse(bn1, visit);

cout<

cout<<"InOrderTraverse:";

InOrderTraverse(bn1, visit);

cout<

cout<<"PostOrderTraverse:";

PostOrderTraverse(bn1,visit);

cout<

e=15;

parent=NULL;

cout<<"Parentof 15:"<

static c=8;

int layer=1;

LayerOrderTraverse(bn1,&table[0],num,layer);

cout<<"LayerOrderTraverse:"<

for(int i=0;num[i];i++){

for(int k=0;k

cout<<" ";

for(int j=0;table[i][j];j++){

cout<

for(int l=0;l

cout<<" ";

}

cout<

c/=2;

}

cout<<"depth:"<

ClearBiTree(bn1);

if(BiTreeEmpty(bn1))

cout<<"ClearBiTree:"<<"Success!"<

}

相关练习

1举例说明什么样的二叉树采用顺序存储，什么样的二叉树采用二叉链存储。

答：完全二叉树采用顺序存储，一般的二叉树都可以采用二叉链存储。

2总结编程调试过程中遇到的问题，你采取的解决方案。若未能测试通过所有操作，请分析原因。

实验三 二叉树的基本操作实现及其应用

二叉树的基本操作实现及其应用 一、实验目的 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);

二叉树的基本 操作

//二叉树的基本操作 #include typedef struct node //定义结点 { char data; struct node *lchild, *rchild; } BinTNode; typedef BinTNode *BinTree; //定义二叉树 void CreateBinTree(BinTree &T); //先序创建二叉树 void PreOrder(BinTree T); //先序遍历二叉树 void InOrder(BinTree T); //中序遍历二叉树 void PostOrder(BinTree T); //后序遍历二叉树 int onechild(BinTree T); //求度为1的结点的个数int leafs(BinTree T); //求叶子结点的个数 int twochild(BinTree T); //度为2的结点的个数void translevel(BinTree b); //层序遍历二叉树 void main() { int n; BinTree T; char ch1,ch2; cout<<"欢迎进入二叉树测试程序的基本操作"<

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

实验三二叉树的操作及应用 实验课程名：数据结构与算法 专业班级：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); }

二叉树的基本操作实验

实验三二叉树的基本运算 一、实验目的 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;

数据结构——二叉树基本操作源代码

数据结构二叉树基本操作 (1). // 对二叉树的基本操作的类模板封装 //------------------------------------------------------------------------------------------------------------------------ #include using namespace std; //------------------------------------------------------------------------------------------------------------------------ //定义二叉树的结点类型BTNode,其中包含数据域、左孩子，右孩子结点。template struct BTNode { T data ; //数据域 BTNode* lchild; //指向左子树的指针 BTNode* rchild; //指向右子树的指针 }; //------------------------------------------------------------------------------------------------------------------------ //CBinary的类模板 template class BinaryTree { BTNode* BT; public: BinaryTree(){BT=NULL;} // 构造函数,将根结点置空 ~BinaryTree(){clear(BT);} // 调用Clear()函数将二叉树销毁 void ClearBiTree(){clear(BT);BT=NULL;}; // 销毁一棵二叉树 void CreateBiTree(T end); // 创建一棵二叉树，end为空指针域标志 bool IsEmpty(); // 判断二叉树是否为空 int BiTreeDepth(); // 计算二叉树的深度 bool RootValue(T &e); // 若二叉树不为空用e返回根结点的值，函数返回true，否则函数返回false BTNode*GetRoot(); // 二叉树不为空获取根结点指针，否则返回NULL bool Assign(T e,T value); // 找到二叉树中值为e的结点，并将其值修改为value。

数据结构实验二叉树

实验六：二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。 二、问题描述 首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：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()函数。分解出原始中缀表达式中的操作数、操作符以及括号，保存在队列中，以本实验中的数据为例，分解完成后队列中的保存顺序如下图所示：

数据结构实验三——二叉树基本操作及运算实验报告

《数据结构与数据库》 实验报告 实验题目 二叉树的基本操作及运算 一、需要分析 问题描述： 实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目，以及二叉树常用运算。 问题分析： 二叉树树型结构是一类重要的非线性数据结构，对它的熟练掌握是学习数据结构的基本要求。由于二叉树的定义本身就是一种递归定义，所以二叉树的一些基本操作也可采用递归调用的方法。处理本问题，我觉得应该：

1、建立二叉树； 2、通过递归方法来遍历（先序、中序和后序）二叉树； 3、通过队列应用来实现对二叉树的层次遍历； 4、借用递归方法对二叉树进行一些基本操作，如：求叶子数、树的深度宽度等； 5、运用广义表对二叉树进行广义表形式的打印。 算法规定： 输入形式：为了方便操作，规定二叉树的元素类型都为字符型，允许各种字符类型的输入，没有元素的结点以空格输入表示，并且本实验是以先序顺序输入的。 输出形式：通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印，再以广义表形式进行打印。对二叉树的一些运算结果以整型输出。 程序功能：实现对二叉树的先序、中序和后序遍历，层次遍历。计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目。对二叉树的某个元素进行查找，对二叉树的某个结点进行删除。 测试数据：输入一：ABC□□DE□G□□F□□□（以□表示空格）,查找5,删除E 预测结果：先序遍历ABCDEGF 中序遍历CBEGDFA 后序遍历CGEFDBA 层次遍历ABCDEFG 广义表打印A（B（C,D（E（,G）,F））） 叶子数3 深度5 宽度2 非空子孙数6 度为2的数目2 度为1的数目2 查找5，成功，查找的元素为E 删除E后，以广义表形式打印A（B（C,D（,F））） 输入二：ABD□□EH□□□CF□G□□□（以□表示空格）,查找10,删除B 预测结果：先序遍历ABDEHCFG 中序遍历DBHEAGFC 后序遍历DHEBGFCA 层次遍历ABCDEFHG 广义表打印A（B(D,E(H)),C(F(,G))） 叶子数3 深度4 宽度3 非空子孙数7 度为2的数目2 度为1的数目3 查找10，失败。

实验三 二叉树操作的实现 代码及运行结果图

二叉树操作的实现 #include #include #include typedef struct BiTNode { int data; BiTNode *lchild,*rchild; }BiTNode,*BiTree; int Nil=0; // 设整型以0为空 void visit(int e) { printf("%d ",e); } void CreateBiTree(BiTree &T) { int number; scanf("%d",&number); if(number==Nil) T=NULL; else // 结点的值不为空 { T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点 if(!T) exit(-2); T->data=number; // 将值赋给T所指结点 CreateBiTree(T->lchild); //C 递归构造左子树 CreateBiTree(T->rchild); // 递归构造右子树 } } void DestroyBiTree(BiTree &T) { if(T) // 非空树 { DestroyBiTree(T->lchild); DestroyBiTree(T->rchild); free(T); } } void PreOrderTraverse(BiTree T,void (*Visit)(int)){

{ Visit(T->data); PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树 PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树} } void InOrderTraverse(BiTree T,void(*Visit)(int)) { if(T) { InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树 Visit(T->data); // 再访问根结点 InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树} } void PostOrderTraverse(BiTree T,void(*Visit)(int)) { if(T) // T不空 { PostOrderTraverse(T->lchild,Visit); PostOrderTraverse(T->rchild,Visit); Visit(T->data); // 最后访问根结点 } } int LeafNum( BiTree T){ if(!T) return 0; else if(!T->lchild&&!T->rchild) return 1; else // printf("nihao"); return LeafNum(T->lchild)+LeafNum(T->rchild); }

实验10 二叉树的基本操作

浙江大学城市学院实验报告 课程名称数据结构 实验项目名称实验十二叉树的基本操作 学生姓名专业班级学号 实验成绩指导老师（签名）日期 一.实验目的和要求 1、掌握二叉树的链式存储结构。 2、掌握在二叉链表上的二叉树操作的实现原理与方法。 3、进一步掌握递归算法的设计方法。 二.实验内容 1、按照下面二叉树二叉链表的存储表示，编写头文件binary_tree.h，实现二叉链表的定义与基本操作实现函数；编写主函数文件test10.cpp，验证头文件中各个操作。 二叉树二叉链表存储表示如下： typedef struct BiTNode { TElemType data ; struct BiTNode *lchild , *rchild ; }BiTNode,*BiTree ; 基本操作如下： ①void InitBiTree(BiTree &T ) //初始化二叉树T ②void CreateBiTree(BiTree &T) //按先序遍历序列建立二叉链表T ③bool BiTreeEmpty (BiTree T); //检查二叉树T是否为空，空返回1，否则返回0 ④int BiTreeDepth(BiTree T); //求二叉树T的深度并返回该值 ⑤void PreOrderTraverse (BiTree T); //先序遍历二叉树T ⑥void InOrderTraverse (BiTree T); //中序遍历二叉树T ⑦void PostOrderTraverse (BiTree T); //后序遍历二叉树T ⑧void DestroyBiTree(BiTree &T) //销毁二叉树T

二叉树基本操作经典实例

本程序由SOGOF完成 该完整程序主要是递归函数的使用及模板的使用，完成了对二叉树基本的链表操作，主要有二叉树的建立，前序、中序、后序遍历，求树的高度，每层结点数（包含树的最大宽度），左右结点对换，二叉树的内存释放，求解树的叶子数。 #include using namespace std; #define FLAG'#' typedef char Record; template struct Binary_Node { Entry data; Binary_Node*left; Binary_Node*right; Binary_Node(); Binary_Node(const Entry& x); }; template Binary_Node::Binary_Node() { left=NULL; right=NULL; } template Binary_Node::Binary_Node(const Entry &x) { data=x; left=NULL; right=NULL; } template class Binary_tree { public: bool empty()const; Binary_tree(); Binary_tree(Binary_tree&org); void create_tree(Binary_Node*&tree);//建立二叉树 void recursive_copy(Binary_Node*&tree,Binary_Node*&cur); void pre_traverse(Binary_Node *tree);//前序 void mid_traverse(Binary_Node *tree);//中序 void post_traverse(Binary_Node *tree);//后序遍历

二叉树的基本操作及实现.cpp

二叉树的基本操作及实现 二叉树的基本操作及实现的代码如下： #include #define MAXNODE 100 typedef char DataType; typedef struct BiTNode{ DataType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; void Visit(DataType bt){ //输出二叉树结点值 cout<lchild=NULL;bt->rchild=NULL; return bt; } BiTree Create_BiTree(DataType x,BiTree lbt,BiTree rbt){ //建立二叉树：以结点值为x的结点为头结点，并以lbt和rbt为左右子树BiTree p; p=new BiTNode; if(!p){ cout<<"无法完成二叉树的建立!"<data=x; p->lchild=lbt;p->rchild=rbt; return p; } BiTree InsertL(BiTree bt,DataType x,BiTree parent){ //在某结点之后插入左结点BiTree p; if(parent==NULL){ cout<<"要插入结点的父节点不存在！"<

二叉树的基本 操作

创作编号： GB8878185555334563BT9125XW 创作者：凤呜大王* //二叉树的基本操作 #include typedef struct node //定义结点 { char data; struct node *lchild, *rchild; } BinTNode; typedef BinTNode *BinTree; //定义二叉树 void CreateBinTree(BinTree &T); //先序创建二叉树 void PreOrder(BinTree T); //先序遍历二叉树 void InOrder(BinTree T); //中序遍历二叉树 void PostOrder(BinTree T); //后序遍历二叉树 int onechild(BinTree T); //求度为1的结点的个数int leafs(BinTree T); //求叶子结点的个数 int twochild(BinTree T); //度为2的结点的个数void translevel(BinTree b); //层序遍历二叉树 void main() { int n; BinTree T; char ch1,ch2; cout<<"欢迎进入二叉树测试程序的基本操作"<

cout<<"--------------请选择------------"<>ch2; switch(ch2) { case '1': cout<<"请输入按先序建立二叉树的结点序列：\n"; CreateBinTree(T); cout<

C++二叉树的创建与遍历实验报告

二叉树的创建与遍历 一、实验目的 1．学会实现二叉树结点结构和对二叉树的基本操作。 2．掌握对二叉树每种操作的具体实现，学会利用递归和非递归方法编写对二叉树这种递归数据结构进行处理的算法。 二、实验要求 1．认真阅读和掌握和本实验相关的教材内容。 2．编写完整程序完成下面的实验内容并上机运行。 3．整理并上交实验报告。 三、实验内容 1．编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归和非递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历。 四、实验步骤 源程序代码1 #include #include using namespace std; template struct BinTreeNode //二叉树结点类定义 { T data; //数据域 BinTreeNode *leftChild,*rightChild; //左子女、右子女域 BinTreeNode(T x=T(),BinTreeNode* l =NULL,BinTreeNode* r = NULL ) :data(x),leftChild(l),rightChild(r){} //可选择参数的默认构造函数 }; //------------------------------------------------------------------------- template void PreOrder_2(BinTreeNode *p) //非递归前序遍历 { stack * > S;

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

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

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

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.举出二叉树的应用范例？ 答：一个集合的幂集、排列问题、组合问题

二叉树的基本操作实验报告

二叉树的基本操作实验报告 学号姓名实验日期 2012-12-26 实验室计算机软件技术实验指导教师设备编号 401 实验内容二叉树的基本操作 一实验题目 实现二叉树的基本操作的代码实现 二实验目的 1、掌握二叉树的基本特性 2、掌握二叉树的先序、中序、后序的递归遍历算法 3、通过求二叉树的深度、度为2的结点数和叶子结点数等算法三实习要求 (1)认真阅读书上给出的算法 (2)编写程序并独立调试 四、给出二叉树的抽象数据类型 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，?H，且存在D1上的关系H1 ?H;若Dr?Φ，则Dr中存在惟一的元素xr，?H，且存在上的关系 Hr ?H;H={,,H1,Hr};

// (4)(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树;(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。 //基本操作: CreateBiTree( &T, definition ) // 初始条件:definition给出二叉树T的定义。 // 操作结果:按definiton构造二叉树T。 BiTreeDepth( T ) // 初始条件:二叉树T存在。 // 操作结果:返回T的深度。 PreOrderTraverse( T, visit() ) // 初始条件:二叉树T存在，Visit是对结点操作的应用函数。 // 操作结果:先序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操 作失败。 InOrderTraverse( T, visit() ) // 初始条件:二叉树T存在，Visit是对结点操作的应用函数。 // 操作结果:中序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操 作失败。 PostOrderTraverse( T, visit() ) // 初始条件:二叉树T存在，Visit是对结点操作的应用函数。 // 操作结果:后序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操 作失败。 LeafNodes(p) // 初始条件:二叉树T存在。 // 操作结果:返回T的叶子结点数。

二叉树基本操作+数据结构+实验报告

郑州轻工业学院数据结构实验报告 题目 学生姓名 学号 专业班级 完成时间2016年月日

目录 一、系统功能介绍 (2) 二、需求分析 (2) 三、概要设计 (2) 四、详细设计 (5) 五、调试分析 (8) 六、使用说明 (8) 七、测试结果 (9) 八、心得体会 (10) 九、附录（程序代码） (11)

一、系统功能介绍 该系统主要功能是实现二叉树的定义和基本操作，包括定义二叉树的结构类型以及各个操作的具体函数的定义和主函数的定义。 各操作主要包括：初始化二叉树、按先序次序建立二叉树、检查二叉树是否为空、前序、中序、后序遍历树的方式、求树的深度、求树的结点数目、清空二叉树等九个对树的操作。 二、需求分析 本系统通过函数调用实现二叉树初始化，建立二叉树，检查树空与否，用前序、中序、后序遍历二叉树，求树的深度，求树的结点数目，清空二叉树等功能。 1）输出的形式和输出值的范围：在选择操作中，都以整型（数字）选择操作，插入和输出的数值都是char类型的字符； 2）输出的形式：在每次操作后，都会提示操作是否成功或者操作的结果； 3）程序达到的功能：完成初始化、检查是否为空、请空、遍历、求树的深度、求树的结点数目等功能； 4)测试数据设计： A,按先序次序建立二叉树。依次输入a,b,c,d,e,f,g.建立二叉树。 B,分别按先序，中序和后序遍历输出二叉树中的结点元素。 C,求树的高度和结点数。 三、概要分析 为了实现上述功能，定义二叉树的抽象数据类型。 ADT BinTree{ 数据对象D:D是具有相同特性的数据元素的集合。 数据关系R: 若D=￠，称BinTree为空二叉树 若D≠￠,则R={H},H是如下的二元关系； （1）在D中存在唯一的称为根的数据元素root,它在关系H下无前驱； （2）若D-{root}≠￠，则存在D-{root}={D1,Dr},且D1∩Dr=￠； （3）若D≠￠，则中存在唯一的元素x1,∈H,，且存在D1上的关系H1H;若则中存在唯一的元素且存在上的饿关系 （4）是一棵符合本定义的二叉树，称为根的左子树，是一棵符合本定义的二叉树，称为根的右子树。 基本操作P：

二叉树的基本操作完整版,包含二叉树的所有操作,凡是你想要的都在里面

#include "stdio.h" #include "stdlib.h" #include "string.h" #include "math.h" typedef char TElemType; //定义结点数据为字符型 typedef int Status; //定义函数类型为 int 型 #define ERROR 0 #define OK 1 }BiTNode, *BiTree; Status NumJudge(char ch[20]){ //限制输入数据必须为大于零的整形 char ch1[20]; int num; while(1){ scanf("%s",ch); num=atoi(ch); // 将字符串转换为整型 itoa(num,ch1,10); //将整型转换为字符串型 if(strcmp(ch,ch1)==0&&num>0)break; else{printf(" 请输入一个大于零的整数 : ");} } return num; }//NumJudge Status InitBiTree(BiTree &T){ //构造空二叉树 T if(!(T=(BiTree)malloc(sizeof(BiTNode))))exit(ERROR); T->next=NULL; printf("\n\t 空二叉树构建成功 !\n\n"); return OK; }//InitBiTree Status DestroyTree(BiTree &T,BiTree t){ //销毁二叉树 if(T){ free(T);T=NULL; printf （"\t 二叉树销毁成功 !\n"）; } if(t){ DestroyTree(T,t->lchild); DestroyTree(T,t->rchild); free(t); } return OK; }//DestroyTree Status ClearBiTree(BiTree &T,int sum,int &i){ //清空二叉树 if(T){ typedef struct BiTNode{ //定义结构 体 TElemType data; // 结点数值 struct BiTNode *lchild; // 左孩子指针 struct BiTNode *rchild; // 右孩子指针 struct BiTNode *next; //下一结点指针 //若申请空间失败则退出

二叉树的定义及基本操作

附件2： 北京理工大学珠海学院实验报告实验题目二叉树的定义及基本操作实验时间 一、实验目的、意义 （1）熟悉二叉链表表示的二叉树结构及其递归遍历。 （2）掌握建立二叉链表要领，深入理解递归遍历二叉链表的执行路径。 （3）根据具体问题的需要，能够设计出相关算法。 二、实验内容及要求 说明1：学生在上机实验时，需要自己设计出所涉及到的函数，同时设计多组输入数据并编写主程序分别调用这些函数，调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。 具体要求： （1）定义二叉树的链式存储结构； （2）建立一颗二叉链表表示的二叉树； （3）对其进行前序，中序，后序输出。（参见教材127页） （4）存储并写出下列表达式二叉树的前序、中序、后序输出。 - +/ a e f * b- c d 表达式二叉树1.中缀表达式（中序遍历）： a+(b*(c-d))-(e/f) 2.前缀表达式/波兰式（前序遍历）： -+a*b-cd/ef 3.后缀表达式/逆波兰式（后序遍历）： abcd-*+ef/- 引自严蔚敏《数据结构C语言版》P129

三、实验所涉及的知识点 递归函数 二叉树 四、实验记录 (调试过程及调试中遇到的问题及解决办法，其他算法的存在与实践等。) ①调试过程老是出现访问冲突的错问，通过上网查找访问冲突方面的消息，才知 道应该是指针指错地址，经过调试，最终解决了问题。 ② 调试过程中还出现了这个问题，Status CreateBiTree(BiTree T)，当这样定义时，问题就出现了，但是Status CreateBiTree(BiTree &T)这样定义就没问题了，这个想不通。 五、实验结果及分析