当前位置:文档之家› 第7讲 树和二叉树讲解

第7讲 树和二叉树讲解

中序遍历(LDR)递归算法为: 若二叉树为空则算法结束;否则:
(1)中序遍历根结点的左子树; (2)访问根结点; (3)中序遍历根结点的右子树。
结点A的度:3 结点B的度:2 结点M的度:0
叶子:K,L,F,G,M,I,J
结点A的孩子:B,C,D
A
结点B的孩子:E,F
结点I的双亲:D 结点L的双亲:E
树的度:3
B
C
D
结点B,C,D为兄弟
E
F G H I J 结点K,L为兄弟
KL
结点A的层次:1 结点M的层次:4
M
树的深度:4
结点F,G为堂兄弟 结点A是结点F,G的祖先
一般树的遍历(续)
A
B
C
D
EFG
H
I
J K LM
NO
先序遍历:A B E F I G C D H J K L N O M
后序遍历: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
7.2二叉树的定义及特点 • 定义:

二叉树是结点的有限集合,这个集合或者是空
• 4 孩子兄弟表示法 • 孩子兄弟表示法就是用指针既表示出每个结
点的孩子结点,也表示出每个结点的兄弟结点。
root
A∧
B
C∧
∧D
E
∧F ∧
∧ G∧
∧H
∧ I∧
7.9 树的遍历及应用
• 树的用法之一就是许多操作系统中的目录结构
• 如果要列出目录中所有文件的名字,输出格式是:层次 为di的文件将在di次跳格(tab)缩进后打印其名
右子树 。 • 根据遍历算法访问根结点的次序,我们介绍三
种遍历算法分别为前序遍历(DLR)、中序遍历 (LDR)和后序遍历(LRD)。
• 前序遍历(DLR)递归算法为: • 若二叉树为空则算法结束;否
则: • (1)访问根结点; • (2)前序遍历根结点的左子树; • (3)前序遍历根结点的右子树。

leftChild
data
rightChild
• 二叉链存储结构的二叉树
• (a)不带头结点的二叉树 (b)带头结点 的二叉树
root
root

A
A
B∧
C
B∧
C
∧D
∧ E∧
∧ F∧
∧ G∧
∧D
∧ E∧
∧ F∧
∧ G∧
(a)
(b)
• 3 二叉树的仿真指针存储结构
• 二叉树的仿真指针存储结构是用数组存储 二叉树中的结点 。
• 二叉树的仿真二叉链存储结构

data leftChild rightChild
0
A
1
2
1
B
3
-1
2
C
4
5
3
D
-1
6
4
E
-1
-1
5
F
-1
-1
6
G
-1
-1
7.3 以结点类为基础的二叉树设计
• 7.3.1 二叉树结点类 • 7.3.2 二叉树的遍历 • 1 二叉树遍历的基本方法 • 一棵二叉树由三部分组成:根结点、左子树和
• 性质4 对于一棵非空的二叉树,如果叶结 点个数为n0,度为2的结点数为n2,则有n0= n2+1。
• 性质5 对于具有n个结点的完全二叉树,如果按照
从上至下和从左至右的顺序对所有结点从0开始顺序 编号,则对于序号为i的结点,有:
• (1)如果i>0,则序号为i结点的双亲结点的序 号为 (i-1)/2(“/”表示整除);如果i=0,则序号为 i结点为根结点,无双亲结点。
的双亲结点。 • 对于使用仿真指针的双亲表示法来说,
每个结点应有两个域,一个是数据元素域, 另一个是指示其双亲结点在数组中下标序号 的仿真指针域。
• 树及其使用仿真指针的双亲表示法
A BC DE F G HI
(a)
data 0A 1B 2C 3D 4E 5F 6G 7H 8I
parent -1 0 0 1 1 1 2 4 4
• 7.2.3 二叉树的性质
• 性质1 若规定根结点的层次为0,则一棵非 空二叉树的第i层上最多有2i(i≥0)个结点。
• 性质2 若规定空二叉树树的深度为-1(即根 结点的深度为0),则深度为k的二叉树的最大 结点数是2k+1-1(k≥-1)个。
• 性质3 具有n个结点的完全二叉树的深度k 为不超过log2(n+1)-1的最大整数。
● 哈夫曼树和哈夫曼编码,哈夫曼编码的软件设 计方法
● 树与二叉树的转换,树的遍历
7.1 树
• 7.1.1 树的定义 • 树是由n(n≥0)个结点构成的满足以下条件的结点集合: • (1)当n>0时,有一个特殊的结点称为根结点,根结点
没有前驱结点; • (2)当n>1时,除根结点外的其他结点被分成m(m>0)
• private void listAll(int depth)
• { printName(depth); //Print the name of the object;
• if(isDeirectory())
• for each file c in this directory (for each child)
• if(isDirectory())
• for each file c in this directory(for each
child)

totalSize+=c.size();
• return totalSize();
•}
A
B
C
D
E
F
G
H
I
J
K
L
先根遍历得到的结点序列为:A B E J F C G K L D H I 后根遍历得到的结点序列为:J E F B K L G C H I D A
• 7.1.2 树的表示方法 • 1 直观表示法
A
B
C
D
A
E
F
G
H
I
J
K
L
(a)
(b)
• 2 形式化表示法
• 树的形式化表示法主要用于树的理论描述。树 的形式化表示法定义树T为T=(D,R)其中D为 树T中结点的集合,R为树T中结点之间关系的集 合。当树T为空树时D=¢;当树T不为空树时有 D={Root}∪DF,其中Root为树T的根结点,DF 为树T的根Root的子树集合,DF可由下式表示:
(b)
• 2 孩子表示法 • 孩子表示法就是用指针表示出每个结点的孩子
结点。 • 常规指针的孩子表示法
root
A

