当前位置：文档之家 › 树和二叉树 PPT课件

树和二叉树 PPT课件

  • 格式：ppt
  • 大小：1.04 MB
  • 文档页数：102

下载文档原格式

  / 102

合集下载

数据结构二叉树PPT课件

数据结构二叉树PPT课件

A
B
CX
E FGH I
J
8
四. 基本名词术语
1. 结点的度：该结点拥有的子树的数目。
2. 树的度：树中结点度的最大值。
3. 叶结点：度为0 的结点. 4. 分支结点: 度非0 的结点. 5. 层次的定义: 根结点为第一层,若某结点在第i 层,
则其孩子结点(若存在)为第i+1层.
A
第1层
B
CX
第2层
12
完全二叉树.
三.i 层最多有2i–1个结点(i1)。
2. 深度为h 的非空二叉树最多有2h -1个结点.
3. 若非空二叉树有n0个叶结点,有n2个度为2的结点,
则
n0=n2+1
4. 具有n个结点的完全二叉树的深度h=log2n+1.
13
二叉树的存储结构
39
例
A
BC D
E F GH I
对树进行先根遍历，获得的先根序列是： ABEFCDGHI
对树进行后根遍历，获得的后根序列是： EFBCGHIDA
40
2.森林的遍历
先序遍历(对森林中的每一棵树进行先根遍历)
1）若森林不空，访问森林中第一棵树的根结点； 2）先序遍历森林中第一棵树的子树森林； 3）先序遍历森林中(除第一棵树外)其余树构成的森林。
(空) 根 根 根
根
左 子 树
右 子 树
左 子 树
右 子 树
11
二. 两种特殊形态的二叉树
1. 满二叉树
若一棵二叉树中的结点, 或者为叶结点， 或者具有两 棵非空子树,并且叶结点都集 中在二叉树的最下面一层.这 样的二叉树为满二叉树.
2.完全二叉树
若一棵二叉树中只有最下 面两层的结点的度可以小于2, 并且最下面一层的结点(叶结 点)都依次排列在该层从左至 右的位置上。这样的二叉树为

第7章-树和二叉树第2讲-二叉树的概念

第7章-树和二叉树第2讲-二叉树的概念
（root），其余结点可分为m （m≥0）个互不相交的有限子集 T1、T2、…、Tm，而每个子集本身又是一棵树，称为根结点 root的子树。 树中所有结点构成一种层次关系！
第一层
树的特 点？
第二层 第三层 第四层
复习：二、树的基本术语
1.结点A、D的度？树的度？ 2;3;3; 2.根结点？分支结点？叶子结点？ A;BCDE;GHIJF;
在二叉链中，空指针的个数？
b A
B∧
C
∧D
∧E∧
∧F∧
∧G∧
n个结点 2n个指针域 分支数为n-1 非空指针域有n-1个 空指针域个数 = 2n-(n-1) = n+1
n=7 空指针域个数=8
39/10
40/10
二叉树
当n=3，结果为ห้องสมุดไป่ตู้。
第n个Catalan数
41/23
有n个结点并且高度为n的不同形态的二叉树个数是多少？ 该二叉树：有n层，每层一个结点，该结点可以
43/23
结点个数为n，树形可以唯一确定 叶子结点个数为n0，树形不能唯一确定 n为奇数时，n1=0； n为偶数时，n1=1。 n0=n2+1 高度h= log2(n+1)，是n个结点高度最小的二叉树
44/23
含有60个叶子结点的二叉树的最小高度是多少？
在该二叉树中，n0=60，n2=n0-1=59，n=n0+n1+n2=119+n1。 当n1=0且为完全二叉树时高度最小。 此时高度h=log2(n+1)= log2120=7。
作为双亲结点的左孩子，也可以作为右孩子 这样的二叉树的个数=1×2×…×2=2n-1。
例如，当n=3时有22=4个这样的二叉树。

