第六章树及二叉树
一、判断题
1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1
个非空指针域。（）
2.二叉树中每个结点的两棵子树的高度差等于1。（）
3.二叉树中每个结点的两棵子树是有序的。（）
4.二叉树中每个结点有两棵非空子树或有两棵空子树。（）
5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关
键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。（）
6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（）
7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。（）
8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i
—1个结点。（）
9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针
区域中有n+1个为空指针。（）
10.具有12个结点的完全二叉树有5个度为2的结点。（）
11、哈夫曼树中没有度为1的结点，所以必为满二叉树。（）
12、在哈夫曼树中，权值最小的结点离根结点最近。（）
13、线索二叉树是一种逻辑结构。（）
14、深度为K的完全二叉树至少有2K-1个结点。（）
15、具有n个结点的满二叉树，其叶结点的个数为（n+1）/2。（）
16、前序和中序遍历用线索树方式存储的二叉树，不必使用栈。（）
17、哈夫曼树是带权路径长度最短的树，路径上权值较大的点离根较远（）。
18、在二叉树结点的先序序列和后序序列中，所有叶子结点的先后顺序完全相同。
（）
19、二叉树的遍历操作实际上是将非线性结构线性化的过程。（）
20、树的先根遍历序列与其所转化的二叉树的先序遍历序列相同。（）
21、树的后根遍历序列与其所转化的二叉树的后序遍历序列相同。（）
二、填空
1．由3个结点所构成的二叉树有种形态。
2. 线索二元树的左线索指向其 _，右线索指向其 _。3．一棵具有257个结点的完全二叉树，它的深度为。
4、如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总
结点数为。
5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，
有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。
6. 一棵含有n个结点的k叉树，可能达到的最大深度为，最小深度为。
7. 若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后
序序列是。
8. 具有256个结点的完全二叉树的深度为_ 。
9. 在二叉树中，指针p所指结点为叶子结点的条件是_ 。
10、N个结点的二叉树采用二叉链表存放，共有空链域个数为n+1
11、深度为6（根层次为1）的二叉树至多有个结点。
12、平衡二叉树中某一结点左子树的深度减去右子树的深度称为该结点的。
三、选择题
1．某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、
F、G、E，则其左子树中结点数目为（）
A、3
B、2
C、4
D、5
2．二叉树是非线性数据结构，所以（）。
A、不能用顺序存储结构存储
B、不能用链式存储结构存储
C、顺序和链式存储结构都能存储
D、顺序和链式存储结构都不能使用
3.具有n(n>0)个结点的完全二叉树的深度为（）。
A、?log
2(n)? B、? log
2
(n)? C、? log
2
(n) ?+1 D、?log
2
(n)+1?
4．把一棵树转换为二叉树后，这棵二叉树的形态是（）。
A、唯一的
B、有多种
C、有多种，但根结点都没有左孩子
D、有多种，但根结点都没有右孩子
5.下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点
序列按其关键字有序（）。
A、二叉排序树
B、哈夫曼树
C、AVL树
D、堆
6、线索二叉树是一种（ C ）结构。
A．逻辑 B．逻辑和存储 C．物理 D．线性
7、将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对
结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为（）
A、98
B、99
C、50
D、48
8、设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和
M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。
A、M1
B、M1+M2
C、M3
D、M2+M3
9、将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对
结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为（）
A、48
B、49
C、50
D、51
10、引入二叉线索树的目的是（）
A、加快查找结点的前驱或后继的速度 C、为了能方便的找到双亲
B、为了能在二叉树中方便的进行插入与删除 D、使二叉树的遍历结果唯一11．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）
A．9 B．11 C．15
D．不确定
12．一棵树高为K的完全二叉树至少有（）个结点
A．2k–1 B. 2k-1–1 C.
2k-1 D. 2k
13．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。
A．M1 B．M1+M2 C．M3
D．M2+M3
14．一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）A．CABDEFG B．ABCDEFG C．DACEFBG
D．ADCFEG
15. 有关二叉树下列说法正确的是（）
A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2
16. 一个具有1025个结点的二叉树的高h为（）
A．11 B．10 C．11至1025之间 D．10至1024之间
17．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有（）结点
A．2h B．2h-1 C．2h+1 D．h+1 18．对于有n 个结点的二叉树, 其高度为（）
A．nlog
2n B．log
2
n C．log
2
n|+1 D．不确定
19. 一棵具有 n个结点的完全二叉树的树高度（深度）是（）
A．logn+1 B．logn+1 C．logn D．logn-1
20. 已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前
序遍历是（）。
A．acbed B．decab C．deabc D．cedba 21．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（）遍历方法最合适。
A．前序 B．中序C．后序 D．按层次
22．在下列存储形式中，（）不是树的存储形式。
A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法23．在下列关于二叉树的叙述中，正确的是（）
①只有一个结点的二叉树度为0; ②二叉树的度为2；③二叉树的左右子树
可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A．①②③ B．②③④ C．②④ D．①④
24．若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为（）
A.X的双亲
B.X的右子树中最左的结点
C.X的左子树中最右结点
D.X的左子树中最右叶结点
25．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）
A．都不相同 C．先序和中序相同，而与后序不同
B．完全相同 D．中序和后序相同，而与先序不同
26在线索化二叉树中，t所指结点没有右子树的充要条件是（）。
A、t->Rtag==1
B、t->Rchild==NULL
C、t->Rtag==1且t->Rchild==NULL
D、以上都不对
27、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含
的结点数至少为（）。
A．2h B．2h-1
C．2h+1 D．h+1
28、如右图所示二叉树的中序遍历序列是（）。
A．abcdgef B．dfebagc
C．dbaefcg D．defbagc
29、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，
它的先序遍历序列是（）。
A．cedba B．cdbae C．cabed D．cabde 30、设a和b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是（）。
A．a是b的左孩子 B．b是a的右孩子
C．a是b左子树上结点或b是a右子树上结点 D．以上三项均可
31、假定在一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结
点数为（）个。
A．45 B．15 C．16 D．31
32、某二叉树的先序遍历序列是abdgcefh，中序遍历序列是dgbaechf，则其后
序遍历序列是（）。
A．gdbehfca B．abcdefgh C．gdbaefch D．ghbcdefa
33、树的基本遍历策略可分为先根遍历和后根遍历；二叉树的遍历策略分为先序、
中序和后序遍历。这里把由树转化得到的二叉树叫做这棵树对应的二叉树。
以下结论（）是正确的。
A．树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B．树的后根遍历序列与其对应的二叉树的后序遍历序列相同
C．树的先根遍历序列与其对应的二叉树的中序遍历序列相同
D．以上都不对
34、如下图所示的4棵二叉树，（）不是完全二叉树。
35、设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫
曼树中总共有（）个空指针域。
A．2m-1 B．2m C．2m+1 D．4m
36、二叉树的第k层的结点数最多为（）
A．2k-1 B．2K+1 C．2K-1 D．2K-1
37、设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。
A．9 B．10 C．11 D．12
38、一棵有n个结点的树，在把它转换成对应的二叉树后，该二叉树根结点的左
子树上共有（）个结点。
A．n-2 B．n-1 C．n+1 D．n+2
39、对于一棵深度为4的三叉树，最多有（）个结点。
A．30 B．36 C．40 D．54
40、按照二叉树的定义，具有3个结点的二叉树有（）种。
A．2 B．3 C．4 D．5
四、简答题
1.已知二叉树的前序遍历序列是：D，A，C，E，B，H，F，G，I；中序遍历序列
是：D，C，B，E，H，A，G，I，F，试画出二叉树B。
2、已知一棵二叉树，其中序序列DBCAFGE，后序序列DCBGFEA，构造该二叉树。
3、给定权值{8，12，4，5，26，16，9}，构造一棵带权路径长度最短的二叉树，
并计算其带权路径长度。
4. 把如图所示的树转化成二叉树。
5、画出和下列二叉树相应的森林。
6、假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为
0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计
哈夫曼编码。
五、算法设计题
1.编写算法，计算二叉树中叶子结点的数目。
2.写出求二叉树深度的算法
3、已知一棵二叉树按顺序方式存储在数组A[1..n]中。设计算法，求出下标分别为i和j的两个结点的最近的公共祖先结点的值。
4.编写按层次顺序（同一层自左至右）遍历二叉树的算法。
5.编写算法判别给定二叉树是否为完全二叉树。
6、试设计算法计算一棵给定二叉树上所有结点数目。假设二叉树的存储结构描述如下：
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild;*rchild; /*左右孩子指针*/ }BiTNode,*BiTree；
7、计算二叉树上单分支结点数目。假设二叉树的存储结构描述如下：
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild;*rchild; /*左右孩子指针*/
} BiTNode,*BiTree；
8、利用栈的基本操作写出先序遍历二叉树的非递归算法
第6章树和二叉树作业 1、假设在树中，结点x是结点y的双亲时，用(x,y)来表示树边。已知一棵树的树边集合为{ (e,i), (b,e), (b,d), (a,b), (g,j), (c,g), (c,f), (h,l), (c,h), (a,c) } ，用树型表示法表示该树，并回答下列问题： ①哪个是根结点? 哪些是叶子结点? 哪个是g的双亲? 哪些是g的祖先? 哪些是g的孩子? 那些是e的子孙? 哪些是e的兄弟? 哪些是f 的兄弟? ②b和n的层次各是多少? 树的深度是多少? 以结点c为根的子树的深度是多少? 2、一棵深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对全部结点编号，问： ①各层的结点数是多少? ②编号为i的结点的双亲结点(若存在)的编号是多少? ③编号为i的结点的第j个孩子结点(若存在)的编号是多少? ④编号为i的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少? 3、设有如图6-27所示的二叉树。 ①分别用顺序存储方法和链接存储方法画 出该二叉树的存储结构。 ②写出该二叉树的先序、中序、后序遍历序 列。 4、已知一棵二叉树的先序遍历序列和中序遍 历序列分别为ABDGHCEFI和 GDHBAECIF，请画出这棵二叉树，然后给 出该树的后序遍历序列。
5、设一棵二叉树的中序遍历序列和后序遍历序列分别为BDCEAFHG 和DECBHGFA ，请画出这棵二叉树，然后给出该树的先序序列。 6、已知一棵二叉树的中序遍历序列和后序遍历序列分别为dgbaekchif 和gdbkeihfca，请画出这棵二叉树对应的中序线索树和后序线索树。 7、以二叉链表为存储结构，请分别写出求二叉树的结点总数及叶子结点总数的算法。 8、设图6-27所示的二叉树是森林F所对应的二叉树，请画出森林F。 9、设有一棵树，如图6-28 所示。 ①请分别用双亲表示法、孩 子表示法、孩子兄弟表示法 给出该树的存储结构。 ②请给出该树的先序遍历 序列和后序遍历序列。 ③请将这棵树转换成二叉 树。 10、设给定权值集合 w={3,5,7,8,11,12} ，请构造 关于w的一棵huffman树，并求其加权路径长度WPL 。 11、假设用于通信的电文是由字符集{a, b, c, d, e, f, g, h}中的字符构成，这8个字符在电文中出现的概率分别为{0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10} 。 ①请画出对应的huffman树(按左子树根结点的权小于等于右子树根结点的权的次序构造)。 ②求出每个字符的huffman编码。
二叉树的基本操作实现及其应用 一、实验目的 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<<"二叉树初始化成功!"<
//二叉树的基本操作 #include 树作业（一） 【作业要求】 1.提交文档，写出答案 2.如果有需要绘图，可以手绘拍照节省时间 【题目说明】 1 单项选择题 1. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法_B_。 A. 正确 B. 错误 2. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 B 个。 A．15 B．16C．17D．47 3. 按照二叉树的定义，具有3个结点的不同形状的二叉树有__C__种。 A. 3 B. 4 C. 5 D. 6 4. 按照二叉树的定义，具有3个不同数据结点的不同的二叉树有__C__种。 A. 5 B. 6 C. 30 D. 32 5. 深度为5的二叉树至多有__C__个结点。 A. 16 B. 32 C. 31 D. 10 6. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_ _B__。 A. 2h B. 2h-1 C. 2h+1 D. h+1 7. 对一个满二叉树，m个树叶，n个结点，深度为h，则__D__ 。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h-1 8. 如图1所示的4棵二叉树，__C__不是完全二叉树。 (A) (B) (C) (D) 图1 9. 树最适合用来表示__C__。 A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 2 填空题 1. 举例说明树和二叉树的两个主要差别_树的节点的最大度数没有限制，但是二叉树的节点的最大度数为2___、__树中节点的子节点没有顺序之分，但是二叉树中节点的子节点分左孩子、右孩子__。 2. 一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如下图所示，请画出该二叉树的形态。 123456789101112131415161718192021 e a f d g c j l h b 一棵二叉树的顺序存储数组t 3. 深度为k的完全二叉树至少有__2k?1__个结点。至多有__2k?1__个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是__2k?2+1__。 4、已知一棵完全二叉树的第6层（设根是第1层）有8个叶结点，则该完全二叉树的结点个数最多是多少？ 实验三二叉树的基本运算 一、实验目的 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 树 (树根结点的高度为1) 一、选择题 3．以下说法错误的是( )。 A．完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达B．在三叉链表上，二叉树的求双亲操作很容易实现 C．在二叉链表上，求根以及求左、右孩子等操作很容易实现 D．在二叉链表上，求双亲操作的时间性能很好 4．以下说法错误的是( )。 A．一般在哈夫曼树中，权值越大的叶子离根结点越近 B．哈夫曼树中没有度数为1的分支结点 C．若初始森林中共有n棵二叉树，最终求得的哈夫曼树共有2n-1个结点D．若初始森林中共有n棵二叉树， 进行2n-1次合并后才能剩下一棵最终的哈夫曼树 5．深度为6的二叉树最多有( )个结点。 A．64 B．63 C．32 D．31 6．将含有41个结点的完全二叉树从根结点开始编号，根为1号， 后面按从上到下、从左到右的顺序对结点编号， 那么编号为21的双亲结点编号为( )。 A．10B．11 C．41 D．20 7．设深度为k的二叉树上只有度为0和度为2的结点， 则这类二叉树上所含结点总数最少( )个。 A．k+l B．2k C．2k-1D．2k+1 8．下列说法中正确的是( )。 A．任何一棵二叉树中至少有一个结点的度为2 B．任何一棵二叉树中每个结点的度都为2 C．任何一棵二叉树中的每个结点的度肯定等于2 D．任何一棵二叉树中的每个结点的度都可以小于2 9．一棵二叉树满足下列条件：对任意结点，若存在左、右子树， 则其值都小于它的左子树上所有结点的值， 而大于右子树上所有结点的值。 现采用( )遍历方式就可以得到这棵二叉树所有结点的递减序列。A．前序B．中序C．后序D．层次 10．如图6-1所示的二叉树的中序遍历序列是( )。 A．abcdgef B．dfebagc C．dbaefcg D．defbagc 数据结构二叉树基本操作 (1). // 对二叉树的基本操作的类模板封装 //------------------------------------------------------------------------------------------------------------------------ #include 第六章树和二叉树 1 一、选择题 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 2. 在下述结论中，正确的是（） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③B．②③④C．②④D．①④ 3. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（） A．5 B．6 C．7 D．8 4. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（） A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定 5. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（） A．9 B．11 C．15 D．不确定 6. 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。 A．M1 B．M1+M2 C．M3 D．M2+M3 7.有关二叉树下列说法正确的是（） A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 8. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。 A．250 B．500 C．254 D．505 E．以上答案都不对 9. 具有10个叶结点的二叉树中有（）个度为2的结点。 A．8 B．9 C．10 D．ll 10. 深度为h的满m叉树的第k层有（）个结点。(1= 实验六：二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。 二、问题描述 首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：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，失败。 习题6树和二叉树 说明： 本文档中，凡红色字标出的题请提交纸质作业，只写题号和答案即可。 6.1单项选择题 1. 由于二叉树屮每个结点的度最大为2,所以二叉树是一种特殊的树，这种说法_B_。 A. 正确 B.错误 2. 假定在一棵二叉树屮，双分支结点数为15,单分支结点数为30个，则叶子结点数为 B_个。 A. 15 B. 16 C. 17 D. 47 3. 按照二叉树的定义，具有3个结点的不同形状的二叉树有_C_种。 A. 3 B.4 C. 5 D. 6 4. 按照二叉树的定义，具有3个不同数据结点的不同的二叉树有_C_种。 A.5 B.6 C. 30 D. 32 5. 深度为5的二叉树至多有_C_个结点。 A. 16 B. 32 C. 31 D. 10 6. 设高度为h 的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点 数至少为 B 。 A. 2h B. 2h-l C. 2h+l D. h+l 7. 对一个满二叉树，m 个树叶，n 个结点，深度为h,则_A_。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h -l 8. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序_A_。 A.不发生改变 B.发生改变 C.不能确定 D.以上都不对 9. 如杲某二叉树的前根次序遍历结果为stuwv,中序遍历为uwtvs,那么该二叉树的后 序为_C_。 A. uwvts B. vwuts C. wuvts D. wutsv 10. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法_A_。 A.正确 B.错误 11. 某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是 dgbaechf,则其后序遍历的结点访问顺序是_D_。 A. bdgcefha B. gdbecfha 12. 在一非空二叉树的中序遍历序列中, A.只有右子树上的所有结点 13. 如图6.1所示二叉树的中序遍历序列是_B_。 14. 一棵二叉树如图6.2所示，其中序遍历的序列为 B 。 A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh C. bdgaechf D. gdbehfca 根结点的右边_A_。 B.只有右子树上的部分结点 C.只有左子树上的部分结点 D.只有左子树上的所有结点 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 图6」 浙江大学城市学院实验报告 课程名称数据结构 实验项目名称实验十二叉树的基本操作 学生姓名专业班级学号 实验成绩指导老师（签名）日期 一.实验目的和要求 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 作业-树和二叉树 树 (树根结点的高度为1) 一、选择题 3．以下说法错误的是( )。 A．完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 B．在三叉链表上，二叉树的求双亲操作很容易实现 C．在二叉链表上，求根以及求左、右孩子等操作很容易实现 D．在二叉链表上，求双亲操作的时间性能很好4．以下说法错误的是( )。 A．一般在哈夫曼树中，权值越大的叶子离根结点越近 B．哈夫曼树中没有度数为1的分支结点C．若初始森林中共有n棵二叉树，最终求得的哈夫曼树共有2n-1个结点 D．若初始森林中共有n棵二叉树， 进行2n-1次合并后才能剩下一棵最终的哈夫曼树 5．深度为6的二叉树最多有( )个结点。A．64 B．63 C．32 D．31 6．将含有41个结点的完全二叉树从根结点开始编号，根为1号， 后面按从上到下、从左到右的顺序对结点编号，那么编号为21的双亲结点编号为( )。 A．10B．11 C．41 D．20 7．设深度为k的二叉树上只有度为0和度为2的结点， 则这类二叉树上所含结点总数最少( )个。A．k+l B．2k C．2k-1D．2k+1 8．下列说法中正确的是( )。 A．任何一棵二叉树中至少有一个结点的度为2 B．任何一棵二叉树中每个结点的度都为2 C．任何一棵二叉树中的每个结点的度肯定等于2 D．任何一棵二叉树中的每个结点的度都可以小于2 9．一棵二叉树满足下列条件：对任意结点，若存在左、右子树， 则其值都小于它的左子树上所有结点的值， 而大于右子树上所有结点的值。 现采用( )遍历方式就可以得到这棵二叉树所有结点的递减序列。 A．前序B．中序C．后序D．层次 10．如图6-1所示的二叉树的中序遍历序列是( )。 A．abcdgef B．dfebagc C．dbaefcg D．defbagc 11．已知某二叉树的后序遍历序列是deacb，中序遍历序列是deabc， 它的前序遍历序列是( )。 A．acbed B．baedc C．dceab D．cedba 12．某二叉树的前序遍历的结点访问顺序是abdgcefh， 中序遍历的结点访问顺序是dgbaechf， 则其后序遍历的结点访问顺序是( )。 二叉树的基本操作及实现 二叉树的基本操作及实现的代码如下： #include 数据结构程序报告（3） 2011.3.29 2. 需求分析： （1）功能：表达式可以用二叉树表示，对于简单的四则运算，请实现以下功能 【1】对于任意给出的前缀表达式（不带括号）、中缀表达式（可以带括号）或后缀表达式（不带括号），能够在计算机内部构造出一棵表达式二叉树，并且图示出来（图形的形式）。【2】对于构造好的内部表达式二叉树，按照用户的要求输出相应的前缀表达式（不带括号）、中缀表达式（可以带括号，但不允许冗余括）或后缀表达式（不带括号）。 提示：所谓中缀表达式中的冗余括号，就是去掉括号后不影响表达式的计算顺序。例如：“（c+b）+a”中的括号是冗余的，可以表示成不冗余的“c+b+a”。 （2）输入输出要求：请输入字符串表达式： 树形二叉树（图形显示） 中缀表达式为： 前缀表达式为： 后缀表达式为： 3.概要设计：（算法） 分成两部分完成： 【1】前缀、中缀、后缀表达式->二叉树表达式 前缀表达式->二叉树表达式：（a）碰到操作数则把其值赋给相应的新申请的二叉树结点，地址压栈；（b）碰到操作符则把其值赋给相应的新申请的二叉树，并从栈中弹出两个地址，分别作为其右指针和左指针，然后再把其地址压栈，最后一个地址即为二叉树的根结点地址。 中缀表达式->二叉树表达式：把中缀表达式转换成后缀表达式，然后再建立二叉树。 后缀表达式->二叉树表达式：（a）碰到操作数则把其值赋给相应的新申请的二叉树结点，若栈为空则地址压栈，若非空则取栈顶元素，若栈顶元素的左孩子为空则当前结点设为其左孩子，左孩子为满则设为其右孩子再压栈；（b）碰到操作数则把其值赋给相应的新申请的二叉树结点，取栈顶元素，若栈顶元素的左孩子为空则设为其左孩子，左孩子为满则设为其右孩子开始那个元素地址为根结点地址，开始时用变量root保存。 【1】二叉树表达式->前缀、中缀、后缀表达式 二叉树表达式->前缀表达式：对二叉树表达式进行前序遍历。 二叉树表达式->中缀表达式：对二叉树表达式进行中序遍历，若结点操作符的优先级高于其左或右子树，在打印相应的子树之前先打印开括号，在打印相应的子树最后在打印一个闭括号。 二叉树表达式->后缀表达式：对二叉树表达式进行后序遍历。 创作编号： GB8878185555334563BT9125XW 创作者：凤呜大王* //二叉树的基本操作 #include cout<<"--------------请选择------------"< 二叉树的创建与遍历 一、实验目的 1．学会实现二叉树结点结构和对二叉树的基本操作。 2．掌握对二叉树每种操作的具体实现，学会利用递归和非递归方法编写对二叉树这种递归数据结构进行处理的算法。 二、实验要求 1．认真阅读和掌握和本实验相关的教材内容。 2．编写完整程序完成下面的实验内容并上机运行。 3．整理并上交实验报告。 三、实验内容 1．编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归和非递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历。 四、实验步骤 源程序代码1 #include 实验五-二叉树基本操作的编程实现实验报告 ————————————————————————————————作者：————————————————————————————————日期： 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,树和二叉树作业(一)
二叉树的基本操作实验
作业-树和二叉树
数据结构——二叉树基本操作源代码
第6章 树和二叉树_作业(1)
数据结构实验二叉树
数据结构实验三——二叉树基本操作及运算实验报告
习题6树和二叉树.docx
实验10 二叉树的基本操作
二叉树基本操作经典实例
作业-树和二叉树
二叉树的基本操作及实现.cpp
表达式用二叉树表示
二叉树的基本 操作
C++二叉树的创建与遍历实验报告
实验五-二叉树基本操作的编程实现实验分析报告
相关主题
文本预览