数据结构二叉树教案

实验六：二叉树及其应用

一、实验目的

树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。

二、问题描述

首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：a+b*(c-d)-e/f

三、实验要求

如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算统计叶子结点的个数。求二叉树的深度。十进制的四则运算的计算器可以接收用户来自键盘的输入。由输入的表达式字符串动态生成算术表达式所对应的二叉树。自动完成求值运算和输出结果。

四、实验环境

PC微机

DOS操作系统或 Windows 操作系统

Turbo C 程序集成环境或 Visual C++ 程序集成环境 1、根据二叉树的各种存储结构建立二叉树；

2、设计求叶子结点个数算法和树的深度算法；

3、根据表达式建立相应的二叉树，生成表达式树的模块； 4、根据表达式树，求出表达式值，生成求值模块； 5、程序运行效果，测试数据分析算法。

五、实验步骤

六、测试数据

1、输入数据：2.2*（3.1+1.20）-7.5/3

正确结果：6.9

第六章 习题

一、选择题

1、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个 A 、4 B、5 C、6 D、 7

2、假定在一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（ ）个。

A、 15 B、16 C、17 Ｄ、47

3、假定一棵三叉树的结点数为50，则它的最小高度为（ ） A、 3 B、4 C、5 D、6

4、在一棵二叉树上第5层的结点数最多为（ ） A、8 B、 16 C、 15 D、32

5、用顺序存储方式将完全二叉树中的所有结点逐层存放在数组R[1..n]中，结点R[I]若有子树，则左子树是结点（ ）

A、R[2I+1] B、R[2I] C、R[I/2] D、R[2I-1] 6、在一棵具有k层的满三叉树中，结点总数为（ ） A、（3k-1）/2 B、3k-1 C、（3k-1）/3 D、3k

7、由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（

第六章 树和二叉树

一、选择题

1．已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )

A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE 【北京航空航天大学 1999 一、3 （2分)】

2．算术表达式a+b*（c+d/e）转为后缀表达式后为（ ）【中山大学 1999 一、5】

A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++ / 3. 设有一表示算术表达式的二叉树（见下图），

+ + 它所表示的算术表达式是（ ）

【南京理工大学1999 一、20（2分）】 * - * C A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) E F G D B A C. (A*B+C)/(D*E+（F-G）) D. A*B+C/D*E+F-G

则T中的叶子 ，1 4. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1

数为（ ）

A．

第六章 树和二叉树

一、选择题

1．已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )

A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE 【北京航空航天大学 1999 一、3 （2分)】

2．算术表达式a+b*（c+d/e）转为后缀表达式后为（ ）【中山大学 1999 一、5】

A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++ / 3. 设有一表示算术表达式的二叉树（见下图），

+ + 它所表示的算术表达式是（ ） 【南京理工大学1999 一、20（2分）】 * - * C A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) B D E F G A C. (A*B+C)/(D*E+（F-G）) D. A*B+C/D*E+F-G

则T中的叶子 ，1 4. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1

数为（ ）

A．

数据结构上机实验报告

二叉树问题

陈冠豪

2010210501

0101015

二O一O年5月26号

验的目建一棵立二树叉要，分别求递用归和递非方法实归二现 叉树的先、序序中和序遍后历。

实现代码:

#ifndef TREE_H #define TREE_H #include <stdio.h> #include <malloc.h> #include <stack> #include <queue> #include <assert.h> using namespace std; typedefintElemType; typedef struct treeT { ElemType key; struct treeT* left; struct treeT* right; }treeT, *pTreeT;

