计算机软件基础第3章
- 格式：pdf
- 大小：473.92 KB
- 文档页数：13
法）
data child brother 节点结构
树，T’为T所对应的二叉树，则有： Ø T中结点与T’中的结点一一对应； Ø 若在T中d1是其父结点d 的第一个子结 点，则在T’中d1是d 的左子结点； Ø 若在T中di是其父结点d 的第i个子结点 (i>1)， di-1是d 的第i-1个子结点，则在T’ 中di是di-1的右子结点。
二叉树的遍历示例
•
前序遍历的递归算法
A B E F G H I J C D
前序遍历序列为： ABEFCGDHIJ 中序遍历序列为： EFBGCHIJDA 后序遍历序列为： FEGJIHDCBA
•
•
void preorder(TNODE *bt) { if (bt != NULL) { printf("%d ", bt->data); preorder(bt->lchild); preorder(bt->rchild); } }
3-6
第3章 非线性数据结构 —————————————————————————————
Huffman树的构造过程 Huffman树节点定义
typedef struct { char data; int weight; int lchild; int rchild; } huffnode; //字符值 //权重 //左子结点 //右子结点
二叉树称为满二叉树。 q 定义：若一棵深度为k的二叉树，每层结 点个数满足： Ø 第i 层（1≤i ≤k-1）上有2i-1个结点； Ø 第k 层只在右边连续缺若干结点； 则称此树为完全二叉树。 q 满二叉树也是完全二叉树。
完全二叉树的性质
q 性质4
完全二叉树的性质
q 性质5'：对一棵含有n个结点的完全二叉树的
q 树的带权路径长度
树中所有叶子结点的带
权路径长度之和。
WPL =
å
n
i=1
w i * li
其中wi为叶子结点 i 所带的权值；li 为叶子 结点 i 的带权路径长度。 q 最优二叉树 给定n个权值{ w1, w2, …, wn}， 构造具有n个分别带权为 w1, w2, …, wn 的 叶子的二叉树，其中带权路径长度WPL最 小的二叉树称为最优二叉树或Huffman树。
后序遍历的递归算法
void postorder(TNODE *bt) { if (bt != NULL) { postorder(bt->lchild); postorder(bt->rchild); printf("%d ", bt->data); } }
3.4 树与二叉树的转换
q 树的二叉树表示法规则：设T为一棵有序
3-2
第3章 非线性数据结构 —————————————————————————————
二叉树的存储结构
q 顺序存储结构：
Ø 数组表示
二叉树的数组表示
q 链式存储结构：
Ø 二叉链表表示
完全二叉树的数组表示
一般二叉树的数组表示
二叉树的二叉链表表示
q节点结构 lchild data rchild
二叉链表表示法示例
A
B
C
D
B
C
D
E
F
G
H
I
E
F
G
H
I
J
J
树的存储结构—多重链表
data child1 child2 ……
A
3.2 二叉树
一棵二叉树是n (n ³ 0) 个结点的有限集合，该集合或者为空 (n=0)，或者是由一个根结点和两棵互不 相交的，称为左子树和右子树的二叉树 组成。 q 特点：二叉树的度≤2；有序。
q 初始条件：n个盘上小下大顺序堆在1柱上。 q 游戏目标：将1柱上的n个盘全部移到3柱上，
保持上小下大。
q 游戏规则：一次移动一个盘，始终保持上小
下大顺序。可用另一个柱做暂存。
3-3
第3章 非线性数据结构 —————————————————————————————
算法思想
q 用hanoi(n,
Hanoi塔递归算法
具有n个结点的完全二叉树的深度为 ëlog2nû+1。 q 性质5 对一棵含有n个结点的完全二叉树的 结点自上而下从左到右顺序编号，则对于编 号为i（1≤i≤n）的结点，有： Ø 若i>1，则结点i的父结点的编号为ëi/2û；若 i=1，则结点i是根，无父结点； Ø 若2*i>n, 则结点i无左子结点;否则结点i的 左子结点的编号为2*i； Ø 若2*i+1>n, 则结点i无右子结点;否则结点i 的右子结点的编号为2*i+1。
森林与二叉树的转换
3.5 树的应用1—波兰表达式
q 表达式树：用非叶子结点表示运算符，
其子结点为运算对象（运算数或子表达 式），根运算符的优先级最低。 q 例：A*(B+C)+D-(E/F)
+
* A B + C D E
/
F
3-5
第3章 非线性数据结构 —————————————————————————————
第3章 非线性数据结构 —————————————————————————————
3.1 树的概念
第3章 非线性数据结构
q q q q q
p 树的递归定义
3.1 3.2 3.3 3.4 3.5
树的概念 二叉树 二叉树的遍历 树与二叉树的转换 树的应用
q 3.6 图的基本概念
q q
3.7 图的存储结构 3.8 图的遍历
#include <stdio.h> void hanoi(int n, int x, int y, int z) { /*将n个盘从x 柱移到z 柱，用y 柱暂存*/ if(n==1) printf("%d à %d\n", x, z); else { hanoi(n-1, x, z, y); //将n-1个盘从x移到y，z作暂存 printf("%d à %d\n", x, z); //将1个盘从x移到z hanoi(n-1, y, x, z); //将n-1个盘从y移到z，x作暂存 } return; } void main() { hanoi(4, 1, 2, 3); }
具有不同带权路径长度的二叉树
Huffman树的构造
1.
2.
在Huffman树中，权值大的结点离根最近。
3. 4.
由给定的n个权值{w1, w2, …, wn}，构造具有n 棵二叉树的集合 F = {T1, T2, …, Tn}，其中每 棵二叉树Ti只有一个带权为wi的根结点，其左 右子树均为空。 在F中选取两棵根结点的权值最小的树, 作为 左、右子树构造一棵新的二叉树。置新的二 叉树的根结点的权值为其左、右子树根结点 的权值之和。 在F中删去这两棵二叉树，并将新的二叉树加 入F。 重复步骤2和3，直到F中仅剩下一棵树为止。
3-4
第3章 非线性数据结构 —————————————————————————————
中序遍历的递归算法
void inorder(TNODE *bt) { if (bt != NULL) { inorder(bt->lchild); printf("%d ", bt->data); inorder(bt->rchild); } }
二元表达式的表示法
q 原表达式： A*(B+C)+D-(E/F) q 前缀表达式，表达式树的前序遍历序列：
波兰表达式的计算
q 从左到右扫描表达式，遇到运算符（n元）
-+*A+BCD/EF
q 中缀表达式，表达式树的中序遍历序列：
A*B+C+D-E/F
q 后缀表达式，也称逆波兰表达式，波兰表
达式，表达式树的后序遍历序列： ABC+*D+EF/-
就与前n个运算数作运算，结果作为运算 数取代原运算数与运算符。例： ABC+*D+EF/AT1*D+EF/T2D+EF/T3 EF/T3T4T5
树的应用2— Huffman树
相关术语： q 路径 两个结点之间的路径由两结点及连 接两结点之间的分支结点构成。 q 路径长度 路径上的边数。 q 树的路径长度 根结点到各叶子结点的路 径长度之和。 q 带权树 若树中结点赋有反映该结点的某 种特性的数据，则称此树为带权树。称与 结点相关联的数据为权。 q 结点的带权路径长度 由根结点到该结点 的路径长度与该结点的权的乘积。
树的术语
A
Ø 根结点 Ø 父结点 Ø 子结点 Ø 兄弟结点 Ø 叶子结点 Ø 分支结点 Ø 结点的度 Ø 树的度 Ø 结点的层次 Ø 树的深度 Ø 森林
前驱，其余节点都有一 个惟一的前驱；每个节 点可以有0~多个后继。 q 表示法：所有节点按前 驱后继关系从上至下分 层排列，根节点在最上 层。连线箭头均向下， 可忽略。
1, 2, 3)表示将n个盘从1柱移到3 柱，以2柱作暂存。该功能等价于： Ø hanoi(n-1, 1, 3, 2)：将n-1个盘从1柱移到2 柱，以3柱作暂存； Ø 将1个盘从1柱移到3柱； Ø hanoi(n-1, 2, 1, 3)：将n-1个盘从2柱移到3 柱，以1柱作暂存；
1
2
3
Hanoi塔的递归过程
q 树的遍历
按某种次序访问树中的结点， 要求每个结点访问一次且仅访问一次。 q 遍历的方式 按访问根结点的先后顺序分 为： Ø 前序遍历：访问根结点；前序遍历左 子树；前序遍历右子树。 Ø 中序遍历：中序遍历左子树；访问根 结点；中序遍历右子树。 Ø 后序遍历：后序遍历左子树；后序遍 历右子树；访问根结点。
data child brother 节点结构
树，T’为T所对应的二叉树，则有： Ø T中结点与T’中的结点一一对应； Ø 若在T中d1是其父结点d 的第一个子结 点，则在T’中d1是d 的左子结点； Ø 若在T中di是其父结点d 的第i个子结点 (i>1)， di-1是d 的第i-1个子结点，则在T’ 中di是di-1的右子结点。
二叉树的遍历示例
•
前序遍历的递归算法
A B E F G H I J C D
前序遍历序列为： ABEFCGDHIJ 中序遍历序列为： EFBGCHIJDA 后序遍历序列为： FEGJIHDCBA
•
•
void preorder(TNODE *bt) { if (bt != NULL) { printf("%d ", bt->data); preorder(bt->lchild); preorder(bt->rchild); } }
3-6
第3章 非线性数据结构 —————————————————————————————
Huffman树的构造过程 Huffman树节点定义
typedef struct { char data; int weight; int lchild; int rchild; } huffnode; //字符值 //权重 //左子结点 //右子结点
二叉树称为满二叉树。 q 定义：若一棵深度为k的二叉树，每层结 点个数满足： Ø 第i 层（1≤i ≤k-1）上有2i-1个结点； Ø 第k 层只在右边连续缺若干结点； 则称此树为完全二叉树。 q 满二叉树也是完全二叉树。
完全二叉树的性质
q 性质4
完全二叉树的性质
q 性质5'：对一棵含有n个结点的完全二叉树的
q 树的带权路径长度
树中所有叶子结点的带
权路径长度之和。
WPL =
å
n
i=1
w i * li
其中wi为叶子结点 i 所带的权值；li 为叶子 结点 i 的带权路径长度。 q 最优二叉树 给定n个权值{ w1, w2, …, wn}， 构造具有n个分别带权为 w1, w2, …, wn 的 叶子的二叉树，其中带权路径长度WPL最 小的二叉树称为最优二叉树或Huffman树。
后序遍历的递归算法
void postorder(TNODE *bt) { if (bt != NULL) { postorder(bt->lchild); postorder(bt->rchild); printf("%d ", bt->data); } }
3.4 树与二叉树的转换
q 树的二叉树表示法规则：设T为一棵有序
3-2
第3章 非线性数据结构 —————————————————————————————
二叉树的存储结构
q 顺序存储结构：
Ø 数组表示
二叉树的数组表示
q 链式存储结构：
Ø 二叉链表表示
完全二叉树的数组表示
一般二叉树的数组表示
二叉树的二叉链表表示
q节点结构 lchild data rchild
二叉链表表示法示例
A
B
C
D
B
C
D
E
F
G
H
I
E
F
G
H
I
J
J
树的存储结构—多重链表
data child1 child2 ……
A
3.2 二叉树
一棵二叉树是n (n ³ 0) 个结点的有限集合，该集合或者为空 (n=0)，或者是由一个根结点和两棵互不 相交的，称为左子树和右子树的二叉树 组成。 q 特点：二叉树的度≤2；有序。
q 初始条件：n个盘上小下大顺序堆在1柱上。 q 游戏目标：将1柱上的n个盘全部移到3柱上，
保持上小下大。
q 游戏规则：一次移动一个盘，始终保持上小
下大顺序。可用另一个柱做暂存。
3-3
第3章 非线性数据结构 —————————————————————————————
算法思想
q 用hanoi(n,
Hanoi塔递归算法
具有n个结点的完全二叉树的深度为 ëlog2nû+1。 q 性质5 对一棵含有n个结点的完全二叉树的 结点自上而下从左到右顺序编号，则对于编 号为i（1≤i≤n）的结点，有： Ø 若i>1，则结点i的父结点的编号为ëi/2û；若 i=1，则结点i是根，无父结点； Ø 若2*i>n, 则结点i无左子结点;否则结点i的 左子结点的编号为2*i； Ø 若2*i+1>n, 则结点i无右子结点;否则结点i 的右子结点的编号为2*i+1。
森林与二叉树的转换
3.5 树的应用1—波兰表达式
q 表达式树：用非叶子结点表示运算符，
其子结点为运算对象（运算数或子表达 式），根运算符的优先级最低。 q 例：A*(B+C)+D-(E/F)
+
* A B + C D E
/
F
3-5
第3章 非线性数据结构 —————————————————————————————
第3章 非线性数据结构 —————————————————————————————
3.1 树的概念
第3章 非线性数据结构
q q q q q
p 树的递归定义
3.1 3.2 3.3 3.4 3.5
树的概念 二叉树 二叉树的遍历 树与二叉树的转换 树的应用
q 3.6 图的基本概念
q q
3.7 图的存储结构 3.8 图的遍历
#include <stdio.h> void hanoi(int n, int x, int y, int z) { /*将n个盘从x 柱移到z 柱，用y 柱暂存*/ if(n==1) printf("%d à %d\n", x, z); else { hanoi(n-1, x, z, y); //将n-1个盘从x移到y，z作暂存 printf("%d à %d\n", x, z); //将1个盘从x移到z hanoi(n-1, y, x, z); //将n-1个盘从y移到z，x作暂存 } return; } void main() { hanoi(4, 1, 2, 3); }
具有不同带权路径长度的二叉树
Huffman树的构造
1.
2.
在Huffman树中，权值大的结点离根最近。
3. 4.
由给定的n个权值{w1, w2, …, wn}，构造具有n 棵二叉树的集合 F = {T1, T2, …, Tn}，其中每 棵二叉树Ti只有一个带权为wi的根结点，其左 右子树均为空。 在F中选取两棵根结点的权值最小的树, 作为 左、右子树构造一棵新的二叉树。置新的二 叉树的根结点的权值为其左、右子树根结点 的权值之和。 在F中删去这两棵二叉树，并将新的二叉树加 入F。 重复步骤2和3，直到F中仅剩下一棵树为止。
3-4
第3章 非线性数据结构 —————————————————————————————
中序遍历的递归算法
void inorder(TNODE *bt) { if (bt != NULL) { inorder(bt->lchild); printf("%d ", bt->data); inorder(bt->rchild); } }
二元表达式的表示法
q 原表达式： A*(B+C)+D-(E/F) q 前缀表达式，表达式树的前序遍历序列：
波兰表达式的计算
q 从左到右扫描表达式，遇到运算符（n元）
-+*A+BCD/EF
q 中缀表达式，表达式树的中序遍历序列：
A*B+C+D-E/F
q 后缀表达式，也称逆波兰表达式，波兰表
达式，表达式树的后序遍历序列： ABC+*D+EF/-
就与前n个运算数作运算，结果作为运算 数取代原运算数与运算符。例： ABC+*D+EF/AT1*D+EF/T2D+EF/T3 EF/T3T4T5
树的应用2— Huffman树
相关术语： q 路径 两个结点之间的路径由两结点及连 接两结点之间的分支结点构成。 q 路径长度 路径上的边数。 q 树的路径长度 根结点到各叶子结点的路 径长度之和。 q 带权树 若树中结点赋有反映该结点的某 种特性的数据，则称此树为带权树。称与 结点相关联的数据为权。 q 结点的带权路径长度 由根结点到该结点 的路径长度与该结点的权的乘积。
树的术语
A
Ø 根结点 Ø 父结点 Ø 子结点 Ø 兄弟结点 Ø 叶子结点 Ø 分支结点 Ø 结点的度 Ø 树的度 Ø 结点的层次 Ø 树的深度 Ø 森林
前驱，其余节点都有一 个惟一的前驱；每个节 点可以有0~多个后继。 q 表示法：所有节点按前 驱后继关系从上至下分 层排列，根节点在最上 层。连线箭头均向下， 可忽略。
1, 2, 3)表示将n个盘从1柱移到3 柱，以2柱作暂存。该功能等价于： Ø hanoi(n-1, 1, 3, 2)：将n-1个盘从1柱移到2 柱，以3柱作暂存； Ø 将1个盘从1柱移到3柱； Ø hanoi(n-1, 2, 1, 3)：将n-1个盘从2柱移到3 柱，以1柱作暂存；
1
2
3
Hanoi塔的递归过程
q 树的遍历
按某种次序访问树中的结点， 要求每个结点访问一次且仅访问一次。 q 遍历的方式 按访问根结点的先后顺序分 为： Ø 前序遍历：访问根结点；前序遍历左 子树；前序遍历右子树。 Ø 中序遍历：中序遍历左子树；访问根 结点；中序遍历右子树。 Ø 后序遍历：后序遍历左子树；后序遍 历右子树；访问根结点。
