资源简介

(共37张PPT)
树与二叉树
1 树
本节要点：
2 二叉树
1.1 树的概念
1.2 树的特点
2.1 二叉树的概念
2.2 二叉树的分类
2.3 二叉树的性质
树？
生活中的树
逻辑上的树
常见的树形结构
1.公司组织架构
2.知识点汇总
3.动物分类
共同特征：一对多的非线性关系
1.1 树的概念
树：一种非线性数据结构，
是有 n（n>=0）个节点构成的有限集合
空树：节点n=0的树
1.2 树的特点
1.2 树的特点
当n>0时，n个节点的树有n-1条边
子树：树中某个节点下面的所有节点所构成的树
边
节点
T1
T2
T3
T4
11个节点，10条边
1.2 树的特点
节点的度: 节点所拥有的子树个数
树的度：最大的节点的度（树的宽度）
A的度: _____
B的度: _____
C的度：____
树的度：___
3
2
0
4
1.2 树的特点
高度或深度：树中节点的最大层数
树的高度：___
①
②
③
④
4
根节点：（开始节点）没有前驱节点
叶子节点：（终端节点）没有后继节点，度为0
1.2 树的特点
A是根节点
E、F、C、H、I、J、K是叶子节点
分支节点：度不为0的节点
内部节点：除根节点外的分支节点
1.2 树的特点
A、B、D、G是分支节点
B、D、G是内部节点
父节点：对于两个以边直接连接的节点，
上端节点称为下端节点的父节点或双亲节点
1.2 树的特点
A是B、C、D的父节点
1.2 树的特点
B、C、D是A的孩子节点
B、C、D互为兄弟节点
孩子节点：下端节点称为上端节点的孩子节点
兄弟节点: 拥有同一个父节点的同层节点
1.2 树的特点
学习任务一
填一填：
1.该树有___个节点，___条边，该树的度是_____,高度是___
2.该树的叶子节点是________,内部节点是______________
3.度为1的节点数有__个，B的孩子节点是___, Q的兄弟节点是__
12
11
3
6
E F Z P C H
B G R Q D
3
E F G
P
小明写了一个100以内的正整数，让小红猜；
小红每猜一次，
小明会告诉她“猜大了”还是“猜小了”，
直到猜出正确的结果。
请问小红采用什么方法，
能用最少的次数猜出正确结果？
猜数游戏
答：用折半猜数法 效率最高
猜数游戏

50
小

75

25
大
小

12
大

37
小

62
大

88
. . . . . . . . . . . .
二叉树
2.1 二叉树的概念
二叉树是一个具有 n（n>=0）个节点的有限集合。
当 n=0时，二叉树是一棵空树；
当 n>0时，则是由根节点、左子树和右子树组成
由于左、右子树也是二叉树，因此子树也可以是空树
二叉树的典型特征：所有节点的度都小于等于2
二叉树的5种形态：
2.1 二叉树的概念
①
②
③
④
⑤
左子树
右子树
左子树
右子树
学习任务二
画一画：
有3个节点的二叉树有几种不同的形态？
学习任务二
画一画：
有3个节点的二叉树共有5种不同的形态















①
②
③
④
⑤
2.2 二叉树的分类
所有的叶子节点都在最底层，
除了叶子节点外，每个结点的度是 2
满二叉树
以下3个二叉树的共同特点是？
2.2 二叉树的分类
至多只有最下两层中的节点的度数小于2，
且最后一层的叶子结点都依次从左到右分布
完全二叉树
在满二叉树基础上去掉几个节点：
学习任务三
A.
B.
C.
D.
判一判： 下列4棵树是否为完全二叉树？
√
完全二叉树：至多只有最下两层中的节点的度数小于2，且最后一层的叶子结点都依次从左到右分布
满二叉树 VS 完全二叉树
1.满二叉树一定是完全二叉树
但完全二叉树不一定是满二叉树
2.满二叉树在最后一层从最后一个节点开始，
从右向左连续去掉任意个节点，即为完全二叉树
2.2 二叉树的分类
学习任务四
选一选：下列哪些是满二叉树，哪些是完全二叉树？
②
③
④
⑤
①
②是满二叉树
⑤是完全二叉树
二叉树有哪些性质呢？
因为满二叉树在同层二叉树中
拥有的节点数最多
我们以满二叉树为例来探究下
2.3 二叉树的性质
2.3 二叉树的性质
第①层：1个
第②层：2个
第③层：4个
第④层：8个
1.满二叉树中每层的节点数分别是？
. . . . . .第k层有几个节点？
第k层：2k-1个
20
21
22
23
2.3 二叉树的性质
性质1：
二叉树的第k层上最多有2k-1个节点
2.3 二叉树的性质
2.不同深度的满二叉树共有几个节点数？
深度为2
共有3个节点
深度为3
共有7个节点
深度为4
共有15个节点
. . . . . .深度为k的满二叉树共有几个节点？
2k-1个
2.3 二叉树的性质
性质2：
深度为k的二叉树最多有2k-1个节点
2.3 二叉树的性质
n0=4
n1=1
n2=3
n0=2
n1=1
n2=1
n0=3
n1=2
n2=2
n0=4
n1=3
n2=3
我们发现：n0=n2+1
①
②
③
④
3.数一数度为0、1、2的节点数分别是多少？
2.3 二叉树的性质
性质3：
在任意一棵二叉树中，度为2的节点数n2和度为0的节点数n0的关系是：n0=n2+1
2.3 二叉树的性质
性质1：
二叉树的第k层上最多有2k-1个节点
性质2：
深度为k的二叉树最多有2k-1个节点
性质3：
在任意一棵二叉树中，度为2的节点数n2和度为0的节点数n0的关系是：n0=n2+1
节点数n满足等式：n=n0+n1+n2 ①
边数B满足等式： B=n-1 ②
B=n0*0+n1*1+n2*2 ③
由①②③可推导出 n0=n2+1
请探究证明：
在任意一棵二叉树中，都满足 n0=n2+1
学习任务五
课堂小结
谢 谢！

展开更多......

收起↑