static void visit(pTreeT root) { if (NULL != root) { printf(" %d\n", root->key); } } static pTreeT BT_MakeNode(E

武汉纺织大学

数学与计算机学院

数据结构课程设计报告

二叉树的编码

学生姓名： 学号： 班级： 指导老师： 报告日期：年月日

1 题目与要求

1.1 问题提出

其中，x，y是两个整数坐标，采用由上至下和从左到右的方法对这些坐标进行赋值；size表示结点所有子孙结点的个数；depth表示结点的层次。如下图所示：

A（1，22，10，1）括号内数值含义（x，y，size，depth）B（2，11，4，2）C（12，21，4，2）D（3，10，3，3）E（13，14，0，3）F（15，20，2，3）G（4，5，0，4）H（6，9，1，4）I（16，19，1，4）J（7，8，0，5）

K（17，18，0，5）要求利用所学的知识编写代码创建二叉树，求x,y,size,depth的值，并完成相应的操作，掌握二叉树的基本知识！

1.2 本系统涉及的知识点

涉及的相关知识点： 1.二叉树的先序建立 2.递归算法 3.队列

4.逆中序输出结点 5.二叉树的遍历 6.凹入法

1.3 功能要求

实现的主要功能：

⑴根据课本“算法6.4”建立上图所示的二叉树，并且对每个结点的（x，y，size，depth）都赋零值，即（0，0，0，0）。 ⑵编写算法求每个结点的

数据结构二叉树基本操作

(1).

// 对二叉树的基本操作的类模板封装

//------------------------------------------------------------------------------------------------------------------------

#include using namespace std;

//------------------------------------------------------------------------------------------------------------------------

//定义二叉树的结点类型BTNode,其中包含数据域、左孩子，右孩子结点。 template struct BTNode {

T data ; //数据域 BTNode* lchild; //指向左子树的指针 BTNode* rchild; //指向右子树的指针 };

//-------------------------------------------------

摘要

针对现实世界中许多关系复杂的数据，如人类社会的家谱，各种社会组织机构,博弈交通等复杂事物或过程以及客观世界中广泛存在的具有分支关系或层次特性的对象．如操作系统的文件构成、人工智能和算法分析的模型表示以及数据库系统的信息组织形式等，用线性结构难以把其中的逻辑关系表达出来，必须借助于数和图这样的非线性结构，因此在以模拟客观世界问题，解决客观世界问题为主要任务的计算机领域中树型结构是信息的一种重要组织形式，树有着广泛应用。在树型结构的应用中又以二叉树最为常用。

二叉树是一种非常重要的非线性结构，所描述的数据有明显的层次关系，其中的每个元素只有一个前驱，二叉树是最为常用的数据结构，它的实际应用非常广泛，二叉树的遍历方式有三种，前序遍历，中序遍历，后序遍历，先序遍历的顺序为：NLR先根结点，然后左子树，右子树；中序遍历顺序为；LNR先左子树，然后根结点，右子树；后序遍历顺序为：LRN先左子树，然后右子树，根结点。由前序和中序遍历，有中序和后序遍历序列可以唯一确定一棵二叉树。对于给几个数据的排序或在已知的几个数据中进行查找，二叉树均能提供一种十分有效的方法，比如在查找问题上，任何借助于比较法查找长度为Ⅳ的一个序表的算法，都可以表示成一株二叉树。反之

遍历二叉树课程教案

授课方式 （请打√） 教学目的： （1）掌握树的各种术语，例如根、叶子、度、深度； （2）掌握二叉树的定义； （3）掌握二叉树的遍历方法； 理论课□ 讨论课□ 实验课□ 习题课□ 其他□ 课时 安排 授课题目：遍历二叉树 要求：（1）提高学生的认知能力； （2）培养学生自主学习和团结协作的能力； 教学重点及难点： 重点：（1）二叉树的定义； （2）二叉树的遍历方法。 难点：二叉树的遍历 教 学 基 本 内 容 遍历二叉树 一、二叉树的定义： 树基本定义： 树：包含N个结点的有穷集合；（N>0） 根：没有父母的结点； 叶子：没有孩子的结点或者度为0的结点； 度：某个结点孩子的个数； 深度：二叉树的层数 1.二叉树是每个结点的度都为2的有序树，它的特点是每个结点至多有两棵子树。 二叉树与树有区别：树至少应有一个结点，而二叉树可以为空；树的子树没有顺序，但如果二叉树的根结点只有一棵子树，必须明确区分它是左子树还是右子树，因为两者将构成不同形态的二叉树。因此，二叉树不是树的特例。它们是两种不同的数据结构。 二叉树有5种基本形态： (a) (b) (c)

树和二叉树：纸质作业

一、已知二叉树T逻辑结构如下图所示，请分别用顺序存储和二叉链表存储法表示此树。

二、将下面的森林F=﹛T1，T2，T3﹜转换为对应的二叉树，并写出相应二叉树的先根遍历序列。

三、将下列由三棵树组成的森林转换为二叉树，并写出相应二叉树的中根遍历序列

B A C D E F K H L G I J M N O P 四、已知树T的孩子链表存储结构如图所示，试画出此树逻辑结构，以及此树转换成的二叉树逻辑结构，并写出二叉树的后根遍历序列

五、设一棵二叉树的先序序列为：A B D F C E G H 中序遍历序列为： B F D A G E H C （1）画出这棵二叉树。

（2）将这棵二叉树转换成对应的树（或森林）。 六、给定集合{15,3,14,2,6,9,16,17}

（1）构造相应的huffman树（规定：二叉树中两个结点，权值小的结点居左） （2）计算它的带权路径长度

（3）写出它的huffman编码：（规定：左子树编码为0，右子树编码为1,左小右大） 七、假设通信电文使用的字符集为{a,b,c,d,e,f}，各字符在电文中出现的频度分别为：0.34，0.05，0.12，0.23，0.08，0.18，试为这6个