第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

北京林业大学《数据结构与算法》课件PPT 第5章 树和二叉树

北京林业大学《数据结构与算法》课件PPT 第5章 树和二叉树

北京林业大学信息学院
A BC DE
先序遍历：A B D E C 中序遍历：D B E A C 后序遍历：D E B C A
口诀： DLR—先序遍历，即先根再左再右 LDR—中序遍历，即先左再根再右 LRD—后序遍历，即先左再右再根
北京林业大学信息学院
用二叉树表示算术表达式
+
*
E
*
D
/
C
A
B
北京林业大学信息学院
叉树。（特点：每层都 “充满”了结点）
完全二叉树：深度为k 的， 有n个结点的二叉树，当且
仅当其每一个结点都与深度
为k 的满二叉树中编号从1 至n的结点一一对应
北京林业大学信息学院
满二叉树和完全二叉树的区别
满二叉树是叶子一个也不少的树，而完全二叉树虽然 前n-1层是满的，但最底层却允许在右边缺少连续若 干个结点。满二叉树是完全二叉树的一个特例。
ADT BinaryTree{
数据对象D: D是具有相同特性的数据元素的集合。
数据关系R: 若D=Φ，则R= Φ ；
若D≠Φ，则R= {H}；存在二元关系：
① root 唯一 //关于根的说明
② Dj∩Dk= Φ //关于子树不相交的说明
③ ……
//关于数据元素的说明
④ ……
//关于左子树和右子树的说明
B n1
B n2 2 n1 1
n n2 2 n1 11 n2 n1 n0
北京林业大学信息学院
特殊形态的二叉树
1
只有最后一层叶子不满 ，且全部1 集中在左边
2
3
2
3
4
5
6
7
4
5
6
7

数据结构第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 树和森林 ❖树的存储结构——孩子兄弟表示法
或称二叉树表示法，或称二叉链表表示法。即以 二叉链表作树的存储结构。链表中结点的两个链域分 别指向该结点的第一个孩子结点和下一个兄弟结点。

第六章-树和二叉树

第六章-树和二叉树

之
树 和 二 叉 树 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]); }

第六章 树与二叉树

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

C
E
D
F
C
D
C

D
F
E F 二叉链表
E
二叉树
三叉链表
三叉链表的静态结构
root data parent lchild rchild 0 1 2 3 4 5 A B C D E F -1 0 1 1 3 3 1 2 -1 4 -1 -1 -1 3 -1 5 -1 -1
A
B C E D F
0
1 3 7 8 9 4 5
2 6
4. 二叉树的存储结构
顺序表示
1
2 4 5 6 3 7 7 4 8 2 5 9 1 3 6 10 9
8 9 10
1 2 3 4 5 6 7 8 910
完全二叉树 的顺序表示
1 2 3 4 0 5 6 7 8 0 0 0 0 910
一般二叉树 的顺序表示
链表表示
第六章 树和二叉树