B
C
∧∧
D ∧∧ ∧ E
F ∧
∧∧∧
G∧ ∧ ∧
H∧ ∧ ∧
I∧∧∧
• 3 双亲孩子表示法
• 双亲孩子表示法就是用指针既表示出每个
结点的双亲结点,也表示出每个结点的孩子结
点。
data parent head 0 A -1
部结点
树的基本术语
树的度——一棵树中最大的结点度数 孩子——结点子树的根称为该结点的孩子 双亲——孩子结点的上层结点叫该结点的双亲 兄弟——同一双亲的孩子之间互成为兄弟 祖先——结点的祖先是从根到该结点所经分支上
的所有结点 子孙——以某结点为根的子树中的任一结点都成
为该结点的子孙
A
A
B D
F (a)
C E
G
B D
F
C E
G (b)
数组 A B C ∧ D E ∧ ∧ ∧ F ∧ ∧ G 下标 0 1 2 3 4 5 6 7 8 9 10 11 12
(c)
2 二叉树的链式存储结构
• 二叉树的链式存储结构是用指针建立二叉
树中结点之间的关系。

二叉链存储结构的每个结点包含三个域 。
第7讲 树和二叉树
• 7.1 树 • 7.2 二叉树 • 7.3 二叉树的设计 • 7.4 线索二叉树 • 7.5树与二叉树的转换
• 本章主要知识点: ● 树的定义、表示方法和存储结构
● 二叉树的定义、性质和存储结构,满二叉树和 完全二叉树的概念
● 二叉树的前序、中序、后序和层序遍历算法 ● 二叉树中序和层序游标类的设计方法 ● 线索二叉树的基本概念
child next
1
2∧
1B 0
3
4
5∧
2C 0
6∧
3D
1

4E
1
7
8∧
5F
1

6G
2

7H
4

8I
4

• 4 孩子兄弟表示法 • 由于每个结点的孩子数可以变化很大并且事
先不知道,建立到各个孩子结点的链接不可行
• class TreeNode •{ • Object element; • TreeNode firstChild; //第一个孩子 • TreeNode nextSibling; //下一个兄弟 •}
• 2 后根遍历 • 树的后根遍历递归算法为: • (1)按照从左到右的次序后根遍历根结点的每一
棵子树;
• (2)访问根结点。
• 例如:计算文件系统某目录下所有文件占用的磁 盘区块的总数(由于目录也是文件,也有大小)
• public int size()
•{
• int totalSize=sizeOfThisFile();
• DF = D1∪D2∪…∪Dm (1≤i, j≤m, Di∩Dj=¢)
相关主题