当前位置：文档之家 › 第6章 树和二叉树分析

第6章 树和二叉树分析

  • 格式：ppt
  • 大小：964.50 KB
  • 文档页数：106

下载文档原格式

  / 106

合集下载

数据结构-第六章 树与二叉树.ppt

数据结构-第六章 树与二叉树.ppt

lChild data parent rChild
含三个指针域的结点结构 parent
data
data
lChild
rChild
二叉链表
lChild
rChild
三叉链表
性质： 含有n个结点的二叉链表中有n+1个空链域。 证明：对于叶结点n0有两个空链域，n1有1
个空链域，n2没有空链域。所以 空链域数＝2n0+n1 将n0=n2+1代入得(根据性质3) 2n0+n1=n0+n1+n2+1=n+1
例如
A 只有根结点的树
A
BC
D
E F GH I J
KL
M
有13个结点的树
其中：A是根；其余结点分成三个互不相交的子集， T1={B,E,F,K,L}； T2={C,G}； T3={D,H,I,J,M}, T1,T2,T3都是根A的子树，且本身也是一棵树
树的基本术语
A
BC
D
E F GH I J
KL
4 5 67
1
8 9 10 11 12
1
2
3
2
3
45
45
6
非完全二叉树
67
性质4 具有 n 个结点的完全二叉树的深度 为log2(n) ＋1 证明：
设完全二叉树的深度为 h，则根据性 质2和完全二叉树的定义有
2h－1 - 1 < n 2h - 1或 2h－1 n < 2h
取对数 h－1 log2n < h，又h是整数， 因此有 h = log2(n) ＋1
证明：若度为1的结点有 n1 个，总结点个 数为 n，总边数为 e，则根据二叉树的定

第6章树和二叉树

第6章树和二叉树
– 先根（序）遍历：先访问树的根结点，然后依次先根遍历根的 每棵子树
– 后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点 – 按层次遍历：先访问第一层上的结点，然后依次遍历第二层，
……第n层的结点
2020/4/13
A
B
C
D
EFG I
H J K LM
NO
先序遍历：A B E F I G C D H J K L N O M
2020/4/13
嵌套集合表示
a
b
e
c
d
ij
f
gh
嵌套括号表示(广义表表示法)
a ( b ( d, e ( i, j ), c ( g, h ) ) )
2020/4/13
• 6.2 二叉树
– 定义
• 定义：二叉树是n(n0)个结点的有限集，它或为空树 (n=0)，或由一个根结点和两棵分别称为左子树和右子 树的互不相交的二叉树构成
后序遍历：E I F G B C J K N O L M H D A 层次遍历：A B C D E F G H I J K L MN O
2020/4/13
– 二叉树的遍历
• 方法
– 先序遍历：先访问根结点,然后分别先序遍历左子树、右子树 – 中序遍历：先中序遍历左子树，然后访问根结点，最后中序
遍历右子树 – 后序遍历：先后序遍历左、右子树，然后访问根结点 – 按层次遍历：从上到下、从左到右访问各结点
a
b
c
d
e
1 2 3 4 5 6 7 8 9 10 11 abcde0000fg
f
g
2020/4/13
• 链式存储结构
空指针个数：–2*二n0叉+1链*n表1+0*n2 =2n0+tynp1edef struct node =n0+n{1+nd0atatype data; =n0+n}1J+Dns;2tr+u1ct node *lchild, *rchild; =n+1

第6章树与二叉树-

第6章树与二叉树-