1. 2. 3. 4. 5. 6.
树的定义和基本术语 二叉树 遍历二叉树与线索二叉树 树与森林 赫夫曼树 及其应用 二叉树的计数
6.1 树的定义和基本术语
树的定义
树是由 n (n 0) 个结点组成的有限集合。如果 n = 0， 称为空树；如果 n > 0，则 有且仅有一个特定的称之为根(Root)的结点，它只有直 接后继，但没有直接前驱； 当n > 1，除根以外的其它结点划分为 m (m >0) 个互不 相交的有限集 T1, T2 ,…, Tm，其中每个集合Ti本身又是一 棵树，并且称为根的子树(SubTree)。
特点
每个结点至多只有两棵非空子树（二叉树中 不存在度大于2的结点）
2.五种形态
L R L R
3. 性质
性质1 在二叉树的第 i 层上至多有 2i －1个结 点。(i 1) [证明用归纳法]
证明：当i=1时，只有根结点，2 i-1=2 0=1。 假设对所有j，i>j1，命题成立，即第j层上至多 有2 j-1 个结点。 由归纳假设第i-1 层上至多有 2i －2个结点。 由于二叉树的每个结点的度至多为2，故在第i层 上的最大结点数为第i-1层上的最大结点数的2倍， 即2* 2i －2= 2 i-1。
二叉链表的定义
typedef char TreeData; /*结点数据类型*/ typedef struct node /*结点定义*/ { TreeData data; struct node * lchild, * rchild; } BinTreeNode;
typedef BinTreeNode * BinTree; /*根指针*/
例如
A
A 只有根结点的树
B
C
D I J
E
K L
F
G H
M
有13个结点的树
其中：A是根；其余结点分成三个互不相交的子集， T1={B,E,F,K,L}； T2={C,G}； T3={D,H,I,J,M}, T1,T2,T3都是根A的子树，且本身也是一棵树
树的基本术语
A
B E K 结点的度 树的度 叶结点 分支结点 L F C G H M D I J
若设二叉树的高度为h，则共有h层。除第 h 层外， 其它各层 (1 h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。
1 2 完全二叉树 4 5 6
3
7 1
8 9 10 11 12 1 2 4 5 6 7 3) 个结点的完全二叉树 的深度为log2 n ＋1
1层
2层 3层 4层
树的深度 有序树 无序树 森林 height =4
子女 双亲 兄弟
祖先 子孙 结点层次
6.2 二叉树 (Binary Tree)
1.定义
一棵二叉树是由 n (n 0) 个结点组成的有 限集合。如果 n = 0，称为空二叉树；如果 n > 0， 则由一个被称为根的结点和两棵互不相交的分 别称为根的左子树和右子树的二叉树组成。
若i = 1, 则 i 无双亲
若i > 1, 则 i 的双亲为i/2 若2*i< n, 则 i 的左子女为 2*i，若2*i+1 < n, 则 i 的右子 女为2*i+1 若结点编号i为奇数，且i!=1,则左兄弟结点i-1. 若结点编号i为偶数，且i!=n,则右兄弟结点为i+1. 结点i 所在层次为log 2 i +1
性质2 深度为 k 的二叉树至多有 2 k-1 个结点(k 1)。
证明：由性质1可见，深度为k的二叉树的 最大结点数为
(第i层上的最大结点数）
i 1
k
＝ 2 i 1 ＝20 + 21 + … + 2 k-1 = 2 k-1
i 1
k
性质3 对任何一棵二叉树T, 如果其叶结点数 为 n0, 度为2的结点数为 n2,则n0＝n2＋1. 证明：若度为1的结点有 n1 个，总结点个数为 n， 总边数为 e，则根据二叉树的定义， n = n0 + n1 + n2 e = 2n2 + n1 n – 1= e 因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n0 = n2 + 1 n2 = n0 - 1
两种特殊形态的二叉树
定义1 满二叉树 (Full Binary Tree) 一棵深度为k且有2 k-1个结点的二叉树称为 满二叉树。(即每一层的结点数都达到最大值) 1 2 4 5 3
6
7
8 9 10 11 12 13 14 15
满二叉树
定义2 完全二叉树 (Complete Binary Tree)
lChild data rChild 含两个指针域的结点结构 lChild data parent rChild
含三个指针域的结点结构
data
lChild 二叉链表 rChild lChild
parent
data rChild 三叉链表
二叉树链表表示的示例
root A B B root A B root A
证明：设完全二叉树的深度为 h，则根据 性质2和完全二叉树的定义有 2h－1 - 1 < n 2h- 1或 2h－1 n < 2h 取对数 h－1 < log2n h，又h是整数， 因此有 h = log2 n ＋1
性质5 如将一棵有n个结点的完全二叉树自顶向
下，同一层自左向右连续给结点编号1, 2, …, n， 则有以下关系：