实验5：二叉树及其应用 一、实验目的
树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。 二、问题描述
首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。
如算术表达式：a+b*(c-d)-e/f 三、实验要求
1、 如果利用完全二叉树的性质和二叉链表
结构建立一棵二叉树，分别计算
a) 统计叶子结点的个数。
b) 求二叉树的深度。
2、 十进制的四则运算的计算器可以接收用户来自键盘的输入。
3、 由输入的表达式字符串动态生成算术表达式所对应的二叉树。
4、 自动完成求值运算和输出结果。 四、实验环境
PC 微机
DOS 操作系统或 Windows 操作系统
Turbo C 程序集成环境或 Visual C++ 程序集成环境 五、实验步骤
1、根据二叉树的各种存储结构建立二叉树；
2、设计求叶子结点个数算法和树的深度算法；
3、 根据表达式建立相应的二叉树，生成表达式树的模块；
4、根据表达式树，求出表达式值，生成求值模块；
5、 程序运行效果，测试数据分析算法。 六、代码
#include
#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10
int OP[8] = { '+', '-', '*', '/', '(', ')', '#', 0 };
-
+
/
a
*
b
-
e f
C d
typedef union
{
int Operator;
float Operand;
}operation;
typedef struct BiThrNode
{
operation data;
int IsOperator;
struct BiThrNode *lchild, *rchild;
}BiThrNode, *BiThrTree;
typedef BiThrTree SElemType;
typedef BiThrTree QElemType;
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
void InitStack(SqStack &S)
{
S.base =
(SElemType*)malloc(STACK_INIT_SIZE*sizeof( SElemType));
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
}
void Push(SqStack &S, SElemType e)
{
if (S.top - S.base >= S.stacksize)
{
S.base =
(SElemType*)realloc(S.base, (S.stacksize + STACKINCREMENT)*sizeof(SElemType));
if (!S.base)
exit(1);
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
}
int Pop(SqStack &S, SElemType &e) {
if (S.base == S.top)
return 0;
e = *--S.top;
return 1;
}
BiThrTree GetTop(SqStack s)
{
BiThrTree e;
if (s.top == s.base)
return NULL;
e = *(s.top - 1);
return e;
}
int IsEmpty(SqStack s)
{
if (s.top == s.base)
return 1;
else
return 0;
}
int In(int c, int *op)
{
while (*op != 0)
{
if (c == *op)
return 1;
op++;
}
return 0;
}
int Precede(int theta1, int theta2) {
int i, j;
int op_look[7][7] =
{ { '>', '>', '<', '<', '<', '>', '>' },
{ '>', '>', '<', '<', '<', '>', '>' },
{ '>', '>', '>', '>', '<', '>', '>' },
{ '>', '>', '>', '>', '<', '>', '>' },
{ '<', '<', '<', '<', '<', '=', ' ' },
{ '>', '>', '>', '>', ' ', '>', '>' },
{ '<', '<', '<', '<', '<', ' ', '=' }
};
switch (theta1)
{
case '+':i = 0; break;
case '-':i = 1; break;
case '*':i = 2; break;
case '/':i = 3; break;
case '(':i = 4; break;
case ')':i = 5; break;
case '#':i = 6; break;
default:
return 0;
}
switch (theta2)
{
case '+':j = 0; break;
case '-':j = 1; break;
case '*':j = 2; break;
case '/':j = 3; break;
case '(':j = 4; break;
case ')':j = 5; break;
case '#':j = 6; break;
default:
return 0;
}
return op_look[i][j];
}
int Nodenum(BiThrTree T) {
int nnum1, nnum2;
if (!T)
return 0;
nnum1 = Nodenum(T->lchild);
nnum2 = Nodenum(T->rchild);
return 1 + nnum1 + nnum2;
}
int Leafnum(BiThrTree T)
{
int lnum1, lnum2;
if (!T)
return 0;
if (!T->lchild&&!T->rchild)
return 1;
lnum1 = Leafnum(T->lchild);
lnum2 = Leafnum(T->rchild);
return lnum1 + lnum2;
}
int Height(BiThrTree T)
{
int h1, h2;
if (!T)
return 0;
h1 = Height(T->lchild);
h2 = Height(T->rchild);
return 1 + ((h1>h2) ? h1 : h2);
}
int Wide(BiThrTree T, int *w, int a)
{
if (!T)
return 0;
else
{
if (T)
w[a] = w[a] + 1;
if (T->lchild)
Wide(T->lchild, w, a + 1);
if (T->rchild)
Wide(T->rchild, w, a + 1);
}
return 1;
}
int isNum(int c)
{
if (c >= '0' && c <= '9')
return 1;
else return 0;
}
int GetInput(operation *Result)
{
static int buffer = 0;
int c;
operation result;
int IsNumber = 0;
int IsFloat = 0;
int i, t = 1;
result.Operand = 0;
if (In(buffer, OP))
{
result.Operator = buffer;
buffer = 0;
Result->Operator = result.Operator;
return 2;
}
c = getchar();
while (c == ' ' && c != 10)
{
c = getchar();
}
while (c != ' ' && c != 10)
{
if (isNum(c))
{
IsNumber = 1;
c = c - 48;
if (IsFloat == 0)
result.Operand = result.Operand * 10 + c;
else
{
result.Operand = result.Operand * 10 + c;
IsFloat++;
}
}
else if (c == '.')
{
if (IsFloat != 0)
{
Result-
>Operand = 0;
return 0;
}
else
IsFloat = 1;
}
else if (In(c, OP))
{
if (IsNumber)
{
if (IsFloat == 1)
{
Result->Operand = 0;
return 0;
}
else
{
buffer = c;
for (i = 0; i t *= 10; Result->Operand = result.Operand / (float)t; return 1; } } else { Result- >Operator = c; return 2; } } c = getchar(); } buffer = 0; if (IsNumber) { if (IsFloat == 1) { Result->Operand = 0; return 0; } else { for (i = 0; i - 1; i++) t *= 10; Result->Operand = result.Operand / (float)t; return 1; } } else if (result.Operand == 0) { Result->Operand = 0; return 0; } else { Result->Operator = result.Operator; return 2; } } BiThrTree CreateBiTree() { SqStack Operand; SqStack Operator; BiThrTree pNode; BiThrTree theta, a, b; operation c; cout<<"输入算式，以'#'结尾"< int r = GetInput(&c); InitStack(Operand); InitStack(Operator); pNode = (BiThrTree)malloc(sizeof(SElemType)); pNode->data.Operator = '#'; pNode->IsOperator = 1; pNode->lchild = NULL; pNode->rchild = NULL; Push(Operator, pNode); while (!(r == 2 && c.Operator == '#') || GetTop(Operator)->data.Operator != '#') { if (r == 0) return NULL; if (r == 1) { pNode = (BiThrTree)malloc(sizeof(SElemType)); pNode- >data.Operand = c.Operand; pNode->IsOperator = 0; pNode->lchild = NULL; pNode->rchild = NULL; Push(Operand, pNode); r = GetInput(&c); } else if (r == 2) { switch (Precede(GetTop(Operator)->data.Operator, c.Operator)) { case '<': pNode = (BiThrTree)malloc(sizeof(SElemType)); pNode- >data.Operator = c.Operator; pNode- >IsOperator = 1; pNode- >lchild = NULL; pNode- >rchild = NULL; Push(Operator, pNode); r = GetInput(&c); break; case '=': Pop(Operator, pNode); r = GetInput(&c); break; case '>': Pop(Operator, theta); Pop(Operand, b); Pop(Operand, a); theta- >lchild = a; theta- >rchild = b; Push(Operand, theta); break; } } } return GetTop(Operand); } bool calculate(BiThrTree T, float *result) { float resultlchild; float resultrchild; if (T != NULL) { if (T->lchild == NULL && T->rchild == NULL) { *result = T- >data.Operand; return true; } else if (T->lchild == NULL || T->rchild == NULL) return false; else { switch (T- >data.Operator) { case '+': if (calculate(T->lchild, &resultlchild) == false) return false; if (calculate(T->rchild, &resultrchild) == false) return false; *result = resultlchild + resultrchild; break; case '-': if (calculate(T->lchild, &resultlchild) == false) return false; if (calculate(T->rchild, &resultrchild) == false) return false; *result = resultlchild - resultrchild; break; case '*': if (calculate(T->lchild, &resultlchild) == false) return false; if (calculate(T->rchild, &resultrchild) == false) return false; *result = resultlchild * resultrchild; break; case '/': if (calculate(T->lchild, &resultlchild) == false) return false; if (calculate(T->rchild, &resultrchild) == false) return false; *result = resultlchild / resultrchild; break; } } } return true; } void main() { BiThrTree T; float result; if (T = CreateBiTree()) { cout<<"叶子数: "< cout<<"深 度:"< if (calculate(T, &result)) { cout<<"Result:"< } else cout<<"0"; } else cout<<"INPUT 0"< #include { inorder(p->lchild); printf("%c ",p->data); inorder(p->rchild); } } void postorder(TREE *p) //后序遍历 { if (p!=NULL) { postorder(p->lchild); postorder(p->rchild); printf("%c ",p->data); } } void shu(TREE *p,int len) //数的形状{ if (p!=NULL) { shu(p->lchild,len+1); for (int i=1;i<=4*len;i++) { printf(" "); } printf("%c",p->data); printf("------\n"); shu(p->rchild,len+1); } } int shendu(TREE *p) //计算深度 { int l,r; if (p==NULL) { return 0; } l=shendu(p->lchild)+1; r=shendu(p->rchild)+1; if (l>=r) //左右子树比较return l; else 二叉树的基本操作实现及其应用 一、实验目的 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<<"二叉树初始化成功!"< 二叉树的应用研究 苏雨洁 （盐城工学院优集学院江苏盐城224001） 摘要：课堂上学习可以知道，二叉树可以简单明了的表示很多繁琐的信息数据。同时，二叉树在有很多方面有具体的应用。通过搜集各方面的资料发现，越来越多的领域开始选择使用二叉树模型来进行设计投资决策，并以此为平台，实现了很多的功能，本文结合了多领域的知识，给出了在生活方面，学习方面，以及理财投资方面的多种实例，并且加以概括和介绍。 关键词：二叉树；数据结构；结点；数组；期权 Study on the application of the binary tree SU Yujie (UGS College, Yancheng Institute of Technology, Yancheng, Jiangsu 224001) Abstract: Through learning in the classroom we can know, binary tree can be simple and clear to show many complicated data.At the same time,binary tree have specific applications in many aspects.Through the collection of information in many aspects,we can find that more and more fields start to use the binomial tree model to design,invest and making descisions. Use it as a platform ,achieving a lot of functions. This article incorporates knowledge from many fields and show a variety of examples in the aspects of living, learning, and financial investment.And summarize and introduce. Key words: Binary tree;Data structure; Node; Array; Option 0引言 在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。逻辑上二叉树有五种基本形态：空二叉树，只有一个根结点的二叉树，右子树为空的二叉树，左子树为空的二叉树，完全二叉树；本文根据二叉树的性质形态，研究了二叉树在各个领域的应用实例，并且展望了二叉树在更多领域的应用。 1二叉树在学习上的应用 1.1二叉树平面坐标网及其应用 平面坐标系是把平面上的点映射为一对有序实数，坐标系是形数结合的桥梁。在图形，图像处理中，要处理的点数很多，能都有效的表示点就成为能否有效地处理图形图像的基本问题。数学上普遍使用切分方法，把一个复杂的几何对象近似表示成简单的几何对象的几何，集合中简单的几何对象位置就由其特征点（或点集）的坐标决定。把复杂的几何对象近似的 课程设计任务书 题目: 二叉排序树的建立及遍历的实现 初始条件： 理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法； 实践：计算机技术系实验室提供计算机及软件开发环境。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、系统应具备的功能： （1）建立二叉排序树； （2）中序遍历二叉排序树并输出排序结果； 2、数据结构设计； 3、主要算法设计； 4、编程及上机实现； 5、撰写课程设计报告，包括： （1）设计题目； （2）摘要和关键字； （3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、设计体会等； （4）结束语； （5）参考文献。 时间安排：2007年7月2日－7日（第18周） 7月2日查阅资料 7月3日系统设计，数据结构设计，算法设计 7月4日-5日编程并上机调试7月6日撰写报告 7月7日验收程序，提交设计报告书。 指导教师签名： 2007年7月2日 系主任（或责任教师）签名： 2007年7月2日 排序二叉树的建立及其遍历的实现 摘要：我所设计的课题为排序二叉树的建立及其遍历的实现，它的主要功能是将输入的数据 组合成排序二叉树，并进行，先序，中序和后序遍历。设计该课题采用了C语言程序设计，简洁而方便，它主要运用了建立函数，调用函数，建立递归函数等等方面来进行设计。 关键字：排序二叉树，先序遍历，中序遍历，后序遍历 0．引言 我所设计的题目为排序二叉树的建立及其遍历的实现。排序二叉树或是一棵空树；或是具有以下性质的二叉树：（1）若它的左子树不空，则作子树上所有的结点的值均小于它的根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；(3）它的左，右子树也分别为二叉排序树。对排序二叉树的建立需知道其定义及其通过插入结点来建立排序二叉树，遍历及其输出结果。 该设计根据输入的数据进行建立排序二叉树。对排序二叉树的遍历，其关键是运用递归 调用，这将极大的方便算法设计。 1．需求分析 建立排序二叉树，主要是需要建立节点用来存储输入的数据，需要建立函数用来创造排序二叉树，在函数内，需要进行数据比较决定数据放在左子树还是右子树。在遍历二叉树中，需要建立递归函数进行遍历。 该题目包含两方面的内容，一为排序二叉树的建立；二为排序二叉树的遍历，包括先序遍历，中序遍历和后序遍历。排序二叉树的建立主要运用了循环语句和递归语句进行，对遍历算法运用了递归语句来进行。 2．数据结构设计 本题目主要会用到建立结点，构造指针变量，插入结点函数和建立排序二叉树函数，求深度函数，以及先序遍历函数，中序遍历函数和后序遍历函数，还有一些常用的输入输出语句。对建立的函明确其作用，先理清函数内部的程序以及算法在将其应用到整个程序中，在建立排序二叉树时，主要用到建立节点函数，建立树函数，深度函数，在遍历树是，用到先序遍历函数，中序遍历函数和后序遍历函数。 内蒙古科技大学 本科生课程设计说明书 题目：数据结构课程设计 ——二叉树的遍历和应用 学生姓名： 学号： 专业： 班级： 指导教师： 2013年5月29日 内蒙古科技大学课程设计说明书 内蒙古科技大学课程设计任务书 I 内蒙古科技大学课程设计说明书 目录 内蒙古科技大学课程设计任务书..............................................................错误！未定义书签。目录....................................................................................................................................II 第一章需求分析 (3) 1.1课程设计目的 (3) 1.2任务概述 (3) 1.3课程设计内容 (3) 第二章概要设计 (5) 2.1设计思想 (5) 2.2二叉树的遍历 (5) 2.3运行界面设计 (6) 第三章详细设计 (7) 3.1二叉树的生成 (7) 3.2二叉树的先序遍历 (7) 3.3 二叉树的中序遍历 (8) 3.4二叉树的后续遍历 (8) 3.5主程序的设计 (8) 第四章测试分析 (11) 4.1二叉树的建立 (11) 4.2二叉树的先序、中序、后序遍历 (11) 第五章课程设计总结 (12) 附录：程序代码 (13) 致谢 ···········································································································错误！未定义书签。 II 实验6:二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的 特性，以及如何应用树结构解决具体问题。 二、问题描述 首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达 式的基础上，设计一个十进制的四则运算的计算器。 三、实验要求 1、 如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算 a) 统计叶子结点的个数。 b) 求二叉树的深度。 2、 十进制的四则运算的计算器可以接收用户来自键盘的输入。 3、 由输入的表达式字符串动态生成算术表达式所对应的二叉树。 4、 自动完成求值运算和输出结果。 四、实验环境 PC 微机 DOS 操作系统或Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 五、实验步骤 1、 根据二叉树的各种存储结构建立二叉树； 2、 设计求叶子结点个数算法和树的深度算法； 3、 根据表达式建立相应的二叉树，生成表达式树的模块； 如算术表达式：a+b*(c-d)-e/f + / a e b C d 5、程序运行效果，测试数据分析算法。 六、功能分析 4、根据表达式树，求出表达式值，生成求值模块； 存储结构 typedef union{ int Operator; // 操作符 float Opera nd; // 操作数 }ln t_Float; //表达式树 typedef struct Bin aryTreeNode{ In t_Float Data; // 数据域 int IsOperator; // 判断是不是操作数的标志位 struct Bi naryTreeNode *RChild;〃左子树 struct Bi naryTreeNode *LChild;〃右子树 }BiTreeNode, *lpBiTreeNode; //栈的定义 typedef struct { lpBiTreeNode *base; lpBiTreeNode *top; int stacksize; }SqStack; 函数一览表 lpBiTreeNode GetTop( SqStack s );// 取栈顶结点函数 int lsEmpty( SqStack s );// 判空函数 int In itStack( SqStack &s );// 初始化栈函数 int Pop( SqStack & s, lpBiTreeNode &e );// 出栈函数 int Push( SqStack & s, lpBiTreeNode e );// 入栈函数 int ln( int c, int* op );// 判断c 是否在op 中 int Precede( int thetal, i nt theta2 );// 比较运算符号的优先级 int isNum( int c );// 判断是不是数 int Getl nput(l nt_Float *Result);// 读入输入的数 lpBiTreeNode CreateBiTree();// 创建二叉树 bool calculate(lpBiTreeNode Root, float *result);// 计算二叉树化表达式的值in t getLeafNum(lpBiTreeNode Root);// 计算二叉树的叶子结点数 in t getDepth(lpBiTreeNode Root);// 计算二叉树的深度 实验6：二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。 二、问题描述 首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：a+b*(c-d)-e/f 三、实验要求 1、 如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算 a) 统计叶子结点的个数。 b) 求二叉树的深度。 2、 十进制的四则运算的计算器可以接收用户来自键盘的输入。 3、 由输入的表达式字符串动态生成算术表达式所对应的二叉树。 4、 自动完成求值运算和输出结果。 四、实验环境 PC 微机 DOS 操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 五、实验步骤 1、根据二叉树的各种存储结构建立二叉树； 2、设计求叶子结点个数算法和树的深度算法； 3、根据表达式建立相应的二叉树，生成表达式树的模块； - + / a * b - e f C d 4、根据表达式树，求出表达式值，生成求值模块； 5、程序运行效果，测试数据分析算法。 六、功能分析 存储结构 typedef union{ int Operator; // 操作符 float Operand; // 操作数 }Int_Float; //表达式树 typedef struct BinaryTreeNode{ Int_Float Data; //数据域 int IsOperator; //判断是不是操作数的标志位 struct BinaryTreeNode *RChild;//左子树 struct BinaryTreeNode *LChild;//右子树 }BiTreeNode, *lpBiTreeNode; //栈的定义 typedef struct { lpBiTreeNode *base; lpBiTreeNode *top; int stacksize; }SqStack; 函数一览表 lpBiTreeNode GetTop( SqStack s );//取栈顶结点函数 int IsEmpty( SqStack s );//判空函数 int InitStack( SqStack &s );//初始化栈函数 int Pop( SqStack &s, lpBiTreeNode &e );//出栈函数 int Push( SqStack &s, lpBiTreeNode e );//入栈函数 int In( int c, int* op );// 判断c是否在op中 int Precede( int theta1, int theta2 );//比较运算符号的优先级 int isNum( int c );//判断是不是数 int GetInput(Int_Float *Result);//读入输入的数 lpBiTreeNode CreateBiTree();//创建二叉树 bool calculate(lpBiTreeNode Root, float *result);//计算二叉树化表达式的值int getLeafNum(lpBiTreeNode Root);//计算二叉树的叶子结点数 实验3 二叉树及其应用 实验目的 1.加深对二叉树的结构特性的理解； 2.熟练掌握二叉树的存储结构，特别是二叉链表类的描述及其实现方法； 3.熟练掌握二叉树的遍历算法原理及实现； 4.学会编写实现二叉树的各种算法； 5.掌握二叉树的应用方法。 实验学时：建议2~4学时 实验内容 内容1：二叉树及其操作 【问题描述】 设计二叉树的二叉链表类，操作主要有建二叉树、遍历二叉树、求该二叉树中、的结点个数等。 【基本要求】 （1）建立二叉树可用先序方式建立，也可根据二叉树的先序和中序序列建立。 （2）对二叉树的遍历可采用递归或非递归的算法。 【实现提示】 （1）二叉链表的结点结构描述 struct btnode{ // 定义结点类型 ElemType data; //数据域 btnode * lchild，* rchild; //左、右指针域/ }; // btnode （2）可设计以下功能函数： btnode* createbitree(); //建立二叉链表 void preorder(btnode* bt); //先序遍历二叉树 int sum(btnode* bt); //求二叉树中的结点个数 算法可用递归或非递归实现。 建立二叉树可用以下两种算法实现： 方案1：btnode * createBT ( ) //前序建树 { bitree T; char ch; cin >>ch ; if(ch==’#’) return NULL; //二叉树为空 T=new BinTNode; //申请根结点 T->data=ch; T->lchild=createBTpre(); //创建根的左子树 1 实验五二叉树建立及应用 一、实验目的 1．熟悉二叉树的存贮结构及遍历方式，掌握有关算法的实现。 2．能够利用二叉树解决具体问题。 二、实验环境 ⒈硬件：每个学生需配备计算机一台。操作系统：DOS或Windows； ⒉软件：DOS或Windows操作系统+Turbo C； 三、实验要求 ⒈要求采用二叉链表作为存贮结构，完成二叉树的建立、先序、中序、和后序遍历的 操作。 ⒉输入数据：树中每个结点的数据类型设定为字符型。 3．设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD###CE##F##，建立二叉树，求出先序、中序和后序遍历，求该二叉树所有叶子结点总数。 四、实验内容 附：参考程序为类C语言程序，非标准C语言程序，需要进行相应的修改。 二叉链表结构如下：P134 typedef struct lnode {char data; struct lnode *lchild,*rchild; }lnode,*tree; 1．建树子函数P137 status creat(tree &t) {//按先序次序输入二叉树中结点的值，’.’字符表示空树 scanf(&ch); if(ch=='.') t=null; else {t=(tree)malloc(sizeof(lnode)); t->data=ch; creat(t->lchild); creat(t->rchild);} return ok; } 2．先序遍历子函数P136 preorder(tree t) { if(t!=null) {printf(t->data); preorder(t->lchild); preorder(t->rchild); } } 3．后序遍历子函数P136 postorder(tree t) {if(t!=null) {postorder(t->lchild); postorder(t->rchild); printf(t->data); } } 五、思考题 1. 已知二叉树先序和中序序列，唯一地构造一棵二叉树并且验证其正确性。 2. 建立一个二叉树，并且按层次遍历操作。 六、报告要求 1．报告要求用专门的实验报告纸书写，字迹清晰，格式规范。 2．报告中应写清姓名、学号、实验日期、实验题目、实验目的、实验要求。 实验六最优二叉树的应用 【实验目的】 掌握求最优二叉树的方法。 【实验内容】 最优二叉树在通信编码中的应用。要求输入一组通信符号的使用频率 {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 public class Tree if(root==null) return false; if(data!=null) { if(!isEmptyTree() && root.equals(data)) return true;//如果树不空，而且根等于data返回true if(!leftChild.isEmptyTree() && leftChild.exists(data)) return true; if(!right.isEmptyTree() && right.exists(data)) return true; } return false; } /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub Tree 实验一最优二叉树及其应用 1．程序设计简介 本实验程序用于验证最优二叉树的算法。树的存储采用带孩子的双亲顺序存储方法。2．源程序 //最优二叉树 #include 广西工学院计算机学院 《数据结构》课程实验报告书 实验六二叉树的基本操作及其应用 学生姓名： 学号： 班级： 指导老师： 专业：计算机学院软件学院 提交日期：2013年6月22日 1．实验目的 1）了解二叉树的特点、掌握二叉树的主要存储结构。 2）掌握二叉树的基本操作，能针对二叉树的具体应用选择相应的存储结构。 3）掌握递归算法的设计方法。 2.实验内容 （1）二叉链表表示二叉树，建立一棵二叉树，实现下列基本操作,通过数据测试每个操作的正确性，包括： 1. CreateBinTree(&T)：建立一颗二叉树：。 2. BinTreeEmpty(T): 判断一棵二叉树是否为空树。 3. PreOrderTraverse(T): 先序遍历二叉树T，并输出节点序列。 4. InOrderTraverse(T): 中序遍历二叉树T，并输出节点序列。 5. PostOrderTraverse(T):后序遍历二叉树T，并输出节点序列。 6. LevelOrderTraverse(T):层次遍历二叉树T，并输出节点序列。 7. Value(T,e):查找值为e的节点，并返回该节点的地址。 8. BinTreeDepth(T):返回二叉树的深度。 9. Parent(T,e):查找二叉树T中值为e的节点的双亲，若e为根节点，操作失 败。（流程图） 10. LeftChild(T,e):查找二叉树T中值为e的节点的左孩子，若e没有左孩子， 则操作失败。（流程图） 11.RightChild(T,e):查找二叉树T中值为e的节点的右孩子，若e没有右孩子， 则操作失败。 12. CountNode(T):计算二叉树中节点的个数。 13. Leaf(T): 计算二叉树中叶子节点的个数。 14. OneChild(T): 计算二叉树中度为1的节点个数。 3．实验要求 （1）上机前交实验源程序（纸质版），由学习委员统一收好交老师（附上不交同学名单）。 （2）用一切你能想到的办法解决遇到的问题，培养解决问题的能力。 （3）实验课上进行答辩。 （4）实验报告当场交。报告内容包括：实验目的、实验内容、实验代码、实验运行结果以及实验体会供五部分。 第六章树和二叉树的应用 6.1二叉排序树和平衡二叉树 在实际应用中，常常需要在一组记录中检索一个记录，向其中插入一个记录或者把找到的记录删除。 如果记录无序，查找起来将会很慢。如果记录有序，查找将会很快。但是遇到动态增减变化时，需要移动大量的元素。即使使用链表结构，查找起来也相当麻烦。非常需要一中插入、删除、和检索记录效率都很高的数据组织方法。二叉排序（查找、搜索）树就是这样一种高效的数据结构。 二叉排序树也称二叉查找树或二叉搜索树。它或者是一棵空树； 或者有性质： （1）若其左子树不空，则左子树上所有结点的值均小于根结点 的值。 （2）若其右子树不空，则右子树上所有结点的值均大于根结点 的值。 （3）左右子树也为二叉排序树。 图5.21就是一棵二叉排序树。二叉排序树通常采用二叉链存储结构。二叉链存储结构的结点类型定义： typedefstructtnode { KeyTypekey;//关键字域 ElemTypedata;//其他数据域 structtnode*lchild,*rchild;//指针 }BSTNode; 中序遍历二叉排序树可以得到有序序列。 6.1.2二叉排序树的基本运算 二叉排序树的基本运算如下： 1.BSTSearch(bt,k)在二叉排序树bt中，查找值为k的结点。 2.BSTInsert(bt,k)在二叉排序树bt中，插入值为k的结点。 3.CreateBST(bt,str,n)创建二叉排序树 4.输出二叉排序树DispBST(bt) 5.删除结点BSTDelete(bt,k) 1.查找结点BSTSearch(bt,k) 方法：将给定值k与查找树的根结点关键码比较。若相等，查找成功，结束查找过程。否则，a．当给k小于根结点关键码，查找将在以左子女为根的子树上继续进行； b．当给k大于根结点关键码，查找将在以右子女为根的子树上继续进行； /************************************************************************/ 二叉树在C语言中的实现与应用 /************************************************************************/ #include 数据结构实验五 课程数据结构实验名称二叉树的建立及遍历第页 专业班级学号 姓名 实验日期:年月日评分 一、实验目的 １．学会实现二叉树结点结构和对二叉树的基本操作。 ２．掌握对二叉树每种操作的具体实现,学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。 二、实验要求 1．认真阅读和掌握和本实验相关的教材内容。 2．编写完整程序完成下面的实验内容并上机运行。 3.整理并上交实验报告。 三、实验内容 1.编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树,采用三种递归遍历算法（前序、中序、后序）对这棵二叉树进行遍历并计算出二叉树的高度。 2 .编写程序生成下面所示的二叉树,并采用先序遍历的非递归算法对此二叉 树进行遍历。 四、实验步骤 （描述实验步骤及中间的结果或现象。在实验中做了什么事情，怎么做的,发生的现象和中间结果) 第一题 #ｉnｃlude "sｔdafx.ｈ" #include＂ｉoｓtｒeam.h" #inclｕde"sｔｄliｂ.h" ＃incｌudｅ"ｓｔdiｏ.ｈ" #include 实验四 二叉树的建立和应用 1、实验目的 （1）熟练掌握树的基本概念、二叉树的基本操作及在链式存储结构上的实现； （2）重点掌握二叉树的生成、遍历及求深度等算法； （3）掌握运用递归方式描述算法及编写递归C 程序的方法，提高算法分析和程序设计能力。 2、实验内容 按照已知二叉树，从键盘读入节点字符，建立二叉树（ABD#G###CE##FH###） ；分别采用先序、中序、后序遍历该二叉树，分别输出遍历结果。 3、实验步骤 （1）仔细分析实验内容，给出其算法和流程图； （2）用C 语言实现该算法； （3）给出测试数据，并分析其结果； （4）在实验报告册上写出实验过程。 4、测试数据 先序序列： ABDGCEFHjfkdkfakf 中序序列： DGBAECHF 后序序列： GDBEHFCA 5、结构定义 typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; 6、实验报告要求 实验报告要求书写整齐，步骤完整，实验报告格式如下： 1、［实验目的］ 2、［实验设备］ 3、［实验步骤］ 4、［实验内容］ 5、［实验结果(结论)］ G H B C D E F A 程序如下： #include "stdio.h" #include "string.h" typedef char TElemType ; typedef struct BiNode { TElemType data; struct BiNode * lchild ,* rchild; }BiNode ,*BiTree; BiTree CreateBiTree(BiTree bt) { char ch; B iTree h=NULL; c h=getchar(); i f(ch=='#') bt=NULL; e lse { if((bt=(BiNode *)malloc(sizeof(BiNode)))==NULL) exit(-2); bt->data=ch; bt->lchild=CreateBiTree(h); bt->rchild=CreateBiTree(h); } r eturn(bt); } void PreOrderTraverse(BiTree bt)二叉树的建立及其应用程序代码
实验三 二叉树的基本操作实现及其应用
二叉树的应用研究
二叉排序树的建立及遍历的实现
二叉树的遍历和应用
实验6：二叉树及其应用
实验二叉树及其应用(严选材料)
实验3 二叉树及其应用
实验5 二叉树建立及应用
实验六 最优二叉树的应用
java二叉树的建立与应用代码
数据结构—最优二叉树及其应用
二叉树的基本操作及其应用
数据结构之树和二叉树的应用
二叉树在C语言中的实现与应用详解
二叉树的建立及遍历
数据结构课程实验(树和二叉树的建立和应用)
相关主题
文本预览