当前位置：文档之家 › 数据结构-第6章 树和二叉树---4. 树和森林(V1)

数据结构-第6章 树和二叉树---4. 树和森林(V1)

  • 格式：pptx
  • 大小：139.84 KB
  • 文档页数：22

下载文档原格式

  / 22

合集下载

数据结构各章概要

数据结构各章概要

数据结构各章概要数据结构是计算机科学中非常重要的一个学科，其主要研究各种数据的组织方式和操作方法。

善于运用合适的数据结构可以提高算法的效率，并优化程序的性能。

本文将对数据结构的各个章节进行概要介绍，帮助读者了解不同章节的主要内容和应用。

第一章：引论在引论章节，我们将引入数据结构的基本概念和术语，例如什么是数据、数据项、数据对象等等。

同时，还将介绍数据结构的分类和基本操作，如搜索、遍历、插入、删除和排序。

这些基础知识是后续章节的基础。

第二章：线性表线性表是数据结构中最简单、最基本的一种结构。

其特点是数据元素之间的前驱和后继关系非常明确。

线性表可以用数组和链表两种方式实现。

在本章节中，我们将分别介绍顺序表和链表的实现原理、插入、删除、合并以及应用场景。

第三章：栈和队列栈和队列是两种特殊的线性表结构，它们对数据的访问具有限制性。

栈具有“先进后出”的特点，而队列则具有“先进先出”的特点。

在本章节中，我们将介绍栈和队列的实现方式以及常见的应用场景，如递归、表达式求值、广度优先搜索等。

第四章：串串是由零个或多个字符组成的有限序列，其长度可以为零。

在本章节中，我们将介绍串的定义和操作，包括字符串的模式匹配、模式识别和编辑操作。

串的相关算法在文本处理、计算机网络等领域具有广泛的应用。

第五章：数组和广义表数组是一种在内存中以连续方式存储的数据结构，它具有高效的随机访问特性。

广义表是线性表的一种扩展，可以包含表结构、原子结构以及其他广义表。

本章节将介绍数组和广义表的定义、操作和应用。

第六章：树树是一种非线性的数据结构，具有分层次、递归和层次遍历等特点。

在本章节中，我们将介绍树的基本概念、二叉树、树的遍历算法、平衡树以及树的应用，如编译器中的语法树、文件系统的目录结构等。

第七章：图图是一种复杂的非线性数据结构，由顶点集合和边集合组成。

在本章节中，我们将介绍图的各种表示方式，图的遍历算法、最短路径算法以及常用的图算法，如最小生成树算法和拓扑排序。

《数据结构与算法》第六章-树与二叉树习题

《数据结构与算法》第六章-树与二叉树习题

《数据结构与算法》第二部分习题精选一、下面是有关二叉树的叙述，请判断正误（）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的结点。

二、填空1．由３个结点所构成的二叉树有种形态。

2. 一棵深度为6的满二叉树有个分支结点和个叶子。

3．一棵具有２５７个结点的完全二叉树，它的深度为。

4.设一棵完全二叉树有700个结点，则共有个叶子结点。

5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。

6.一棵含有n个结点的k叉树，可能达到的最大深度为，最小深度为。

7. 二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。

因而二叉树的遍历次序有六种。

最常用的是三种：前序法（即按N L R次序），后序法（即按次序）和中序法（也称对称序法，即按L N R次序）。

这三种方法相互之间有关联。

若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是。

8.中序遍历的递归算法平均空间复杂度为。

9.用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是。

第6章_数据结构习题题目及答案_树和二叉树_参考答案

第6章_数据结构习题题目及答案_树和二叉树_参考答案

一、基础知识题6.1设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，求树T中的叶子数。

【解答】设度为m的树中度为0,1,2,…,m的结点数分别为n0, n1, n2,…, nm，结点总数为n，分枝数为B，则下面二式成立n= n0+n1+n2+…+nm (1)n=B+1= n1+2n2 +…+mnm+1 (2)由(1)和(2)得叶子结点数n0=1+即： n0=1+(1-1)*4+(2-1)*2+(3-1)*1+(4-1)*1=86.2一棵完全二叉树上有1001个结点，求叶子结点的个数。

【解答】因为在任意二叉树中度为2 的结点数n2和叶子结点数n0有如下关系：n2=n0-1,所以设二叉树的结点数为n, 度为1的结点数为n1，则n= n0+ n1+ n2n=2n0+n1-11002=2n0+n1由于在完全二叉树中，度为1的结点数n1至多为1，叶子数n0是整数。