F3
7
G6
8
H6
9
K6
8
2. 孩子表示法
由于树中每个结点可能有多棵子树，则可以用多重 链表，即每个结点有多个指针域，其中每个指针指向一 棵子树的根结点，此时，链表中的结点可以有如下 3 种 结构格式：
同构结点格式 不同构结点格式 单链表存储结构
9
(1) 同构结点格式。即多重链表中的结点是同构的。
完全二叉树：一棵深度为 k 并且有 n 个结点的二叉 树，当且仅当其每一个结点都与深度为 k 的满二叉树中 编号从 1 至 n 的结点一一对应时，称之为完全二叉树。
完全二叉树的特点是：二叉树中的叶子结点只可能 出现在二叉树中层次最大的两层上；最下一层的结点一 定是从最左边开始向右放的；并且若某个结点没有左孩 子，则它一定没有右孩子。
为 2 的结点有两个出支，则：B = n1 + 2n2 故：n = n1 + 2n2 + 1；最后得到： n0 = n2 + 1。
20
为便于介绍下面两个二叉树性质，先了解满二叉树 (full binary tree) 和完全二叉树 (complete binary tree) 的 概念。
满二叉树：一棵深度为 k 并且有 2k-1 个结点的二叉 树，称之为满二叉树。
23
性质5：如果对一棵有 n 个结点的完全二叉树（此二 叉树的深度为 log2n +1）的结点按照层次编号（从第 1 层到第 log2n +1 层，每层从左到右），那么对任一结点 i（1 ≤i ≤n），有
(1) 若 i = 1，则结点 i 是二叉树的根，没有双亲结点； 若 i ＞1，则其双亲结点是结点 i / 2。
(2) 若 2i ＞n，则结点 i 没有左孩子（结点 i 为叶子结 点）；否则其左孩子是结点 2i。

第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章树和二叉树基本概念和二叉树ppt课件

数据结构第6章树和二叉树基本概念和二叉树ppt课件

