当前位置：文档之家 › 数据结构第6章 树和二叉树4

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

  • 格式：ppt
  • 大小：1.66 MB
  • 文档页数：56

下载文档原格式

  / 56

合集下载

数据结构-6 树和二叉树

数据结构-6 树和二叉树

第六章树和二叉树一．选择题1. 以下说法错误的是。

A.树形结构的特点是一个结点可以有多个直接前趋B.线性结构中的一个结点至多只有一个直接后继C.树形结构可以表达(组织)更复杂的数据D.树(及一切树形结构)是一种"分支层次"结构2. 如图6-2所示的4 棵二叉树中，不是完全二叉树。

图6-2 4 棵二叉树3. 在线索化二叉树中，t 所指结点没有左子树的充要条件是。

A. t->left == NULLB. t->ltag==1C. t->ltag==1 且t->left==NULL D .以上都不对4. 以下说法错误的是。

A.二叉树可以是空集B.二叉树的任一结点最多有两棵子树C.二叉树不是一种树D.二叉树中任一结点的两棵子树有次序之分5. 以下说法错误的是。

A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达B.在三叉链表上，二叉树的求双亲运算很容易实现C.在二叉链表上，求根，求左、右孩子等很容易实现D.在二叉链表上，求双亲运算的时间性能很好6. 如图6-3所示的4 棵二叉树，是平衡二叉树。

图6-3 4 棵二叉树7. 如图6-4所示二叉树的中序遍历序列是。

A. abcdgefB. dfebagcC. dbaefcgD. defbagc图6-4 1 棵二叉树8. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是。

A. acbedB. decabC. deabcD. cedba9. 如果T2 是由有序树T 转换而来的二叉树，那么T 中结点的前序就是T2 中结点的。

A. 前序B.中序C. 后序D. 层次序10. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是。

A. bdgcefhaB. gdbecfhaC. bdgaechfD. gdbehfca11. 将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为。

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

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

习题六树和二叉树一、单项选择题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 层上最多含有结点数为（）I I-1 I-1 IA．2IB ．2I-1-1 C ．2I-1D ．2I-110．一棵二叉树高度为h, 所有结点的度或为0，或为2，则这棵二叉树最少有（）结点A．2h B ．2h-1 C ．2h+1 D ．h+111. 利用二叉链表存储树，则根结点的右指针是（）。

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

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

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 ;
第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个结点仅有一个孩子，则该二叉树的总结点数是多少。

数据结构第6章作业 树和二叉树答案

数据结构第6章作业 树和二叉树答案

第6章树和二叉树答案一、判断正误（√）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。

（×）2.二叉树中每个结点的两棵子树的高度差等于1。

（√）3.二叉树中每个结点的两棵子树是有序的。

（×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。

（×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。

（应当是二叉排序树的特点）（×）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。

（应2i-1）（×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。

（×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。

（应2i-1）（√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。

（正确。

用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。

由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。

）即有后继链接的指针仅n-1个。

（√）10. 〖01年计算机系研题〗具有12个结点的完全二叉树有5个度为2的结点。

最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5二、填空题1．由３个结点所构成的二叉树有5种形态。

2. 一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32个叶子。

注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。

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

（注：用⎣ log2(n) ⎦+1= ⎣ 8.xx ⎦+1=94.设一棵完全二叉树有700个结点，则共有350个叶子结点。

数据结构二叉树习题含答案

数据结构二叉树习题含答案

第 6 章树和二叉树1．选择题（ 1）把一棵树变换为二叉树后，这棵二叉树的形态是（）。

A．独一的Ｂ．有多种C．有多种，但根结点都没有左孩子Ｄ．有多种，但根结点都没有右孩子（ 2）由 3 个结点能够结构出多少种不一样的二叉树？（）A． 2 B ． 3 C ． 4 D． 5（ 3）一棵完整二叉树上有1001 个结点，此中叶子结点的个数是（）。

A． 250 B ． 500 C ． 254 D． 501（ 4）一个拥有 1025 个结点的二叉树的高h 为（）。

A． 11 B ． 10 C．11 至 1025 之间 D ．10 至 1024 之间（ 5）深度为 h 的满 m叉树的第 k 层有（）个结点。

(1=<k=<h)k-1B kCh-1 hA． m ． m-1 ． m D．m-1（ 6）利用二叉链表储存树，则根结点的右指针是（）。

A．指向最左孩子 B ．指向最右孩子 C ．空 D ．非空（ 7）对二叉树的结点从 1 开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采纳（）遍历实现编号。