本题中度为1的结点数n1只能是0，故叶子结点的个数n0为501.注：解本题时要使用以上公式，不要先判断完全二叉树高10，前9层是满二叉树，第10层都是叶子，……。

虽然解法也对，但步骤多且复杂，极易出错。

6.3 一棵124个叶结点的完全二叉树，最多有多少个结点。

【解答】由公式n=2n0+n1-1,当n1为1时，结点数达到最多248个。

6.4．一棵完全二叉树有500个结点，请问该完全二叉树有多少个叶子结点？有多少个度为1的结点？有多少个度为2的结点？如果完全二叉树有501个结点，结果如何？请写出推导过程。

【解答】由公式n=2n0+n1-1，带入具体数得，500=2n0+n1-1，叶子数是整数，度为1的结点数只能为1，故叶子数为250，度为2的结点数是249。

若完全二叉树有501个结点，则叶子数251，度为2的结点数是250，度为1的结点数为0。

6.5 某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数是多少。

数据结构习题第六章树和二叉树

数据结构习题第六章树和二叉树

第六章 树和二叉树一、选择题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 3. 设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是（ ） 【南京理工大学1999 一、20（2分）】 A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G 4. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T 中的叶子数为（ ）A ．5B ．6C ．7D ．8【南京理工大学 2000 一、8 （1.5分）】5. 在下述结论中，正确的是（ ）【南京理工大学 1999 一、4 （1分）】①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A ．①②③B ．②③④C ．②④D ．①④6. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是（ ）A ．m-nB ．m-n-1C ．n+1D ．条件不足，无法确定 【南京理工大学2000一、17（1.5分）】7. 树是结点的有限集合，它（ (1）)根结点，记为T 。

其余结点分成为m （m>0）个(（2）)的集合T1，T2， …，Ｔm ，每个集合又都是树，此时结点T 称为Ti 的父结点，Ti 称为T的子结点（1≤i ≤m ）。

云大《数据结构》课程教学课件-第6章 树和二叉树(147P)_OK

云大《数据结构》课程教学课件-第6章 树和二叉树(147P)_OK