§6.2 二叉树
❖二叉树的定义
问：具有3个结点的二叉树可能有几种不同形态？ 普通树呢？ 5种/2种
§6.2 二叉树
❖二叉树的抽象数据类型定义
ADT BinaryTree{
数据对象D: D是具有相同特性的数据元素的集合。
数据关系R: 若D=Φ，则R= Φ ；
若D≠Φ，则R= {H}；存在二元关系：
第6章 树和二叉树
§6.1 树的基本概念
❖树的逻辑定义
树是由n (n≥0)个结点组成的有限集合T。 在任意一个非空树中：
有且仅有一个特定的结点称为根(root)； n > 1时，其余结点可以分为m (m>0) 个互不相交 的有限集T1, T2, T3, …,Tm，其中每一个集合本身又是 一棵树，且称为根的子树。 注意：1.树的定义具有递归性，即树中有树。
§6.2 二叉树
❖二叉树的性质
讨论3：二叉树的叶子数和度为2的结点数之间有关系吗？ 性质3: 对于任何一棵二叉树，若2度的结点数有n2个，则叶子数 （n0）必定为n2＋1 （即n0=n2+1）
证明： ∵ 二叉树中全部结点数n＝n0+n1+n2(叶子数＋1度结点数＋2度结点数)
又∵ 二叉树中全部结点数n＝B+1 (总分支数＋根结点 ) （除根结点外，每个结点必有一个直接前趋，即一个分支）
=
方 良
蒋丘
纬 国
=
如 雪
蒋徐
孝 文
=
乃 锦
蒋汪
孝 武
=
长 诗
蒋俞
孝 章
=
扬 和
蒋方
孝 勇
=
智 怡
蒋王
孝 刚
=
倚 惠

第6章树和二叉树

第6章树和二叉树
2.孩子表示法 孩子表示法 在结点中设置指向每个孩子的指针域， 在结点中设置指向每个孩子的指针域，利用指针 指向该结点的所有孩子结点。 指向该结点的所有孩子结点。 大多采用按树的度设置结点的指针域的个数。 大多采用按树的度设置结点的指针域的个数。
9
6.1.4 树的存储结构
3.孩子兄弟表示法 孩子兄弟表示法 在结点中设置两个指针域， 在结点中设置两个指针域，一个指针域指向该结 点的第一个孩子，另一个指针域指向其右兄弟。 点的第一个孩子，另一个指针域指向其右兄弟。
2
6.1.1树的定义 树的定义
结点的度：结点所拥有子树的个数称为结点的度。 结点的度：结点所拥有子树的个数称为结点的度。 子树 称为结点的度 树的度：树中所有结点的度的最大值称为树的度。 最大值称为树的度 树的度：树中所有结点的度的最大值称为树的度。 叶结点：度为零的结点称为叶结点。也称终端结点 终端结点或 叶结点：度为零的结点称为叶结点。也称终端结点或叶 子 分支结点：度不为零的结点称为分支结点。也称非终端 分支结点：度不为零的结点称为分支结点。也称非终端 结点。除根结点以外，分支结点也称为内部结点。 结点。除根结点以外，分支结点也称为内部结点。 孩子结点和双亲结点： 孩子结点和双亲结点：树中一个结点的子树的根结点称 为孩子结点。该结点就称为孩子结点的双亲结点。 为孩子结点。该结点就称为孩子结点的双亲结点。 兄弟结点：具有同一双亲的孩子结点互为兄弟结点。 兄弟结点：具有同一双亲的孩子结点互为兄弟结点。 结点的祖先：从根到该结点所经分支上的所有结点， 结点的祖先：从根到该结点所经分支上的所有结点，称 为结点的祖先。 为结点的祖先。
17
6.2.2 二叉树的性质
性质4 具有n（ 性质 具有 （n>0）个结点的完全二叉树的深度 ）个结点的完全二叉树的深度h= log 2 n + 1 证明： 证明： 根据完全二叉树的定义可知深度为h-1层及以上的结点构成 根据完全二叉树的定义可知深度为 层及以上的结点构成 满二叉树，因此由性质2得深度为 得深度为h的完全二叉树满足 满二叉树，因此由性质 得深度为 的完全二叉树满足 n>2h-1-1和n≤2h-1 和 整理后得到 2h-1≤n<2h 不等式两边取对数， 不等式两边取对数，得 h-1≤log2n<h 由于h为正整数 为正整数， 由于 为正整数，因此 h= log 2 n + 1

树和二叉树——精选推荐

第6章 树和二叉树内容概要：本章主要介绍树，二叉树，最优二叉树的相关概念和操作，存储结构和相应的操作，并在综合应用设计中，给出了对应算法的C 语言实现。

教学目标1．理解各种树和森林与二叉树的相应操作。

2．熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其他操作。

3．熟练掌握二叉树和树的各种存储结构及其建立的算法。

4．掌握哈夫曼编码的方法。

5．通过综合应用设计，掌握各种算法的C 语言实现过程。

基本知识点：树和二叉树的定义、二叉树的存储表示、二叉树的遍历以及其它操作的实现、树和森林的存储表示、树和森林的遍历以及其它操作的实现、最优树和赫夫曼编码重点：二叉树的性质、二叉树的遍历及其应用，构造哈夫曼树。

难点：编写实现二叉树和树的各种操作的递归算法。

本章知识体系结构：课时安排：6个课时树的定义 树树的性质 树的逻辑表示法 树形表示法 树的存储结构 双亲存储结构 文氏表示法凹入表示法 括号表示法 孩子存储结构 孩子双亲存储结构二叉树二叉树的定义 二叉树的性质二叉树的逻辑表示法（采用树的逻辑表示法）二叉树的存储结构二叉树的顺序存储结构先序遍历 中序遍历 后序遍历二叉树的遍历 二叉树的链式存储结构（二叉链） 由先序序列和中序序列构造二叉树 由中序序列和后序序列构造二叉树二叉树的构造 二叉树的线索化 哈夫曼树二叉树和树之间的差别 二叉树与树、森林之间的转换二叉树和树课程数据结构教学教具多媒体课件学时2班级06网络教学日期/课时 /2课时教学单元第6章树和二叉树教学方法讲授（PPT）教学目标掌握树、二叉树的基本概念和术语，二叉树的性质教学重点二叉树的定义、二叉树的性质、链式存储结构教学难点二叉树的性质、链式存储二叉树的基本操作组织教学一、树的定义二、树的基本概念三、二叉树的定义、性质四、二叉树的顺序存储结构和链式存储结构五、小结作业复习本讲内容并预习下一讲内容课堂情况及课后分析课程数据结构教学教具多媒体课件学时2班级06网络教学日期/课时 /2课时教学单元第6章树和二叉树教学方法讲授（PPT）教学目标掌握二叉树遍历的三种方法及二叉树的基本操作教学重点二叉树的遍历算法教学难点中序与后序遍历的非递归算法组织教学一、复习二叉树的定义二、遍历二叉树的三种方法三、递归法遍历二叉树四、二叉树的基本操作五、总结作业复习本讲内容并预习下一讲内容课堂情况及课后分析课程数据结构教学教具多媒体课件学时2班级06网络教学日期/课时 /2课时教学单元第6章树和二叉树教学方法讲授（PPT）教学目标理解树与森林的转换，掌握哈夫曼树教学重点哈夫曼树教学难点树与森林的转换组织教学一、导入二、树与森林三、哈夫曼树四、小结作业习题6课堂情况及课后分析前面几章讨论的数据结构都属于线性结构，线性结构的特点是逻辑结构简单，易于进行查找、插入和删除等操作，可用于描述客观世界中具有单一前驱和后继的数据关系。

06树与二叉树详解2PPT课件


12.11.2020
2
本讲主要介绍以下几个方面的内容： • 树的定义及基本概念； • 树、森林与二叉树之间的相互转换； • 树的各种存储结构； • 树、森林的遍历。
12.11.2020
3
6.1 树 的 概 述
6.1.1 树的定义及特性
所谓“树（Tree）”是指由n（n≥0） 个结点构成的有限数据元素的集合T。当n=0 时，称其为“空树”。当n≠0时，树中诸结 点应该满足下面的两个条件：
只有无右子树的二叉树，才能通过转换 成为一棵树。具体步骤如下：
（1）找到二叉树中某结点的右孩子及右 孩子的右孩子……，在它们与该结点的双亲 结点之间添加连线；
树中度大于0的结点称为分支结点，或 非终端结点。
12.11.2020
12
• 路径 从树中一个结点到另一个结点之间的分
支，称为这两个结点间的路径。 • 路径长度
一条路径上的分支数，称为该路径的长 度。
12.11.2020
13
2．有关结点间关系的术语
• 根结点 所谓“根”结点，即是指树中没有直接
前驱的那个结点。一棵树，只能有一个根结 点。 • 孩子结点
棵树的度。 • 树的深度
一棵树中各结点的深度的最大值，称为 该树的深度。树的深度有时也称为树的高度。
12.11.2020
17
• 有序树与无序树 如果限定树中各结点的子树从左至右的
排列具有一定顺序，不得互换，那么就称该 树是有序的，否则称为是无序树。 • 森林
n（n≥0）棵互不相交的树的集合，称 为森林。
12.11.2020
22
例：将图6-6（a）所示的树，转换成它所 对应的二叉树。
12.11.2020
23

第6章树和二叉树好精品PPT课件

或深度为k的满二叉树中编号从1到n的前n个结点构成了一棵深度 为k的完全二叉树。
其中 2k-1 ≦ n≦2k-1 。
完全二叉树是满二叉树的一部分，而满二叉树是完全二叉树的特 例。
•完全二叉树的特点：
若完全二叉树的深度为k ，则所有的叶子结点都出现在第k层
或k-1层。对于任一结点，如果其右子树的最大层次为l，则其左 子树的最大层次为l或l+1。
结点的层次：从根开始定义为第1层，根的孩子
v
为第二层……。
树的深度（高度）：树中结点的最大层数。
森林（forest）：是m（m ≥ 0）棵互不相交的树
的集合。
6.2 二叉树
6.2.1 二叉树的定义 1 二叉树的定义
二叉树(Binary tree)是n(n≥0)个结点的有限集 合。若n=0时称为空树，否则： ⑴ 有且只有一个特殊的称为树的根(Root)结点； ⑵ 若n>1时，其余的结点被分成为二个互不相
(a) 二叉链表结点
(b) 三叉链表结点
图6-7 链表结点结构形式
(2) 二叉树的链式存储形式
例有一棵一般的二叉树，如图6-8(a)所示。以二叉链表和三叉链表 方式存储的结构图分别如图6-8(b) 、 6-8(c)所示。
a b cd
T a⋀
b ⋀c ⋀ d
T a ⋀⋀
b ⋀c ⋀ d
交的子集T1,T2，分别称之为左、右子树，并 且左、右子树又都是二叉树。 由此可知，二叉树的定义是递归的。
2 二叉树的基本形态 二叉树有5种基本形态，如图6-3所示。
AA
A
A
(a) (b)
(c) (d)
(e)
(a) 空二叉树 (b) 单结点二叉树 (c) 右子树为空

第6章树和二叉树

第6章树和二叉树第 6 章树和二叉树6.1 已知一棵树如图所示，回答下列问题：(1) 哪个是根结点?(2) 哪些是叶子结点?(3) 哪个是结点 G 的双亲?(4) 哪些是结点 G 的祖先?(5) 哪些是结点 B 的孩子?(6) 哪些是结点B的子孙?(7) 哪些是结点 E 的兄弟?(8) 结点 B 和 H 的层次号分别是什么 ?(9) 树的深度是多少?(10) 以结点 C 为根的子树的深度是多少? 【6.1 解】：(1) A(2) K, F,G,H,I,J(3) B(4) B,A(5) E,F,G(6) E,F,G,K(7) F,G(8) 2, 3(9) 4(10) 26.2 在结点个数为n(n>1)的各棵树中，最小的高度是多少？它有多少个叶结点？多少个分支结点？最大的高度树是多少？它有多少个叶结点？多少个分去结点？【6.2解】结点个数为n时，高度最小的树高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1，有n层；它有1个叶结点，n-1个分支结点。

6.3简述树与二叉树的区别？【6.3解】二叉树的度最大为2，而树的度可以大于2；二叉树的每个结点的孩子有左、右之分，而树中结点的孩子无左右之分。

6.4 n(n>1)个结点的各棵二叉树中，最小的高度（h≥1）多少？最大的高度是多少？【6.4解】最小高度为：⎣⎦n2log+1,此时树为完全二叉树；最大高度为n，比如一棵斜二叉树。

6.5如果一棵树有n1个度为1的结点，有n2个度为2的结点，…，n m个度为m的结点，试问有多少个度为0的结点？试推导之。

【6.5解】设叶子结点数为n0，则树中结点数和总度数分别为: 结点数=n0+n1+n2+...+n m总度数=n1+2n2+...+m×n m结点数等于总度数加1，所以得到：n0=∑=+-miini21))1((6.6如果已知一棵二叉树有20个叶子结点，有10个结点仅有左孩子，15个结点仅有右孩子，求出该二叉树的结点数目。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第六章 树
（2）除根结点以外的其它结点可以划分为m （ m≥0 ） 个 互 不 相 交 的 有 限 集 合 T0 ， T1 ， … ， Tm-1，每个集合Ti（i=0,1,…,m-1）又是一棵树， 称为根的子树，每棵子树的根结点有且仅有一个 直接前驱，但可以有0个或多个直接后继。
由此可知，树的定义是一个递归的定义，即树的 定义中又用到了树的概念。
第六章 树
第6章 树
数据结构（C描述）
第六章 树
6.1 树的基本概念
6.2 二叉树
目
6.3遍历二叉树
录
6.4线索二叉树
6.5树和森林
6.6 哈夫曼树
第六章 树 6.1 树的基本概念
6.1.1 树的定义
1．树的定义
树是由n（n≥0）个结点组成的有限集合。若n=0， 称为空树；若n>0，则： （1）有一个特定的称为根（root）的结点。它 只有直接后继，但没有直接前驱；
树的结构参见图6-1。
第六章 树
B

E
F
A
C
D
GH
I
ø
A
J KL
M
（a）空树 （b）仅含有根结点的树 （c） 含有多个结点的树 图6-1 树的示意图
第六章 树
在图6-1(c)中，树的根结点为A，该树还可以 分为三个互不相交子集T0，T1，T2，具体请 参见图6-2，其中T0={B，E，F，J，K，L}， T1={C，G}，T2={D，H，I，M}，其中的T0， T1，T2都是树，称为图6-1（C）中树的子树， 而T0，T1，T2又可以分解成若干棵不相交子 树。如T0可以分解成T00，T01两个不相交子集， T00={E，J，K，L}，T01={F}，而T00又可以分 为三个不相交子集T000，T001，T002，其中， T000={J}，T001={K}，T002={L}。
第六章 树
B
E
F
A
C
D
GH
I
J KL
M
图6-2树的树形表示法
第六章 树
2. 凹入法表示法
每棵树的根对应着一个条形，子树的根 对应着较短的条形，且树根在上，子树 的根在下。图1树对应的凹入表见下图 2(b)，具体参见图6-3 。
L F C G D H
第六章 树
A B E J K L
C FA
G
D H M I
图6-2 图6-1(C的) 树的三个子树
第六章 树
B C
E
F
G
J KL
(a) T0子树
(b) T1子树
D
H
I
M (c) T2子树
图6-2 图6-1(C的) 树的三个子树
第六章 树
2．树的逻辑结构描述
一棵树的逻辑结构可以用二元组描述为：
tree =(k,R) k={ki∣1≤i≤n;n≥0,kielemtype}
A
B
C
D
E F GH I
J KL
M
图6-3的树的凹入法表示
图6-2树的树形表示法
第六章 树
3. 嵌套集合表示法（集合图表示法） 每棵树对应一个圆形，园内包括根结点和子 树，下图2(a)就是图1对应的集合图，具体参 见图6-4 。
第六章 树
14. 无序树 若一棵树中所有子树的次序无关紧要，则称为 无序树。 15．森林（树林） 若干棵互不相交的树组成的集合为森林。一棵 树可以看成是一个特殊的森林。
第六章 树
图1 树T
例如：
1. A的度为2，B的度为3， 树的度为3；
2. A,B,C,E为分支结点， D,H,I,F,G为叶子结点
3. B,C为A的孩子结点；A 为B,C的双亲结点；B,C 互为兄弟结点；H的祖先 结点为A,B,E；B的子孙 结点为D,E,F,H,I。
例如，对图6-1的树结构,可以二元组表示为：
A
B
C
D
E
F
G
H
I
J
K
L
M
图6-1 树的示意图
第六章 树
K={A，B，C，D，E，F，G，H，I，J，K，L，M} R={r} r={(A,B)，(A,C)，(A,D)，(B,E)，(B,F)，(C,G)，
(D,H)，(D,I)，(E,J)，(E,K)，(E,L)，(H,M)}
R={r} 其中，n为树中结点个数，若 n=0，则为一棵 空树， n> 0时称为一棵非空树，而关系 r 应满 足下列条件：
第六章 树
（1）有且仅有一个结点没有前驱,称该结点为 树根; （2）除根结点以外,其余每个结点有且仅有一 个直接前驱; （3）树中每个结点可以有多个直接后继(孩子 结点)。
第六章 树
第六章 树
图1 树T
4. A在1层，B,C在2层， D,E,F,G在3层，H,I在4层， 树的深度为4；
5. 对于一棵反映父子关系的家 族树，兄弟结点之间是按照
排行大小有序的，所以它是 一棵有序树。
6. 在图1的树T中，由A结点的 子树所构成的森林为(T1， T2)，由B结点的子树所构成 的森林为(T11，T12，T13)。
5.双亲结点 若结点X有子女Y，则X为Y的双亲结点。
6.祖先结点 从根结点到该结点所经过分枝上的所有结点为该结 点的祖先，如图6-1（c）中M的祖先有A，D ，H 。
第六章 树
7.子孙结点 某一结点的子女及子女的子女都为该结点子孙。
8.兄弟结点 具有同一个双亲的结点，称为兄弟结点。
9.分枝结点 除叶子结点外的所有结点，为分枝结点，也 叫非终端结点。
第六章 树
6.1.2 基本术语
1.结点 指树中的一个数据元素，一般用一个字母表示。 2.结点的度 一个结点包含子树的数目，称为该结点的度。
3.树叶（叶子） 度为0的结点，称为叶子结点或树叶，也叫终 端结点。
第六章 树
4.孩子结点 若结点X有子树，则子树的根结点为X的孩子结 点，也称为孩子，儿子，子女等。
第六章 树
10．层数 根结点的层数为1，其它结点的层数为从根结 点到该结点所经过的分支数目再加1。
11. 树的高度（深度） 树中结点所处的最大层数称为树的高度，如空 树的高度为0，只有一个根结点的树高度为1。
12.树的度 树中结点度的最大值称为树的度。
第六章 树
13. 有序树 若一棵树中所有子树从左到右的排序是有顺 序的，不能颠倒次序。称该树为有序树。
第六章 树
6.1.3 树的表示
1．树形结构表示法
树的表示方法有多种。下图中的树形表示法是 其中的一种，也是最常用的一种。在这种表示 方法中，结点之间的关系是通过连线表示的， 虽然每条线上都不带有箭头（即方向)，但它 并不是无向的，而是有向的，其方向隐含从上 到下，即连线的上方结点是下方结点的前驱， 下方结点是上方结点的后继。