A．先序 B. 中序 C. 后序 D.从根开始按层次遍历（8）若二叉树采纳二叉链表储存结构，要互换其全部分支结点左、右子树的地点，利用（）遍历方法最适合。

A．前序B．中序C．后序D．按层次（9）在以下储存形式中，（）不是树的储存形式？A．双亲表示法 B ．孩子链表表示法 C ．孩子兄弟表示法D．次序储存表示法（ 10）一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树必定满足（）。

A．全部的结点均无左孩子B．全部的结点均无右孩子C．只有一个叶子结点D．是随意一棵二叉树（ 11）某二叉树的前序序列和后序序列正好相反，则该二叉树必定是（）的二叉树。

A．空或只有一个结点B．任一结点无左子树C．高度等于其结点数 D ．任一结点无右子树（ 12）若 X 是二叉中序线索树中一个有左孩子的结点，且 X 不为根，则 X 的前驱为（）。

云大《数据结构》课程教学课件-第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
第六章-树和二叉树

第六章-树和二叉树


之
树 和 二 叉 树 13
1 2 3 A B C
4 5 6 7 0 D E F
8 0
9 10 0 G
¾ 二叉树顺序存储的算法描述
数 据 结 构
¾ 初始化二叉树
之
树 和 二 叉 树 14
#define Max_Size 100 typedef int TElemType; typedef TElemType SqBT[Max_Size+1]; void InitBT(SqBT bt){//设置空树 int i; for(i=1;i<=Max_Size;i++) bt[i]=0; }
数 据 结 构
之
树 和 二 叉 树 19
¾ 后序遍历顺序二叉树算法 void PostBT(SqBT bt,int i){ if(i>Max_Size||!bt[i]) return; PostBT(bt,2*i); PostBT(bt,2*i+1); printf("%3d ",bt[i]); }
数 据 结 构
之
树 和 二 叉 树 4
5. 孩子结点、双亲结点、兄弟结点、堂兄弟 结点、祖先结点、子孙结点…… 6. 结点的层次从根开始，根为第一层，根的 孩子为第二层；若某结点在第L层，则其 子树的根就在第L+1层。 7. 树的深度或高度：树中结点的最大层次。 8. 有序树：如果将树中结点的各子树看成是 从左至右有次序的；反之，则是无序树。 9. 森林：是m棵互不相交的树的集合。
数 据 结 构
之
树 和 二 叉 树 25
¾ 打印一维数组 void printSq(SqBT bt){ int i; printf("\nSeqArray:"); for(i=1;i<=Max_Size;i++) printf("%3d ",bt[i]); }
数据结构(严蔚敏)课件第6章讲解学习

数据结构(严蔚敏)课件第6章讲解学习