^d ^ ^ e ^ 三叉链表
3）二叉链表是二叉树最常用的存储结构。还有其它链接方 法，采用何种方法，主要取决于所要实施的各种运算频度。
例:若经常要在二叉树中寻找某结点的双亲时，可在每个结 点上再加一个指向其双亲的指针域parent，称为三叉链表。
lchild data parent rchild
2021/8/16
2021/8/16
9
6.2 二 叉 树
6.2.1 二叉树的概念
一、二叉树的定义： 二叉树(Binary Tree)是n(n>=0)个结点的有限集，它或者是 空集(n=0)或者由一个根结点和两棵互不相交的，分别称 为根的左子树和右子树的二叉树组成。 可以看出，二叉树的定义和树的定义一样，均为递归定 义。
A
集合3
集合1
BCD
EF
G
集合2
2021/8/16
3
2、树的表示方法 1）树形图法
A
BCD
EF
G
2）嵌套集合法
3）广义表形式 ( A(B, C(E,F), D(G) )
4）凹入表示法
2021/8/16
A B
D
CG
EF
A B C E DF G
4
3、 树结构的基本术语
1）结点的度(Degree)：为该结点的子树的个数。 2）树的度：为该树中结点的最大度数。
7）路径(Path)：若树中存在一个结点序列k1,k2,…,kj,使得ki是 ki+1的双亲(1<=i<j)，则称该结点序列是从ki到kj一条路径 (Path)
路径长度：路径的长度为j-1,其为该路径所经过的边的数 目。
A
BCD
EF
G
《数据结构》习题集：第6章 树和二叉树

《数据结构》习题集：第6章 树和二叉树

第6章树和二叉树一、选择题1.有一“遗传”关系，设x是y的父亲，则x可以把它的属性遗传给y，表示该遗传关系最适合的数据结构是（ D ）A、向量B、树C、图D、二叉树2.树最适合用来表示（ B ）A、有序数据元素B、元素之间具有分支层次关系的数据C、无序数据元素D、元素之间无联系的数据3.树B 的层号表示为1a,2b,3d,3e,2c，对应于下面选择的（ C ）A、1a(2b(3d,3e),2c)B、a(b(D,e),c)C、a(b(d,e),c)D、a(b,d(e),c)4.对二叉树的结点从1 开始连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（ B ）次序的遍历实现二叉树的结点编号。

A、先序B、中序C、后序D、从根开始按层次遍历5.按照二叉树的定义，具有3 个结点的二叉树有（C ）种。

A、3B、4C、5D、66.在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1，度为0的结点数为n0，则树的最大高度为（），其叶结点数为（）；树的最小高度为（），其叶结点数为（）；若采用链表存储结构，则有（）个空链域。

log+1 C、log2n D、nA、n/2B、⎣⎦n2E、n0+n1+n2F、n1+n2G、n2+1H、1I、n+1 J、n1K、n2L、n1+17.对一棵满二叉树，m 个树叶，n 个结点，深度为h，则（ D ）A、n=m+hB、h+m=2nC、m=h-1D、n=2h-18.设高度为h 的二叉树中只有度为0 和度为2 的结点，则此类二叉树中所包含的结点数至少为（ A ），至多为（D ）。

A、2hB、2h-1C、2h-1D、2h-19.在一棵二叉树上第5 层的结点数最多为（B）（假设根结点的层数为1）A、8B、16C、15D、3210.深度为5 的二叉树至多有（ C ）个结点。

A、16B、32C、31D、1011.一棵有124 个叶结点的完全二叉树，最多有（B ）个结点A、247B、248C、249D、25012.含有129 个叶子结点的完全二叉树，最少有（ B ）个结点A、254B、255C、256D、25713.假定有一棵二叉树，双分支结点数为15，单分支结点数为30，则叶子结点数为（ D ）个。

数据结构第6章树和二叉树3树和森林ppt课件

数据结构第6章树和二叉树3树和森林ppt课件


§6.4 树和森林 ❖树的存储结构——孩子兄弟表示法
这种存储结构便于实现各种树的操作。首先易于 实现找结点孩子等的操作。如果为每个结点增设一个 (parent)域，则同样能方便地实现Parent(T, x)操作。
§6.4 树和森林
❖森林和二叉树的转换
1. 树和二叉树的对应关系 由于二叉树和树都可用二叉链表作为存储结构，
R AB C
DE
F
GHK
R^
A
^D
^B
^E ^
C^
F^
^G
^H
^K ^
§6.4 树和森林
❖树的二叉链表（孩子 - 兄弟）存储表示
typedef struct CSNode { Elem data; struct CSNode *firstchild , *nextsibling;
} CSNode, *CSTree;
A BC D E F GH
A BC D
E F GH A
BC D
1）在兄弟之间加一条连线； 2）对每个结点，除了左孩子外，去除其与其余孩子之间的联系； 3）以根结点为轴心，将整个树顺时针转45°。
Ia
A B
Ib
E F
d
C D
G H I
c E F G H I
§6.4 树和森林
❖森林和二叉树的转换
2. 森林和二叉树的对应关系 从树的二叉链表表示的定义可知，任何一棵
§6.4 树和森林
3
6^
5^
0
1
7
8
2^ 9^
R AB C
DE
F
GHK
§6.4 树和森林 ❖树的存储结构——孩子兄弟表示法
或称二叉树表示法，或称二叉链表表示法。即以 二叉链表作树的存储结构。链表中结点的两个链域分 别指向该结点的第一个孩子结点和下一个兄弟结点。
《数据结构——C语言描述》第6章：树

《数据结构——C语言描述》第6章：树

Void paintleaf (Btree root) { if (root!=NULL) { if (root ->Lchild==NULL && root ->Rchild==NULL) printf (root ->data); paintleaf (root ->Lchild); paintleaf (root -遍历左子树； （2）访问根结点； （3）中根遍历右子树。 后根遍历二叉树 （1）后根遍历左子树； （2）后根遍历右子树； （3）访问根结点。
先根遍历: -+a*b–cd/ef 中根遍历: a+b*c–d–e/f 后根遍历: abcd-*+ef/-
typedef struct Node { datatype data; struct Node *Lchild; struct Node *Rchild; } BTnode,*Btree;
满二叉树：一棵深度为k且有2k-1个结 点的二叉树称为满二叉树。 完全二叉树：深度为k，有n个结点的 二叉树当且仅当其每一个结点都与深度 为k的满二叉树中编号从1至n的结点一一 对应时，称为完全二叉树。
1 2 4 8 9 10 5 11 12 6 13 14 3 7 15 4 6 2
1 3 5 7
树的度：树中最大的结点的度数即为 树的度。图6.1中的树的度为3。 结点的层次(level)：从根结点算起， 根为第一层，它的孩子为第二层……。 若某结点在第l层，则其孩子结点就在 第l+1层。图6.1中，结点A的层次为1， 结点M的层次为4。 树的高度(depth)：树中结点的最大层 次数。图6.1中的树的高度为4。 森林(forest)：m(m≥0)棵互不相交的 树的集合。
数据结构与算法第六章课后答案第六章 树和二叉树

数据结构与算法第六章课后答案第六章 树和二叉树

第6章 树和二叉树（参考答案）6.1(1)根结点a6.2三个结点的树的形态： 三个结点的二叉树的形态：（1） （1） （2） （4） （5）6．3 设树的结点数是n ，则n=n0+n1+n2+……+nm+ (1)设树的分支数为B ，有n=B+1n=1n1+2n2+……+mnm+1 (2)由（1）和（2）有：n0=n2+2n3+……+(m-1)nm+16.4(1) k i-1 (i 为层数)(2) (n-2)/k+1(3) (n-1)*k+i+1(4) (n-1)%k !=0; 其右兄弟的编号 n+16.5（1）顺序存储结构注：#为空结点6.6(1) 前序 ABDGCEFH(2) 中序 DGBAECHF(3) 后序 GDBEHFCA6.7(1) 空二叉树或任何结点均无左子树的非空二叉树(2) 空二叉树或任何结点均无右子树的非空二叉树(3) 空二叉树或只有根结点的二叉树6.8int height(bitree bt)// bt是以二叉链表为存储结构的二叉树，本算法求二叉树bt的高度{ int bl,br; // 局部变量，分别表示二叉树左、右子树的高度if (bt==null) return(0);else { bl=height(bt->lchild);br=height(bt->rchild);return(bl>br? bl+1: br+1); // 左右子树高度的大者加1（根） }}// 算法结束6.9void preorder(cbt[],int n,int i);// cbt是以完全二叉树形式存储的n个结点的二叉树，i是数// 组下标，初始调用时为1。

本算法以非递归形式前序遍历该二叉树{ int i=1,s[],top=0; // s是栈，栈中元素是二叉树结点在cbt中的序号 // top是栈顶指针，栈空时top=0if (n<=0) { printf(“输入错误”);exit（0）；}while (i<=n ||top>0){ while(i<=n){visit(cbt[i]); // 访问根结点if (2*i+1<=n) s[++top]=2*i+1; //若右子树非空，其编号进栈i=2*i;// 先序访问左子树}if (top>0) i=s[top--]; // 退栈，先序访问右子树} // END OF while (i<=n ||top>0)}// 算法结束//以下是非完全二叉树顺序存储时的递归遍历算法，“虚结点”用‘*’表示void preorder(bt[],int n,int i);// bt是以完全二叉树形式存储的一维数组，n是数组元素个数。

数据结构第六章树和二叉树习题及答案

数据结构第六章树和二叉树习题及答案

习题六树和二叉树一、单项选择题1．以下说法错误的是 ( )A．树形结构的特点是一个结点可以有多个直接前趋B．线性结构中的一个结点至多只有一个直接后继C．树形结构可以表达(组织)更复杂的数据D．树(及一切树形结构)是一种"分支层次"结构E．任何只含一个结点的集合是一棵树2．下列说法中正确的是 ( )A．任何一棵二叉树中至少有一个结点的度为2B．任何一棵二叉树中每个结点的度都为2C．任何一棵二叉树中的度肯定等于2D．任何一棵二叉树中的度可以小于23．讨论树、森林和二叉树的关系，目的是为了（）A．借助二叉树上的运算方法去实现对树的一些运算B．将树、森林按二叉树的存储方式进行存储C．将树、森林转换成二叉树D．体现一种技巧，没有什么实际意义4．树最适合用来表示 ( )A．有序数据元素 B．无序数据元素C．元素之间具有分支层次关系的数据 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+M37．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A． 250 B． 500 C．254 D．505 E．以上答案都不对8. 设给定权值总数有n 个，其哈夫曼树的结点总数为( )A．不确定 B．2n C．2n+1 D．2n-19．二叉树的第I层上最多含有结点数为（）A．2I B． 2I-1-1 C． 2I-1 D．2I -110．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A．2h B．2h-1 C．2h+1 D．h+111. 利用二叉链表存储树，则根结点的右指针是（）。

A．指向最左孩子 B．指向最右孩子 C．空 D．非空12．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。

第六章 树与二叉树

第六章 树与二叉树

44
森林的遍历
(4) 广度优先遍历(层次序 遍历) ：
数据结构
若森林F为空，返回； 否则 依次遍历各棵树的根 结点； 依次遍历各棵树根结 点的所有子女； 依次遍历这些子女结 森林的二叉树表示 点的子女结点。
45
二叉树的计数 由二叉树的前序序列和中序序列可唯 一地确定一棵二叉树。例, 前序序列 { ABHFDECKG } 和中序序列 { HBDFAEKCG }, 构造二叉树过程如 下：
三个结点构成的不同的二叉树
8
用二 叉 树 表达实际问题
例2 双人比赛的所有可能的结局
开始
甲
开局连赢两局 或五局三胜
乙
甲
甲 甲 乙
乙
乙 甲 乙 甲 甲 乙
甲
乙 甲
乙
乙
甲
乙甲
乙
甲
乙 甲 乙
二叉树的性质
数据结构
性质1 若二叉树的层次从1开始, 则在二叉树的 第 i 层最多有 2i －1个结点。(i 1) [证明用数学归纳法] 性质2 高度为k的二叉树最多有 2k-1个结点。 (k 0) [证明用求等比级数前k项和的公式]
前序遍历二叉树算法的框架是 若二叉树为空，则空操作； 否则 – 访问根结点 (V)； – 前序遍历左子树 (L)； – 前序遍历右子树 (R)。
遍历结果 -+a*b-cd/ef
27
数据结构
后序遍历 (Postorder Traversal)
后序遍历二叉树算法的框架是 若二叉树为空，则空操作； 否则 – 后序遍历左子树 (L)； – 后序遍历右子树 (R)； – 访问根结点 (V)。
数据结构
36
左子女-右兄弟表示法 第一种解决方案

数据结构课后习题答案第六章

(1) 前序遍历序列和中序遍历序列相同。 (2) 中序遍历序列和后序遍历序列相同。 (3) 前序遍历序列和后序遍历序列相同。
欢迎下载
6
-
9．已知信息为“ ABCD BCD CB DB ACB ”，请按此信息构造哈夫曼树，求出每一字符的最优编码。 10. 己知中序线索二叉树采用二叉链表存储结构，链结点的构造为：
_，双分支结点的个数为 ____， 3 分支结点的个数为 ____， C 结点的双亲结点为 ____ ，其孩子结点为 ____。
5. 一棵深度为 h 的满 k 叉树有如下性质：第 h 层上的结点都是叶子结点，其余各层上的每个结点都有
k 棵非空子树。
如果按层次顺序（同层自左至右）从 1 开始对全部结点编号，则：
7．二叉树的遍历分为 ____ ，树与森林的遍历包括 ____。 8．一棵二叉树的第 i(i>=1) 层最多有 ____ 个结点；一棵有 n(n>0) 个结点的满二叉树共有 ____ 个叶子和 ____个非终端结点。
9.在一棵二叉树中，假定双分支结点数为 5 个，单分支结点数为 6 个，则叶子结点为 ____个。
A. 逻辑 B．逻辑和存储 C．物理 D.线性 19.由权值分别是 8，7， 2， 5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为
A. 23 B. 37 C． 46 D. 43 20.设 T 是哈夫曼树，具有 5 个叶结点，树 T 的高度最高可以是 ( )。
A.2 B . 3 C. 4 D. 5
()
6．在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树。
()
7．由于二叉树中每个结点的度最大为 2，所以二叉树是一种特殊的树。 8．二叉树的前序遍历序列中，任意一个结点均处在其子树结点的前面。

数据结构zl-第6章树4-1


E K
有序树——结点各子树从左至右有序,不能互换 结点各子树从左至右有序, 有序树 结点各子树从左至右有序 左为第一) (左为第一) 无序树——结点各子树可互换位置. 结点各子树可互换位置. 无序树 结点各子树可互换位置
15
A
2.
若干术语
E K
B F L
C G H M
D I J
双亲——即上层的那个结点 直接前驱 即上层的那个结点(直接前驱 双亲 即上层的那个结点 直接前驱) 孩子——即下层结点的子树的根 直接后继 即下层结点的子树的根(直接后继 孩子 即下层结点的子树的根 直接后继) 兄弟——同一双亲下的同层结点(孩子之间互称兄弟) 同一双亲下的同层结点( 兄弟 同一双亲下的同层结点 孩子之间互称兄弟) 堂兄弟——即双亲位于同一层的结点(但并非同一双亲 即双亲位于同一层的结点( 堂兄弟 即双亲位于同一层的结点 ) 祖先——即从根到该结点所经分支的所有结点 祖先 即从根到该结点所经分支的所有结点 子孙——即该结点下层子树中的任一结点 子孙 即该结点下层子树中的任一结点
讨论3:树的链式存储方案应该怎样制定? 讨论 :树的链式存储方案应该怎样制定? 链式存储方案应该怎样制定
可用多重链表:一个前趋指针, 个后继指针. 可用多重链表:一个前趋指针,n个后继指针. 细节问题:树中结点的结构类型样式该如何设计? 细节问题:树中结点的结构类型样式该如何设计? 即应该设计成"等长"还是"不等长" 即应该设计成"等长"还是"不等长"? 缺点:等长结构太浪费(每个结点的度不一定相同); 缺点:等长结构太浪费(每个结点的度不一定相同); 不等长结构太复杂(要定义好多种结构类型). 不等长结构太复杂(要定义好多种结构类型). 解决思路:先研究最简单,最有规律的树,然后设法把一般 解决思路:先研究最简单,最有规律的树, 的树转化为简单树. 的树转化为简单树.

数据结构第6章树和二叉树

数据结构第6章树和⼆叉树第六章树和⼆叉树⼀、选择题1．已知⼀算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE2.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶⼦数为（）A．5 B．6 C．7 D．83.在下述结论中，正确的是（）①只有⼀个结点的⼆叉树的度为0; ②⼆叉树的度为2；③⼆叉树的左右⼦树可任意交换;④深度为K的完全⼆叉树的结点个数⼩于或等于深度相同的满⼆叉树。

A．①②③ B．②③④ C．②④ D．①④4.设森林F对应的⼆叉树为B，它有m个结点，B的根为p,p的右⼦树结点个数为n,森林F中第⼀棵树的结点个数是（）A．m-n B．m-n-1 C．n+1 D．条件不⾜，⽆法确定5．⼀棵完全⼆叉树上有1001个结点，其中叶⼦结点的个数是（）A．250 B． 254 C．500 D．5016.设给定权值总数有n 个，其哈夫曼树的结点总数为( )A．不确定 B．2n C．2n+1 D．2n-17.有关⼆叉树下列说法正确的是（）A．⼆叉树的度为2 B．⼀棵⼆叉树的度可以⼩于2 C．⼆叉树中⾄少有⼀个结点的度为2 D．⼆叉树中任何⼀个结点的度都为2 8．⼆叉树的第I层上最多含有结点数为（）A．2I B． 2I-1-1 C． 2I-1 D．2I -19.⼀个具有1025个结点的⼆叉树的⾼h为（）A．11 B．10 C．11⾄1025之间 D．10⾄1024之间10．⼀棵⼆叉树⾼度为h,所有结点的度或为0，或为2，则这棵⼆叉树最少有( )结点A．2h B．2h-1 C．2h+1 D．h+111.⼀棵具有 n个结点的完全⼆叉树的树⾼度（深度）是（）A．?log2n?+1 B．log2n+1 C．?log2n? D．log2n-112．深度为h的满m叉树的第k层有（）个结点。

数据结构详细教案——树与二叉树

数据结构教案第六章树与二叉树目录6.1树的定义和基本术语 (1)6.2二叉树 (2)6.2.1 二叉树的定义 (2)6.2.2 二叉树的性质 (4)6.2.3 二叉树的存储结构 (5)6.3树和森林 (6)6.4二叉树的先|中|后序遍历算法 (7)6.5先|后|中序遍历的应用扩展 (9)6.5.1 基于先序遍历的二叉树(二叉链)的创建 (9)6.5.2 统计二叉树中叶子结点的数目 (9)6.5.3 求二叉树的高度 (10)6.5.4 释放二叉树的所有结点空间 (11)6.5.5 删除并释放二叉树中以元素值为x的结点作为根的各子树 (12)6.5.6 求位于二叉树先序序列中第k个位置的结点的值 (12)6.5.7 线索二叉树 (13)6.5.8 树和森林的遍历 (14)6.6二叉树的层次遍历 (16)6.7判断一棵二叉树是否为完全二叉树 (16)6.8哈夫曼树及其应用 (18)6.8.1 最优二叉树(哈夫曼树) (18)6.8.2 哈夫曼编码 (19)6.9遍历二叉树的非递归算法 (19)6.9.1 先序非递归算法 (19)6.9.2 中序非递归算法 (20)6.9.3 后序非递归算法 (21)第6章二叉树和树6.1 树的定义和基本术语1、树的递归定义1）结点数n=0时，是空树2）结点数n>0时有且仅有一个根结点、m个互不相交的有限结点集——m棵子树2、基本术语结点：叶子(终端结点)、根、内部结点（非终端结点、分支结点）；树的规模：结点的度、树的度、结点的层次、树的高度(深度)结点间的关系：双亲(1)—孩子(m)，祖先—子孙，兄弟，堂兄弟兄弟间是否存在次序：无序树、有序树去掉根结点非空树森林引入一个根结点3、树的抽象数据类型定义树特有的操作：查找：双亲、最左的孩子、右兄弟结点的度不定，给出这两种操作可以查找到一个结点的全部孩子插入、删除：孩子遍历：存在一对多的关系，给出一种有规律的方法遍历(有且仅访问一次)树中的结点ADT Tree{数据对象：D={a i | a i∈ElemSet, i=1,2,…,n, n≥0}数据关系：若D为空集，则称为空树；若D仅含一个数据元素，则R为空集，否则R={H}，H是如下二元关系：(1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2) 若D-{root}≠Ф，则存在D-{root}的一个划分D1, D2, …, D m (m>0)（D i 表示构成第i棵子树的结点集），对任意j≠k (1≤j, k≤m) 有D j∩D k=Ф，且对任意的i (1≤i≤m)，唯一存在数据元素x i∈D i, 有<root,x i>∈H（H表示结点之间的父子关系）；(3) 对应于D-{root}的划分，H-{<root, x1>,…, <root, x m>}有唯一的一个划分H1, H2, …, H m(m>0)（H i表示第i棵子树中的父子关系），对任意j≠k(1≤j,k≤m)有H j∩H k=Ф，且对任意i(1≤i≤m)，H i是D i上的二元关系，(D i, {H i})是一棵符合本定义的树，称为根root的子树。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
ElemType data ; struct CSnode *firstchild, *nextsibing ; }CSNode;
6.4.1 树的存储结构
R AB C D EG F
R⋀
A
⋀D
⋀B
⋀E ⋀
C⋀
⋀G
⋀F ⋀
6.4.2 树、森林和二叉树的转换
1. 树转换为二叉树 将树转换成二叉树在“孩子兄弟表示法”中已 给出，其详细步骤是： ⑴ 加线。在树的所有相邻兄弟结点之间加一 条连线。 ⑵ 去连线。除最左的第一个子结点外，父结点 与所有其它子结点的连线都去掉。 ⑶ 旋转。将树以根结点为轴心，顺时针旋转 450，使之层次分明。
B C
D
A E
L HK
M
技巧：无左孩子 者即为叶子结点
6.4.3 树和森林的遍历
1. 树的遍历 由树结构的定义可知，树的遍历有二种方法。 ⑴ 先序遍历：先访问根结点，然后依次先序 遍历完每棵子树等。价于对应二叉树的先序遍历
⑵ 后序遍历：先依次后序遍历完每棵子树，然 后访问根结点。等价于对应二叉树的中序遍历
0 R -1 1A 0 2B 0 3C 0
}Ptree ; R
4D 1 5E 1
AB C
6F 3
7G 6
DE
F
8H 6
9I 6
G H I 10~MAX_Size-1 ... ...
6.4.1 树的存储结构
2. 孩子表示法
每个结点的孩子结点构成一个单链表，即有n 个结点就有n个孩子链表；
n个孩子的数据和n个孩子链表的头指针组成一 个顺序表； 结点结构定义： 顺序表定义：
typedef struct PTNode { ElemType data ;
int parent ;
}PTNode ;
6.4.1 树的存储结构
1. 双亲表示法
#define MAX_SIZE 100
typedef struct { PTNode Nodes[MAX_SIZE] ;
int num ; /* 结点数 */
6.4.1 树的存储结构
1. 双亲表示法 2. 孩子表示法 3. 孩子兄弟表示法
最常用
6.4.1 树的存储结构
1. 双亲表示法
用一组连续的存储空间来存储树的结点，同时 在每个结点中附加一个指示器(整数域) ，用以 指示双亲结点的位置(下标值) 。
结点的结构表示： 树的结点结构定义：
Data Parent
6.4.3 树和森林的遍历
先序遍历的次序是：ABCDEFGIJHK 后序遍历的次序是：CDBFIJGHEKA
A
B
E
K
C DF GH
IJ
6.4.3 树和森林的遍历
1. 森林的遍历 ⑴ 先序遍历：按先序遍历树的方式依次遍历F 中的每棵树。等价于树的先序遍历 (2) 中序遍历：按中序遍历树的方式依次遍历F 中的每棵树。等价于树的后序遍历
(C) 还原后的树
6.4.2 树、森林和二叉树的转换
树
R
AB C
DE
存储
对应关系
R A ⋀D ⋀
二叉树 R
A
DB
存储
EC
R⋀ A ⋀D ⋀
解释
B ⋀C⋀ ⋀E⋀
B ⋀E⋀ ⋀C ⋀
解释
R⋀
A
⋀D⋀ B ⋀E⋀ ⋀C⋀
练习
如图所示的二叉树BT是由森林T1转换而来的 二叉树，那么森林T1中有（5）叶子结点。
6.1 树的基本概念 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 哈夫曼树及其应用
6.4.1 树
树和二叉树的区别： （1）二叉树至多有两个子树，树则不然； （2）二叉树的子树有左右之分，而树的子树没 有次序； （3）二叉树允许树为空，树一般不允许为空（ 个别教材允许为空）
根结点的右子树，依次类推，则第一棵树的根结
点就是转换后生成的二叉树的根结点。
A
A
G
A
G
B
L
B
G
B C L KM
CH K
C
L
DH
D
MD
(b) 森林中每棵树
HK M
(a) 森林
对应的二叉树
(c) 森林对应的二叉树
6.4.2 树、森林和二叉树的转换
3. 二叉树转换为树或森林 其步骤是：
⑴ 加虚线。若某结点是其父结点的左孩子， 则将该结点的右孩子、右孩子的右孩子、...， 都与该结点的父结点加虚线相连，如图(a)所示 。
⑵ 去连线。去掉原二叉树中所有父结点与其 右孩子之间的连线，如图(b)所示。 ⑶ 规整化。将图中各结点按层次排列且将所 有的虚线变成实线，整理得到树或者森林，如 图(c)所示。
6.4.2 树、森林和二叉树的转换
R A DB EC
G F
(a) 加虚线后
R A DB EC
G F
(b) 去连线后
R AB C D EG F
6.4 树和森林Biblioteka 1、树的存储结构：孩子兄弟表示法（二 叉链表表示法）---掌握 2、树、森林和二叉树之间的转换：把树 的孩子兄弟表示法解释为二叉树的二叉 链表表示法。---掌握 3、树和森林的遍历。---理解
作业
已知一棵二叉树的先序遍历序列和中序遍历序 列分别为ABDEFCGH和DEBFAGCH， （1）请画出这棵二叉树； （2）给出该树的后序遍历序列； （3）画出这棵二叉树对应的中序线索树。 （4）将这棵二叉树转换为对应的森林
6.4.1 树的存储结构
3. 孩子兄弟表示法(二叉树表示法) 以二叉链表作为树的存储结构。 链表中每个结点有两个链域，分别指向第一个 孩子结点和下一个兄弟(右兄弟)结点。
firstchild data nextsibing
第一个孩子结点 下一个兄弟结点
6.4.1 树的存储结构
typedef struct CSnode {
6.4.2 树、森林和二叉树的转换
R AB C D EG F
(a) 一般的树
R AB C DEG F (b) 加虚线，去连线后
R A DB EC
G
F
(C) 转换后的二叉树
6.4.2 树、森林和二叉树的转换
2. 森林转化为二叉树
将F={T1, T2,⋯,Tn} 中的每棵树转换成二叉树。 按森林中树的次序，后一棵树作为前一棵树的
typedef struct PTNode #define N 6 /* 结点数 */
{ ElemType data ;
PTNode Nodes[N] ;
struct PTNode *next ;
}PTNode ;
6.4.1 树的存储结构
1
01
2
3
12
23
45
63 4
45
56
2
3∧
4
5∧
6∧
∧
∧
∧