资源简介

(共27张PPT)
4.1树
情景导入
PART
1
树的概念与特性
一 树的概念
树是一种非线性的数据结构，用它能很好地描述有分支和层次特性的数据集合
树在计算机领域中也有广泛应用，在编译系统中，用树表示源程序的语法结构。在数据库系统中，树形结构是数据库层次模型的基础，也是各种索引和目录的主要组织形式。
一 树的概念
树是由n（n≧0）个节点构成的一个有限集合以及在该集合上定义的一种节点关系。
节点：集合中的元素。
空树：n = 0 的树。
子树：树中某个节点下面的所有节点所构成的树。
边：一颗具有 n 个节点的树有 n-1 条边。
二 基本术语
·节点的度：树的一个节点所拥有的子树个数。
·树的度：最大的节点的度。
二 基本术语
·根节点：没有前驱的节点。
·叶子节点：度为 0 的节点。
·分支节点：度不为0的节点。
·父节点或双亲节点：上端节点称为下端节点的父节点。
·孩子节点：下端节点称为上端节点的孩子节点
·兄弟节点：具有同一父节点的节点
二 基本术语
·节点的层数：树中节点从根开始计算，根的层数为1，其他节点的层数等于父节点层数加1
·树的高度或深度：树中节点的最大层数。根的层数为1。
第1层
第2层
第3层
第4层
树的深度
二 基本术语
·森林：0个或多个不相交的树的集合
A
B
C
练习
【例1】(1)该树共有个 节点， 条边。
(2)根节点的名称是 它有 个孩子节点，节点E . (选填:是/不是)根节点的孩子节点.
(3)节点A和节点B的度分别是 ,整棵树的度是 。
(4)该树的分支节点的数量是 ，叶子节点的数量是 。
(5)节点C的层数是 ，树的深度是 。
(6)节点D的父节点是 ，兄弟节点是 ，孩子节点是 。
10
9
A
3
不是
3、3
3
4
6
2
3
A
B、C
I、J
PART
2
二叉树
一 二叉树的概念
二叉树是一种特殊的树，是由n（n≧0）个节点构成的一个有限集合，且各个节点的度小于或等于2，二叉树的子树有左右之分，其次序不能任意颠倒（有序树）。
A
B
C
D
E
F
G
H
A
B
C
D
E
F
G
H
≠
二 二叉树的形态
A
A
B
A
C
(1)空二叉树
(2)只有根节点的单点树
(3)只有根节点和左子树
(4)只有根节点和右子树
A
B
C
(5)左右子树均非空
三 特殊二叉树
1.完全二叉树
设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
A
B
C
D
E
G
H
I
F
J
(1～h-1) 层
第 h 层
三 特殊二叉树
2.满二叉树
每一层都是满的，每个节点的度要么是2，要么为0，而且所有叶子节点都在同一层。
A
B
C
D
E
G
F
练习
【例2】观察如图所示的二叉树示意图，下列说法正确的是( ）
A.这是一棵完全二叉树
B.这是一棵满二叉树
C.这棵二叉树的深度是4
D.这棵二叉树的度是4
C
四 二叉树的性质
1.二叉树的第i层上最多有 （i>=1）个节点。
2.深度为h的二叉树最多有 （h>=1）个节点。
3.在任意一棵二叉树中，若其叶子节点的数量为n0，度为2的节点数量为n2，则 。
A
B
C
D
E
G
H
I
F
J
A
B
C
D
E
G
F
四 二叉树的性质
4.具有 n 个结点的完全二叉树的深度 。
5.给定n个节点，能构成 种不同的二叉树。
A
B
C
D
E
G
H
I
F
J
A
B
C
D
E
G
F
练习
【举一反三1】已知二叉树T共有10个节点,其中度为1的节点数量为3,则叶子节点数量为()
A.3
B.4
C.5
D.6
B
练习
【举一反三2】某棵树有5个节点,树的度和深度均为3,请画出这棵树所有可能的形态。
练习
【举一反三3】已知某二叉树总共有7个节点,其中叶子节点的个数为4,叶子节点的数据分别为1,2,3,4;每个双亲节点的数据值均为其孩子节点数据值之和。
(1)该二叉树的深度为 。
(2)该二叉树根节点的数据值为 。
(3)若考虑叶子节点不同的排列情况,则该二叉树有 种画法。
(4)请画出2棵符合条件的二叉树。
3
10
24
练习
一棵完全二叉树上有1001个节点，其中叶子节点的个数是（ ）
A.250
B.500
C.505
D.501
D
练习
一棵高度为4的完全二叉树上至少有（ ）个节点
A.15
B.7
C.8
D.16
8
PART
3
哈夫曼树
一 哈夫曼树
4
3
8
2
路径：树中两个节点之间所经过的分支
路径长度：一条路径上的分支数
节点的权：给二叉树中的节点赋一个值
节点带权路径长度：从根节点到一个节点的路径长度与该节点的权值
的乘积
树的带权路径长度：一棵树中所有叶子节点的带权路径长度之和
WPL的公式：
最优二叉树：在具有n个带权叶子节点的所有二叉树中，称带权路径长度WPL最小的二叉树为最优二叉树。在最优二叉树中权值较大的节点离根节点较近。
练习
如图所示三棵树中哪棵树是最优二叉树？
WPL1=8*3+4*2+2*2+3*2=42
4
3
8
2
4
8
3
2
8
2
3
4
WPL2=4*2+8*2+2*3+3*2=36
WPL3=8*1+4*2+3*3+2*4=33
THANKS

展开更多......

收起↑