数据关系 R：
若D为空集，则称为空树 。
否则:
(1) 在D中存在唯一的称为根的数据元素root；
(2) 当n>1时，其余结点可分为m (m>0)个互
不相交的有限集T1, T2, …, Tm，其中每一 棵子集本身又是一棵符合本定义的树，
称为根root的子树。第7页
2020/7/25
基本操作： 查找类 插入类
线性结构
第一个数据元素 (无前驱)
树型结构
根结点 (无前驱)
最后一个数据元素 (无后继)
多个叶子结点 (无后继)
其它数据元素 (一个前驱、
一个后继)
2020/7/25
其它数据元素
(一个前驱、
多个后继)
第15页
基本术语
2020/7/25
第16页
结点: 数据元素+若干指向子树的分支
D
结点的度: 分支的个数
交的有限集合T0，T1，…，Tm-1，每个集合Ti（i=0,1,…,m-1）又是 一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前驱，
但可以有0个或多个直接后继。
由此可知，树的定义是一个递归的定义，即树的定义中又用到了树
的概念。
第6页
2020/7/25
ADT Tree{ 数据对象 D：
D是具有相同特性的数据元素的集合。
6.27,6.28,6.33,6.41,6.43,6.45,6.46,6.47, 6.49,6.50,6.51,6.57,6.59,6.68和6.66。
2020/7/25
第4页
6.1 树的类型定义
6.2 二叉树的类型定义
6.3 二叉树的存储结构
6.4 二叉树的遍历
6.5 线索二叉树6.6 树Fra bibliotek森林的表示方法
数据结构——用C语言描述(第3版)教学课件第6章 树与二叉树

数据结构——用C语言描述(第3版)教学课件第6章 树与二叉树


6.2 二叉树 6.2.1 二叉树的定义与基本操作 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构
6.2.1 二叉树的定义与基本操作 定义：我们把满足以下两个条件的树型结构叫做二 叉树（Binary Tree）： （1）每个结点的度都不大于2； （2）每个结点的孩子结点次序不能任意颠倒。
有序树：在树T中，如果各子树Ti之间是有先后次序的，则称为有序树。 森林：m（m≥0）棵互不相交的树的集合。将一棵非空树的根结点删去，树就变成一 个森林；反之，给森林增加一个统一的根结点，森林就变成一棵树。
同构：对两棵树，通过对结点适当地重命名，就可以使两棵树完全相等（结点对应相 等，对应结点的相关关系也像等），则称这两棵树同构。
二叉树的基本结构由根结点、左子树和右子树组成
如图示
LChild Data RChild
Data
LChild RChild
用L、D、R分别表示遍历左子树、访问根结点、遍 历右子树，那么对二叉树的遍历顺序就可以有：
(1) 访问根，遍历左子树，遍历右子树(记做DLR)。 (2) 访问根，遍历右子树，遍历左子树(记做DRL)。 (3) 遍历左子树，访问根，遍历右子树(记做LDR)。 (4) 遍历左子树，遍历右子树，访问根 (记做LRD)。 (5) 遍历右子树，访问根，遍历左子树 (记做RDL)。 (6) 遍历右子树，遍历左子树，访问根 (记做RLD)。
(8) NextSibling（Tree，x）： 树Tree存在，x是Tree中的某个结点。若x不 是其双亲的最后一个孩子结点，则返回x后面的下一个兄弟结点，否则 返回“空”。
基本操作:
(9) InsertChild（Tree，p，Child）： 树Tree存在，p指向Tree 中某个结点，非空树Child与Tree不相交。将Child插入Tree中， 做p所指向结点的子树。
数据结构第六章：树和二叉树

数据结构第六章：树和二叉树


性质2：深度为 的二叉树至多有 个结点(k≥ 性质 ：深度为k的二叉树至多有2 k 1 个结点 ≥1)
证明：由性质 ，可得深度为k 证明：由性质1，可得深度为 的二叉树最大结点数是
(第i层的最大结点数 ) = ∑ 2 i 1 = 2 k 1 ∑
i =1 i =1
k
k
10
性质3：对任何一棵二叉树 ，如果其终端结点数(即 性质 ：对任何一棵二叉树T，如果其终端结点数 即 叶节点)为 度为2的结点数为 的结点数为n 叶节点 为n0，度为 的结点数为 2，则n0=n2+1 证明： 为二叉树 中度为1的结点数 为二叉树T中度为 证明：n1为二叉树 中度为 的结点数 因为：二叉树中所有结点的度均小于或等于2 因为：二叉树中所有结点的度均小于或等于 所以：其结点总数n=n0+n1+n2 所以：其结点总数 又二叉树中，除根结点外， 又二叉树中，除根结点外，其余结点都只有一个 分支进入； 分支进入； 为分支总数， 设B为分支总数，则n=B+1 为分支总数 又：分支由度为1和度为 的结点射出，∴B=n1+2n2 分支由度为 和度为2的结点射出， 和度为 的结点射出 于是， 于是，n=B+1=n1+2n2+1=n0+n1+n2 ∴n0=n2+1
7
结点A的度：3 结点 的度： 的度 结点B的度：2 结点 的度： 的度 结点M的度：0 结点 的度： 的度 结点A的孩子： ， ， 结点 的孩子：B，C，D 的孩子 结点B的孩子 的孩子： ， 结点 的孩子：E，F 树的度： 树的度：3 E K 结点A的层次： 结点 的层次：1 的层次 结点M的层次 的层次： 结点 的层次：4 L B F A C G H M

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


F
G
H
M
I
J
结点F，G为堂兄弟 结点A是结点F，G的祖先
5
树的基本操作
树的应用很广，应用不同基本操作也不同。下面列举了树的一些基本操作： 1）InitTree(&T); 2）DestroyTree(&T); 3）CreateTree(&T, definition); 4）ClearTree(&T); 5）TreeEmpty(T); 6）TreeDepth(T); 7） Root(T); 8） Value(T, &cur_e); 9） Assign(T, cur_e, value); 10）Paret(T, cur_e); 11）LeftChild(T, cur_e); 12）RightSibling(T, cur_e); 13）InsertChild(&T, &p, i, c); 14）DeleteChild(&T,&p, i); 15）TraverseTree(T, Visit( ));
1
2 4 8 9 10 5 11 12 6 13 14 3 7 15 4 6 2
1
3
5 7
证明：设二叉树中度为1的结点个数为n1 根据二叉树的定义可知，该二叉树的结点数n=n0+n1+n2
又因为在二叉树中，度为0的结点没有孩子，度为1的结点有1 个孩子，度为2的结点有2个结孩子，故该二叉树的孩子结点 数为 n0*0+n1*1+n2*2(分支数） 而一棵二叉树中，除根结点外所有都为孩子结点，故该二叉 树的结点数应为孩子结点数加1即：n=n0*0+n1*1+n2*2+1
文件夹1
文件夹n

第六章 树与二叉树

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
左子女-右兄弟表示法 第一种解决方案

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


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

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

数据结构教案第六章树与二叉树目录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)。

针向下走，直到为空，途经的结点个数是相应森林所 含树的棵数；
若某个结点的左指针非空，说明这个结点在树中必
有孩子，并且从二叉树中该结点左指针所指结点开始， 沿右指针向下走，直到为空，途经的结点个数就是这 个结点的孩子数目。
26
二叉树还原为森林
步骤： 1.抹线：将二叉树中根结点与其右孩子之间的连线，及 沿右分支搜索到的所有右孩子间的连线全部抹掉，使 之变成孤立的二叉树。 2.还原：将孤立的二叉树还原成树。
fc
1 4
2 5^
3^
^ 6^ ^ ^ 7 ^ ^ ^ 8 9 ^
F
H
12
Ⅳ. 孩子-兄弟表示法(二叉树表示法) 用二叉链表作为树的存贮结构。 链表的两个指针域分别指向该结 点的第一个孩子结点和右边的下一 个兄弟结点。
A B C E D F G
13
A
B E
C F G
D
C 语言描述:
typedef struct CSNode{ ElemType data; struct CSNode Λ B *firstchild, *nextsibling; } CSNode, *CSTree; Λ E A
C
D G H
⑴森林中第一棵树的根结点； ⑵森林中第一棵树的子树森林； ⑶森林中其它树构成的森林。
I
J
K
36
1. 先序遍历 ① 若森林不空，则访问森林中第一棵树的根结点；
② 先序遍历森林中第一棵树的子树森林；
③ 先序遍历森林中其余树构成的森林。
即：依次从左至右对森林中的每一棵树进行先根遍历。
２. 中序遍历 ① 若森林不空，则中序遍历第一棵树的子树森林； ② 访问森林中第一棵树的根结点； ③ 中序遍历森林中其余树构成的森林。 即：依次从左至右对森林中的每一棵树进行后根遍历。 37
K
特点：很容易查找到结点 的双亲，但查找结点的孩 子时要遍历整个结构。
data parent R -1 0 A 0 B 0 C 1 D 1 E 3 F 6 G 6 H 6 K r=0,n=10
7
Ⅱ. 孩子链表表示法
首先使用数组来存放树的每个结点。每个数组元素 有两个域：data域和孩子指针域。 树中每个结点的孩子使用单链表组织起来。该元素 的孩子指针域指向孩子链表。如果没有孩子，则孩 子指针域为空。 顺序 + 链式存储结构 顺序结构存放结点，每个结点指向其孩子结点的单 链表。
1.兄弟加线 2. 保 留 双 亲 与 第一孩子连线, 删去与其他孩 子的连线 3. 顺 时 针 转 动 , 使之层次分明
16
G D G
练习题：请把图1的树转换成相应的二叉树。
A
A B
D H I E C
B E F G
C
F
G
D
H I
图1 树 图2 二叉树
17
讨论：二叉树怎样还原为树？
要点：逆操作，把所有右孩子变为兄弟！ a b d e f g h f g h
#define MAX_TREE_SIZE 100 typedef struct PTNode { //结点结构 Elem data; data int parent; // 双亲位置域 } PTNode;
parent
typedef struct { //树结构 PTNode nodes[MAX_TREE_SIZE]; int r, n; // 根结点的位置和结点个数 } PTree;
root
A Λ
C Λ D Λ F Λ
B E
C F G
D
Λ G Λ
14
A的右兄弟结点
R B C F
R G
R∧
A
∧
A
D
∧
D
∧
B C
∧
E
A 的 第 一 个 孩 子 结 点
E∧
A
H
K
F∧
∧
D E
F
B
G
∧
C G
H K
15
H
∧
K∧
树和二叉树之间的转换方法
AA A
B B B
E E E F F F G C
转换成的二叉树 特点是什么？ 根结点没有右孩 C子！ D C D
31
A
B
D E F H I
C G
1、树的遍历
⑶按层次遍历 若树不空，则自上而下自左 至右访问树中每个结点。 层次遍历序列： A
B
D E F H I
C G
AB C D EFGH I
32
A B E F C D G H I J
先根遍历时顶点的访问次序： ABEFCDGHI JK 后根遍历时顶点的访问次序： EFBC IJ KHGDA
19
由森林转换成二叉树的转换规则为:
设森林为：F = { T1, T2, … , Tm }，
二叉树为：B = ( root, LB, RB ) ① 若 F = Φ，即 m = 0，则 B = Φ; ② 若 F ≠ Φ，即 m ≠ 0，
则 root = ROOT(T1)；
LB为T1的子树森林 { T11, T12, … , T1n } 对应的二叉 树； RB为森林 { T2, …, Tm } 对应的二叉树。
先序遍历： a b c d e 中序遍历： b d c e a
后序遍历： d e c b a
结论：
1. 树的先根遍历与二叉树的先序遍历相同；
2. 树的后根遍历相当于二叉树的中序遍历；
3. 树没有中序遍历，因为子树无左右之分。
35
2、森林的遍历
根据森林和二叉树的对应关系，森林可分解成三部分：
B E F
20
森林和二叉树的转换
森林转换成二叉树的方法：
将每棵树分别转换成二叉树；
将每棵树的根结点用线相连，以第一棵树的根结点 为二叉树的根，再以根结点为轴心，顺时针旋转45 度，形成二叉树结构； 或将第i+1棵二叉树作为第i棵二叉树的右子树。
21
有3棵树的森林：
A B C (a)森林 D
E F H G I B
3^
A D
R
B E
G
C F H K
^ 6^ ^ ^ 7 ^ ^ ^ 8 9 ^ 特点：很容易查找到结点的孩 子，但查找结点的双亲时要遍 历整个结构。
11
r=0,n=10
Ⅲ. 双亲孩子表示法
R A D E G B C parent data 0 -1 R 1 0 A 2 0 B 3 0 C 4 1 D K 5 1 E 6 3 F 7 6 G 8 6 H 9 6 K
27
二叉树
B C
A E F D H I J A G B
A F C
E H
G I
D
J 将二叉树还原为树
抹线
B
C D F
E
G H I J B
A C D
E
G H
F
I
J
28
有3棵树的森林
练习题： 请画出和下列二叉树对应的森林。E E B A C F NhomakorabeaI
J G
B
K
A C F
I
J G
K
D
D
29
三、树和森林的遍历
k 1
40
例如：
2
7 5 2 4 9
4 5 7 9
WPL =72+52+23+43+92 =60
WPL = 74+94+53+42+21 = 89
41
最优二叉树
在所有含 n 个叶子结点、并带相同权值的 m 叉树中， 必存在一棵其带权路径长度取最小值的树，称为“最 优树”。 如果 m = 2，称为“最优二叉树 或 赫夫曼树”。
5
Ⅰ.树的双亲表示法举例
data parent
A B E C F G D
0 1 2 3 4
A B C D E
-1 0 0 0 2
r = 0 //根结点位置 n = 7 //结点个数
如何找孩 子结点？
5 6
F G
2 5
6
树的双亲表示法 R A B E C 0 1 2 3 4 5 6 7 8 9
D
F G H
K 层次遍历时顶点的访问次序：
ABCDEFGHIJK
33
树若采用“先转换，后遍历”方式，结果是否一样？ a
a
b
b
c d
e
d
c e
先根序列： a b c d e 后根序列： b d c e a
先序遍历： a b c d e 中序遍历： b d c e a
后序遍历： d e c b a
34
先根序列： a b c d e 后根序列： b d c e a
⑵孩子表示法 ⑶双亲孩子表示法 ⑷孩子兄弟表示法
3
Ⅰ. 双亲表示法 使用一组地址连续的空间（数组）存储树的结点，
同时在每个结点中附设一个指示器来指示其双亲结
点的位置。 即：每个数组元素包含两个域：

数据域：存放结点本身的信息。 双亲域：指示该结点的双亲结点在数组中的下 标位置。
4

C 语言描述:
第六章 树和二叉树
6.1 树的类型定义 6.2 二叉树的类型定义和实现
6.3 遍历二叉树和线索二叉树
6.4 树和森林 6.5 Huffman树与Huffman编码
1
6.1 树的类型定义
树 是 n (n ≥0 )个结点的有限集 D，当n ≥1 时：
1）有一个特定的结点 root 被称为根 (结点);
森林为：F = { T1, T2, … , Tm } ① 若 B = Φ， 则 F = Φ； ② ROOT(T1) = root； 由 LB 对应得到 ( T11, T12, …，T1n )； 由 RB 对应得到 (T2, T3, …, Tm)。