下一页
计算机软件基础
The software basic
of computer
主讲：刘志强
西安交通大学
计算机教学实验中心
第 4单元
非线性数据结构
树、二叉树
下一页
上一页
停止放映
第 2 页
教学目标
? 了解树, 二叉树,
– 基本概念
– 逻辑结构
– 存储结构及实现
– 遍历算法
– 特殊二叉树的表示及性质
下一页
上一页
停止放映
第 3 页
教学要求
通过本单元的学习，了解、掌握：
? 树、二叉树的基本概念
? 树、二叉树的存储结构及实现
? 二叉树的遍历操作及有关算法
? 特殊二叉树的表示及性质
? 树、森林、二叉树的转换
下一页
上一页
停止放映
第 4 页
本单元涉及的内容
第 3章
3.1,树形结构及基本概念
3.2,二叉树
3.3,二叉树的遍历
3.4树, 森林与二叉树的转换
(P81~P90)
下一页
上一页
停止放映
第 5 页
一、树型结构及其基本概念
? 树形结构基本概念包括的内容：
– 树的定义
– 树的基本概念
?结点, 根, 叶, 路径, 结点度,
树的度
?结点的层次, 子结点, 父结点
?有序, 无序
下一页
上一页
停止放映
第 6 页
树形结构
? 树形结构是以分支关系来定义的层次结
构 。 在客观世界中树形结构广泛存在,
并应用于：
– 人类社会的族谱, 家谱, 行政区域划
分管理；
– 各种社会组织机构；
– 在计算机领域中, 用树表示源程序的
语法结构；
– 在 OS中, 文件系统, 目录等组织结构
也是用树来表示的 。
下一页
上一页
停止放映
第 7 页
树的定义 （逻辑结构）
? 树是一种数据结构：
Tree=（ D,R）
其中：
D 是具有相同特性的数据元素的集合；
R 是 D上逻辑关系的集合, 且满足：
– 在 D中存在唯一的称为根的数据元素, 没
有前趋；
– D中其余数据元素都有且只有一个前趋；
– D中所有元素, 或有若干个互不相同的后
继 （ 子树 ）, 或无后继 （ 叶结点 ） ；
则称 Tree为树 。
下一页
上一页
停止放映
第 8 页
树的定义 （递归结构）
? 树是一个或多个结点组成的有限集合
T,有一个特定结点称为根, 其余结
点分为 m（ m?0） 个互不相交的集合
T1,T2,…,Tm。 每个集合又是一棵
树, 被称为这个根的子树 。
? 树是一种递归结构, 可以包含一个结
点, 该结点包含不相交的树的指针
（ 即子树 ） 。
下一页
上一页
停止放映
第 9 页
树结构举例
书目录 目录树 树结构
C1（ 章 ） BOOK ?
S1.1(节 )
S1.2 C1 C2 C3 ? ? ?
C2
S2.1 S1.1 S1.2 S2.1 S2.2 S2.3 ? ? ? ? ?
S2.11
S2.12
S2.2 S2.1.1 S2.1.2 ? ?
S2.3
C3
下一页
上一页
停止放映
第 10 页
树的表示形式
(1) 一般形式
(2) 嵌套形式
(3) 凹入形式
(4) 广义表形式
下一页
上一页
停止放映
第 11 页
树的表示 (一般形式 )
A
B C D
E F
K L
G H I J
M
A
(a) (b)
(a)只有根结点的树 (b)一般的树
下一页
上一页
停止放映
第 12 页
树的表示 (嵌套形式 )
A
C
G
B
F
E
K L M
H D
J I
下一页
上一页
停止放映
第 13 页
树的表示 (凹入形式 )
A
B
E
K
L
C
D
F
G
H
I
J
M
下一页
上一页
停止放映
第 14 页
树的表示 (广义表形式 )
( A ( B ( E (K,L),F),C(G),D( H (M),I,J )))
第一层
第二层
第三层
第四层
下一页
上一页
停止放映
第 15 页
基本术语
? 结点, 结点度, 根, 支, 叶结点
? 子结点, 父结点, 兄弟结点
? 树的度, 路径, 长度, 高度, 深度
? 森林, 有序, 无序
下一页
上一页
停止放映
第 16 页
结点（ Node）
? 结点 包括一个数据元素及若干个指向其它子
树的分支；例如, A,B,C,D等 。
? 结点度 结点拥有的子树数；例如, A的度为 3。
? 根结点 无前趋结点为根；例如, A结点 。
? 支结点 度不为 0的结点为支结点；如 B,C,D
等 。
? 叶结点 无后继结点为叶；如 K,L,M。
? 树的度 树中结点的最大度数；上述树的度为 3。
下一页
上一页
停止放映
第 17 页
基本术语 （二）
? 子结点 某结点子树的根为该结点的子结点；
例如, 结点 A的子结点为 B,C,D。
? 父结点 相对于某结点子树的根, 称该结点为
子树根的父结点；例如子结点 C,B,D的父结
点为 A。
? 兄弟结点 同一父亲的孩子之间互为兄弟结点
（ Sibling） ； H,I,J互为兄弟 。
? 路径 结点的序列 n1,n2,…,nk(K?1)是一条
路径,
? 长度 长度等于路径中结点数 -1.
下一页
上一页
停止放映
第 18 页
基本术语 （三）
? 高度 从一结点到叶结点的最长路径为该结
点的高度；例如, 结点 A到 M的高度为 4。
? 深度 从根结点到某结点的路径为该结点的
深度； M的深度为 4。
? 森林 0棵或多棵互不相交的树的集合 。 对
树中每个结点而言, 其子树的集合即为森林 。
? 有序 如果将树中结点的各子树看成从左至
右是有顺序的 （ 即不能互换 ）, 则称该树为
有序树 。 否则, 称为无序树 。
下一页
上一页
停止放映
第 19 页
树的操作
? PARENT（ n,T） 得到树中 n的父亲结点；
? ROOT（ T） 求树的根, 返回树根的位置 。
? CHILD（ T,x,i） 求树 T中结点 x的第 i个孩子
结点 。
? CREATE（ x,T1,T2,…,Tk) 生成一个结点 x,
下带子树 T1,T2,…,Tk。
? DELETE(x,i) 删除结点 x的第 i个子树 。
? TRAVERSE（ T） 遍历树 T。 按次序依此访问树
中各个结点, 且使每个结点只能被访问一次 。
下一页
上一页
停止放映
第 20 页
树的实现 (存储结构 )
? 数组实现方法 （ 双亲表示法 ）
? 链表实现方式 （ 孩子表示法 ）
? 二叉链表实现方式 （ 孩子兄弟表
示法 ）
下一页
上一页
停止放映
第 21 页
树的存储结构 (一）
? 数组实现方法（双亲表示法）
用数组存储树的结点信息, 在每个结点中附设一个指示器
指示其双亲结点在数组中的位置 。 结构描述：
#define MAXSIZE 100
typedef struct PTNode{
TElemType data；
int parent ；
} PTNode；
typedef struc {
PTNode nodes[MAXSIZE]；
int n；
} Ptree；
下一页
上一页
停止放映
第 22 页
双亲表示法举例
1
2 3
4 5 6
7 8 9
结点序号
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
0 1 1 2 2 3 5 5 5
方法特点：
找根容易，找子结点难，
要遍历整个数组。
下一页
上一页
停止放映
第 23 页
树的存储结构（二）
? 链表实现方式（孩子表示法）
把每个结点的孩子结点排列起来，组成一个线性表，
且以单链表作为存储结构，则 n个结点有 n个孩子链表。
? 结构描述为：
typedef struct CTNode{ typedef struct {
int child； CTBox nodes[MAXSIZE]；
struct CTNode *next,int n,r；
} *Childptr； } Ctree；
typedef struct {
TElemType data；
Childptr firstchild；
} CTBox；
下一页
上一页
停止放映
第 24 页
孩子表示法举例
1
2 3
4 5 6
7 8 9
1
2
3
4
5
6
7
8
9
2 3 ^
4 5 ^
6 ^
^
^
^
^
^
7 8 9 ^
方法特点,
便于实现对孩子的操
作,却不便于对父亲
的操作,
下一页
上一页
停止放映
第 25 页
树的存储结构（三）
? 二叉链表实现方式 （ 孩子兄弟表示法 ）
以二叉链表作为树的存储结构 。 链表中结点的两个链域
分别指向该结点的第一个孩子结点和下一个兄弟结点 。
结构描述为：
typedef struct CSNode{
ElemType data；
struct CSNode *firstchild, *netsibling；
} CSNode,* CSTree；
下一页
上一页
停止放映
第 26 页
孩子兄弟表示法举例
1
2 3
4 5 6
7 8 9
1
2
^
3
7
4 5 6
8 9
^
^
^
^^
^ ^^
方法特点,
这种存储结构便于实
现各种树的操作,
^
下一页
上一页
停止放映
第 27 页
二、二叉树结构
二叉树是另一类重要的非线性结构 。
– 二叉树的定义
– 二叉树的性质
– 二叉树的存储结构
– 特殊二叉树
– 二叉树的遍历操作
– 表达式树及应用
– 树, 森林与二叉树的转换
下一页
上一页
停止放映
第 28 页
1、二叉树的定义
? 二叉树是另一种树形结构：
Binary_Tree =( D,R)
其中,
D 是具有相同性质的数据元素的集合 ;
R 是在 D上某个两元关系的集合,且满足,
– D中存在唯一称为根的数据元素,没有前趋 ;
– D中其余元素都有且仅有一个前趋 ;
– 每个结点至多只有两个子树 ;
– D中元素,或有两个互不相交后继,或无后继 ;
– 左, 右子树分别又是一棵二叉树 。
下一页
上一页
停止放映
第 29 页
二叉树定义（二）
? 定义
n个结点的集合 （ n?0）
T 的度 ? 2
T = 所有子树都有左, 右之分
（ 次序不能任意颠到 ）
下一页
上一页
停止放映
第 30 页
二叉树的五种基本形态
（ a）
（ b）
（ c）
（ d）
（ e）
O 空结点
O 单个结点
O
O
右子树为空
的二叉树
O
O
左子树为空
的二叉树
O
O O
左、右子树
非空的二叉
树
下一页
上一页
停止放映
第 31 页
二叉树与树的区别
? 表达形式 （ 对 3个结点 ）
普通树
二叉树
（ a） （ b） （ c） （ d） （ e）
O
O O
O
O
O有两种不同形式
（ a） （ b）
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O有五种不同形式
下一页
上一页
停止放映
第 32 页
二叉树与树的区别 （二）
? 观念
– 二叉树是一种特定的树结构, 但
不是普通树的特殊情况；
– 二叉树可以为空；而树则不能为
空；
– 二叉树的结点的子树分左子树和
右子树, 而树则无此区分 。
下一页
上一页
停止放映
第 33 页
2、二叉树的性质
? 性质一
二叉树的第 i层上至多有 2i-1 个结点 （ i ? 1） 。
利用归纳法证明：
– i=1时, 只有一个结点, 对的；
– 假设对所有的 j,1? j ? i,命题成立,
即在第 j层上, 至多有 2j-1 个结点 。
– 由归纳假设, 第 i-1层上至多有 2i-2 个结点 。
由于二叉树的每个结点的度至多为 2,故第 i
层上的最大结点数为第 i-1层上的最大
结点数的 2倍, 即 2X2i-2 = 2i-1。
下一页
上一页
停止放映
第 34 页
二叉树的性质（二）
? 性质二
深度为 k的二叉树上最多含有 2k-1个结点
（ k ? 1） 。
由性质一可见, 深度为 k的二叉树的最大结
点数为：
? （ 第 i层上的最大结点数 ）
= ? 2i-1 = 2k - 1
k
i=1
i=1
k
下一页
上一页
停止放映
第 35 页
验证二叉树的性质
1
2 3
8
65 74
109 11 12 13 14 15
?该二叉树的第 3层有 23-1 个结点,
?该二叉树深度为 4,最多有 24 -1 个结点,
下一页
上一页
停止放映
第 36 页
3、二叉树的存储结构
? 顺序存储 （ 一维数组 ）
? 记录数组结构
? 链式存储结构
– 二叉链表
– 三叉链表
下一页
上一页
停止放映
第 37 页
顺序存储（一维数组）
? 用数组存放
存储描述为：
#define MAXSIZE 100；
typedef TElemType SBTree[MAXSIZE]；
SBTree bt；
? 查找不便 。
a1 a2 a3 a4,.,an
下一页
上一页
停止放映
第 38 页
记录数组结构
? 存储结构描述,
#define MAXSIZE 100;
typedef struct SBNode {
TElemType data ;
int Lchild,Rchild;
} SBNode;
typedef struct｛
SBNode nodes[MAXSIZE];
} SBTree;
下一页
上一页
停止放映
第 39 页
记录数组结构举例
1
2 6
3 4
5
1 2 6
2 3 4
3 0 5
4 0 0
5 0 0
6 0 0
结点 左子 右子
特点,
找子方便,找父
结点不便,
下一页
上一页
停止放映
第 40 页
二叉链表存储结构
data leftp rightp
左指针 数据 右指针
A
B
C D
E F
G
A
B
DC
E F
G
^
^^
^
^ ^
^ ^
特点,
找子易,找父难,
下一页
上一页
停止放映
第 41 页
三叉链表存储结构
parent data rightp
左指针 数据 父结点 右指针
A
B
C D
E F
G
C ^^
^
^
^ ^
特点,
找子、找父都易 。
leftp^^A
B
D
E
G ^
F
下一页
上一页
停止放映
第 42 页
4、特殊二叉树
? 满二叉树
? 完全二叉树
? 平衡二叉树
? 二叉排序树
下一页
上一页
停止放映
第 43 页
满二叉树
? 若 k为二叉树 T的深度, 且 T中共有 2k-1个
结点 （ k ? 1）, 则称 T为满二叉树 。
（ a） 满二叉树 （ b） 非满二叉树
O
O O
O O O O
O
O
O O
O
O
下一页
上一页
停止放映
第 44 页
满二叉树的性质
? 若对满二叉树从第 1层开始,自上而下, 从左至右
给每个结点从 1开始编号的话, 则称深度为 k的满
二叉树的结点编号满足：
– 对某结点 i（ 1? i ? 2k -1 -1）, 其左子树的
编号为 2*i（ 偶数 ）, 其右子树的编号为
2* i +1（ 奇数 ） ； （ 非叶结点 ）
– 若 i>1,则结点 i父结点的编号为 i/2(整除 )。
? 根据这一性质, 可用一维数组存储满二叉数的结
点数据 。 知道一个结点的编号, 经计算就能求出
左, 右子树的根及父结点的编号 。
下一页
上一页
停止放映
第 45 页
满二叉树存储举例
1
4
32
5 76
1 2 3 4 5 6 7
1 2 3 4 5 6 7
?第 i个结点就存放在第 i个位置上；
?第 i个结点（ i>1)的父结点就存放在第
i/2个位置 ;
?第 i个结点（ i?2k -1 - 1)的左子结点就存放
在 第 2*i的个位置 ;右子存放在第 2*i+1位置,
下一页
上一页
停止放映
第 46 页
完全二叉树
? 深度为 k的二叉树 T,每层结点数目若满足,
– 第 i层 (1 ? i ? k-1)上的结点个数均为 2i-1(非
叶结点 );
– 第 k层从右边连续缺若干个结点 (即只能从右
至左不间断缺少 );
称这样的树为完全二叉树 。
? （ a） 完全二叉树 （ b） 非完全二叉树
? 特点, 叶结点只可能出现在层次最大的两层上,
O
O O
O O O
O
O
O
O
O
下一页
上一页
停止放映
第 47 页
完全二叉树的性质
? 设完全二叉树的结点总数为 n,深度为 k,某结点
编号为 i（ 1 ?i ? n ）, 则有：
– 若 i>1,则结点 i的双亲结点的编号为 i /2;
– 若 2* i ? n,则结点 i 的左子结点的编号为 2*
i,否则,结点 i为叶结点 ;
– 若 2* i +1? n,则结点 i 的右子结点的编号为
2*i+1,否则,结点 i为叶结点,
? 同理,完全二叉树也可以采用一维树组作为存储
结构,且方法完全同满二叉树,只不过 n ? 2k -1
罢了,
下一页
上一页
停止放映
第 48 页
平衡二叉树
? 二叉树上任一结点的左子树深度减去右子
树深度的差值, 称为该结点的平衡因子 。
? 任意结点左, 右子树的深度之差的绝对值
?1, 这样的树称为平衡二叉树 。
? （ a） 平衡二叉树 （ b） 非平衡二叉树
O
O
O
O
O
O
O
O
O
O O
O
O
O
下一页
上一页
停止放映
第 49 页
二叉排序树定义（一）
? 二叉排序树
– 或者是空二叉树；
– 或者是：
?左子树上所有结点的值均小于
根结点的值；
?右子树上所有结点的值均大于
等于根结点的值；
– 左, 右子树本身又是一棵二叉排
序树 。
下一页
上一页
停止放映
第 50 页
二叉排序树定义（二）
? X是二叉排序树 T中的一个结点；
– 所有的左后裔小于 X；
– 所有的右后裔大于等于 X；
– T可以为空树；
? T称为二叉排序树 。
（ a） 二叉排序树 （ b） 非二叉排序树
10
5
7 12
14
18
15
15
14 18
5
10
12
13
7
下一页
上一页
停止放映
第 51 页
5、二叉树的 遍 历
? 遍 历 （ Traversing） 是树形结构的一种重
要运算, 即按一定的次序系统地访问结构
中的所有结点, 使每个结点只被访问一次 。
? 遍 历的方法很多, 常用的有：
– 前序法 （ PreOrder）
– 中序法 （ InOrder）
– 后序法 （ PostOrder）
下一页
上一页
停止放映
第 52 页
前序法（ PreOrder）
? 方法描述：
– 从根结点 a开始访问,
– 接着访问左子结点 b，
– 最后访问右子结点 c。
? 即：
根
左子 右子
a
b c
下一页
上一页
停止放映
第 53 页
中序法（ InOrder）
? 方法描述：
– 从左子结点 b开始访问,
– 接着访问根结点 a，
– 最后访问右子结点 c。
? 即：
根
左子 右子
a
b c
下一页
上一页
停止放映
第 54 页
后序法（ PostOrder）
? 方法描述：
– 从左子结点 b开始访问,
– 接着访问右子结点 c，
– 最后访问根结点 a。
? 即：
根
左子 右子
a
b c
下一页
上一页
停止放映
第 55 页
二叉树的遍历举例
o
o o
o o
o
o
o o
A
B C
D E F
G H I
?前序遍历序列,ABDEGCFHI
?中序遍历序列,DBGEACHFI
?后序遍历序列,DGEBHIFCA
下一页
上一页
停止放映
第 56 页
二叉树遍历算法
? 二叉树 遍 历方法分为：
– 递归算法
– 非递归算法
? 递归算法和非递归算法中又分：
– 前序法
– 中序法
– 后序法
下一页
上一页
停止放映
第 57 页
二叉树遍历算法 （递归算法）
?二叉链表的 C语言描述：
struct tnode {
int data；
struct tnode *lchild,*rchild ；
} ；
typedef struct tnode TNODE;
下一页
上一页
停止放映
第 58 页
二叉树遍历算法 （递归、前序法程序）
? void preorder_t (TNODE *root)
{ if ( root != NULL )
{ printf(“%d \n”,root->data);
if (root->lc!=NULL)
proorder_t(root->lc);
if (root->rc!=NULL)
proorder_t(root->rc);
}
}
? 前序遍历二叉树的序列为：
A B C D E F
A
B
C D
E F
下一页
上一页
停止放映
第 59 页
二叉树 遍 历算法 （递归、前序法程序验证）
? 打印 A
– 取 A?.左子 (B)
– 打印 B
? 取 B?.左子 (C)
? 打印 C
– 取 C?.左子 (空 )
– 取 C?.右子 (空 )
? 取 B?.右子 (D)
? 打印 D
– 取 D?.左子 (E)
– 打印 E
? 取 E?.左子 (空 )
? 取 E?.右子 (空 )
– 取 D?.右子 (F)
– 打印 F
? 取 F?.左子 (空 )
? 取 F?.右子 (空 )
– 取 A?.右子 (空 )
? 结束
A
B C
D E
F
下一页
上一页
停止放映
第 60 页
二叉树 遍 历算法 （非递归算法 -前序法）
? 算法步骤,
– step1 初始化,置栈为空 (top=-1),
工作变量 p指向 root;
– step2 p非空 (p!=NULL)
或栈非空 (top!=-1)循环 ;
– step3 p非空循环 ; 访问 p(打印 p->data);
– step4 当前元素进栈,p取 p->lc;
执行 step3；
– step5 p为空, 栈非空, 则出栈,
p取 p->rc,返回 step2.
下一页
上一页
停止放映
第 61 页
二叉树 遍 历算法 （非递归算法 -前序法程序）
#define N m
void preorder_t(TNODE * root)
{ TNODE *p,*stack[N]; int top=-1;
p=root;
while ((p!= NULL)||(top!= -1))
{ while ( P!=NULL)
{ printf(“%d\n”,p->data);
top ++; stack[top]=p;
p=p->lc;
}
if ( top !=-1)
{ p=stack[top]; top - - ;
p=p->rc;
}
}
}
下一页
上一页
停止放映
第 62 页
二叉树 遍 历算法 （非递归、前序法程序验证）
? 打印 A
– A进栈, 取 A?.左子 ( B )
– 打印 B
? B进栈，取 B?.左子 ( C )
? 打印 C
– C 进栈,取 C?.左子 ( 空 )
– C 退栈,取 C?.右子 ( 空 )
? B 退栈,取 B?.右子 ( D )
? 打印 D
– D进栈，取 D?.左子 ( E )
– 打印 E
? E进栈，取 E?.左子 ( 空 )
? E退栈,取 E?.右子 ( 空 )
– D退 栈，取 D?.右子 ( F )
– 打印 F
? F进栈，取 F?.左子 ( 空 )
? F退栈,取 F?.右子 ( 空 )
– A退 栈，取 A?.右子 ( 空 )
? 结束
F
E
D
CB
A
下一页
上一页
停止放映
第 63 页
6、表达式树及应用
? 在计算机中对表达式进行分析和计算是一项重要的任务 。
? 举例, 用二叉树表示表达式：
a + b * （ c - d ） － ｅ ／ｆ
前序遍历序列：－＋ａ＊ｂ－ｃｄ／ｅｆ
中序遍历序列：ａ＋ｂ＊ｃ－ｄ－ｅ／ｆ
后序遍历序列：ａｂｃｄ－＊＋ｅｆ／－
? 分析：
– 每个叶结点为运算对象；
– 每个非叶结点为运算符；
– 每个子树对应一个子表达式 。
? 表达式处理一般采用后序法, 也称, 逆波兰, 法 。
? 表达式处理规则：
– 见运算数入栈；
– 见运算符, 取两个栈顶元素运算后再压栈；
– 直到处理结束 。
－
＋ ／
－ e f＊
b －
c d
a
下一页
上一页
停止放映
第 64 页
表达式树应用举例
（ 1） a b c d 入栈,
（ 2） 遇 ‘ -’,c d 出栈,
运算后再压栈；
（ 3） 遇 ‘ *’, （ c - d） 和 b 出栈,
运算后再压栈；
（ 4） 遇 ‘ +’,b*（ c-d） 和 a出栈,
运算后再压栈；
（ 5） e f 入栈；
（ 6） 遇 ‘ /’,f e 出栈,
运算后再压栈；
（ 7） 遇 ‘ -’,a+b*（ c-d）
和 e/f出栈,
运算后再压栈 。
d
c
b
a
（ 1） （ 2） c - d
b
a
（ 3） b*（ c-d）a
（ 5）
a+b*（ c-d）（ 4）
a+b*（ c-d）
f
e （ 6） e/f
a+b*（ c-d）
（ 7） a+b*（ c-d） - e/f
下一页
上一页
停止放映
第 65 页
7、树、森林与二叉树的转换
? 由于二叉树的存储结构比较简单, 处
理起来也比较方便, 所以有时需要把
复杂的树, 转换为简单的二叉树后再
作处理 。
? 树转换成二叉树
? 森林转换成二叉树
下一页
上一页
停止放映
第 66 页
树转换成二叉树
? 操作算法：
– 保留一个结点的最左子结点；
– 抹掉其余兄弟结点与上级结点的连线；
– 将兄弟结点连在一起；
– 以根为轴, 顺时针旋转一个角度 。
? 举例,o
o
o
o
o o o
o
o o
o o o o
加线 抹线
o
o o
o o o o
旋转
o
o
o
o
o o
o
下一页
上一页
停止放映
第 67 页
森林转换成二叉树
? 操作算法：
– 将森林中每棵树的树根连接起来；
– 将每棵树转换成对应的二叉树；
– 以森林中第一棵树的根为轴顺时针旋转一个角度 。
? 举例 o
o o
o
o o
o o o
o
连线
o
o o
o
o o
o o o
o
抹线o o o
o o
o
o o o
o旋转
oo
o
oo oo
o
oo
下一页
上一页
停止放映
第 68 页
将二叉树还原成树
? 将二叉树还原成树的操作步骤为：
step1 若某结点是其双亲的左子，则
把该结点的右子、右子的右子,…,都
与该结点的双亲结点用线连起来；
step2 删除原二叉树中所有的双亲结
点与右子结点的连线；
step3 整理 1,2两步所得到的树或森
林，使之结构层次分明。
下一页
上一页
停止放映
第 69 页
举例
A
B
E C
F D
G
A
B
E C
F D
G
（ a）二叉树 （ b）加连线
A
B
E C
F D
G
（ c）删除与
右子的连线A
B
E
C
F
D
G （ d）还原后的树
下一页
上一页
停止放映
第 70 页
作业、思考题
1、本单元 作业：
5,6,7,9,11
2、作业要求：
– 提交数字化作业，按要求提交到
指定路径下
– 用 C语言描述
– 作业命名方式为：
学号,章数 _序号
下一页
上一页
停止放映
第 71 页
结束语
? 欢迎对数字化教学法提出意见，以利改进。
? 我的 E-mail地址：
fcliu@xjtu.edu.cn
? 数字化课件的路径,
jec254\user2\tools\lzq\软件基础
? 作业提交路径：
jec251\user\dataroom\homework\班级编号
谢谢，再见！
计算机软件基础
The software basic
of computer
主讲：刘志强
西安交通大学
计算机教学实验中心
第 4单元
非线性数据结构
树、二叉树
下一页
上一页
停止放映
第 2 页
教学目标
? 了解树, 二叉树,
– 基本概念
– 逻辑结构
– 存储结构及实现
– 遍历算法
– 特殊二叉树的表示及性质
下一页
上一页
停止放映
第 3 页
教学要求
通过本单元的学习，了解、掌握：
? 树、二叉树的基本概念
? 树、二叉树的存储结构及实现
? 二叉树的遍历操作及有关算法
? 特殊二叉树的表示及性质
? 树、森林、二叉树的转换
下一页
上一页
停止放映
第 4 页
本单元涉及的内容
第 3章
3.1,树形结构及基本概念
3.2,二叉树
3.3,二叉树的遍历
3.4树, 森林与二叉树的转换
(P81~P90)
下一页
上一页
停止放映
第 5 页
一、树型结构及其基本概念
? 树形结构基本概念包括的内容：
– 树的定义
– 树的基本概念
?结点, 根, 叶, 路径, 结点度,
树的度
?结点的层次, 子结点, 父结点
?有序, 无序
下一页
上一页
停止放映
第 6 页
树形结构
? 树形结构是以分支关系来定义的层次结
构 。 在客观世界中树形结构广泛存在,
并应用于：
– 人类社会的族谱, 家谱, 行政区域划
分管理；
– 各种社会组织机构；
– 在计算机领域中, 用树表示源程序的
语法结构；
– 在 OS中, 文件系统, 目录等组织结构
也是用树来表示的 。
下一页
上一页
停止放映
第 7 页
树的定义 （逻辑结构）
? 树是一种数据结构：
Tree=（ D,R）
其中：
D 是具有相同特性的数据元素的集合；
R 是 D上逻辑关系的集合, 且满足：
– 在 D中存在唯一的称为根的数据元素, 没
有前趋；
– D中其余数据元素都有且只有一个前趋；
– D中所有元素, 或有若干个互不相同的后
继 （ 子树 ）, 或无后继 （ 叶结点 ） ；
则称 Tree为树 。
下一页
上一页
停止放映
第 8 页
树的定义 （递归结构）
? 树是一个或多个结点组成的有限集合
T,有一个特定结点称为根, 其余结
点分为 m（ m?0） 个互不相交的集合
T1,T2,…,Tm。 每个集合又是一棵
树, 被称为这个根的子树 。
? 树是一种递归结构, 可以包含一个结
点, 该结点包含不相交的树的指针
（ 即子树 ） 。
下一页
上一页
停止放映
第 9 页
树结构举例
书目录 目录树 树结构
C1（ 章 ） BOOK ?
S1.1(节 )
S1.2 C1 C2 C3 ? ? ?
C2
S2.1 S1.1 S1.2 S2.1 S2.2 S2.3 ? ? ? ? ?
S2.11
S2.12
S2.2 S2.1.1 S2.1.2 ? ?
S2.3
C3
下一页
上一页
停止放映
第 10 页
树的表示形式
(1) 一般形式
(2) 嵌套形式
(3) 凹入形式
(4) 广义表形式
下一页
上一页
停止放映
第 11 页
树的表示 (一般形式 )
A
B C D
E F
K L
G H I J
M
A
(a) (b)
(a)只有根结点的树 (b)一般的树
下一页
上一页
停止放映
第 12 页
树的表示 (嵌套形式 )
A
C
G
B
F
E
K L M
H D
J I
下一页
上一页
停止放映
第 13 页
树的表示 (凹入形式 )
A
B
E
K
L
C
D
F
G
H
I
J
M
下一页
上一页
停止放映
第 14 页
树的表示 (广义表形式 )
( A ( B ( E (K,L),F),C(G),D( H (M),I,J )))
第一层
第二层
第三层
第四层
下一页
上一页
停止放映
第 15 页
基本术语
? 结点, 结点度, 根, 支, 叶结点
? 子结点, 父结点, 兄弟结点
? 树的度, 路径, 长度, 高度, 深度
? 森林, 有序, 无序
下一页
上一页
停止放映
第 16 页
结点（ Node）
? 结点 包括一个数据元素及若干个指向其它子
树的分支；例如, A,B,C,D等 。
? 结点度 结点拥有的子树数；例如, A的度为 3。
? 根结点 无前趋结点为根；例如, A结点 。
? 支结点 度不为 0的结点为支结点；如 B,C,D
等 。
? 叶结点 无后继结点为叶；如 K,L,M。
? 树的度 树中结点的最大度数；上述树的度为 3。
下一页
上一页
停止放映
第 17 页
基本术语 （二）
? 子结点 某结点子树的根为该结点的子结点；
例如, 结点 A的子结点为 B,C,D。
? 父结点 相对于某结点子树的根, 称该结点为
子树根的父结点；例如子结点 C,B,D的父结
点为 A。
? 兄弟结点 同一父亲的孩子之间互为兄弟结点
（ Sibling） ； H,I,J互为兄弟 。
? 路径 结点的序列 n1,n2,…,nk(K?1)是一条
路径,
? 长度 长度等于路径中结点数 -1.
下一页
上一页
停止放映
第 18 页
基本术语 （三）
? 高度 从一结点到叶结点的最长路径为该结
点的高度；例如, 结点 A到 M的高度为 4。
? 深度 从根结点到某结点的路径为该结点的
深度； M的深度为 4。
? 森林 0棵或多棵互不相交的树的集合 。 对
树中每个结点而言, 其子树的集合即为森林 。
? 有序 如果将树中结点的各子树看成从左至
右是有顺序的 （ 即不能互换 ）, 则称该树为
有序树 。 否则, 称为无序树 。
下一页
上一页
停止放映
第 19 页
树的操作
? PARENT（ n,T） 得到树中 n的父亲结点；
? ROOT（ T） 求树的根, 返回树根的位置 。
? CHILD（ T,x,i） 求树 T中结点 x的第 i个孩子
结点 。
? CREATE（ x,T1,T2,…,Tk) 生成一个结点 x,
下带子树 T1,T2,…,Tk。
? DELETE(x,i) 删除结点 x的第 i个子树 。
? TRAVERSE（ T） 遍历树 T。 按次序依此访问树
中各个结点, 且使每个结点只能被访问一次 。
下一页
上一页
停止放映
第 20 页
树的实现 (存储结构 )
? 数组实现方法 （ 双亲表示法 ）
? 链表实现方式 （ 孩子表示法 ）
? 二叉链表实现方式 （ 孩子兄弟表
示法 ）
下一页
上一页
停止放映
第 21 页
树的存储结构 (一）
? 数组实现方法（双亲表示法）
用数组存储树的结点信息, 在每个结点中附设一个指示器
指示其双亲结点在数组中的位置 。 结构描述：
#define MAXSIZE 100
typedef struct PTNode{
TElemType data；
int parent ；
} PTNode；
typedef struc {
PTNode nodes[MAXSIZE]；
int n；
} Ptree；
下一页
上一页
停止放映
第 22 页
双亲表示法举例
1
2 3
4 5 6
7 8 9
结点序号
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
0 1 1 2 2 3 5 5 5
方法特点：
找根容易，找子结点难，
要遍历整个数组。
下一页
上一页
停止放映
第 23 页
树的存储结构（二）
? 链表实现方式（孩子表示法）
把每个结点的孩子结点排列起来，组成一个线性表，
且以单链表作为存储结构，则 n个结点有 n个孩子链表。
? 结构描述为：
typedef struct CTNode{ typedef struct {
int child； CTBox nodes[MAXSIZE]；
struct CTNode *next,int n,r；
} *Childptr； } Ctree；
typedef struct {
TElemType data；
Childptr firstchild；
} CTBox；
下一页
上一页
停止放映
第 24 页
孩子表示法举例
1
2 3
4 5 6
7 8 9
1
2
3
4
5
6
7
8
9
2 3 ^
4 5 ^
6 ^
^
^
^
^
^
7 8 9 ^
方法特点,
便于实现对孩子的操
作,却不便于对父亲
的操作,
下一页
上一页
停止放映
第 25 页
树的存储结构（三）
? 二叉链表实现方式 （ 孩子兄弟表示法 ）
以二叉链表作为树的存储结构 。 链表中结点的两个链域
分别指向该结点的第一个孩子结点和下一个兄弟结点 。
结构描述为：
typedef struct CSNode{
ElemType data；
struct CSNode *firstchild, *netsibling；
} CSNode,* CSTree；
下一页
上一页
停止放映
第 26 页
孩子兄弟表示法举例
1
2 3
4 5 6
7 8 9
1
2
^
3
7
4 5 6
8 9
^
^
^
^^
^ ^^
方法特点,
这种存储结构便于实
现各种树的操作,
^
下一页
上一页
停止放映
第 27 页
二、二叉树结构
二叉树是另一类重要的非线性结构 。
– 二叉树的定义
– 二叉树的性质
– 二叉树的存储结构
– 特殊二叉树
– 二叉树的遍历操作
– 表达式树及应用
– 树, 森林与二叉树的转换
下一页
上一页
停止放映
第 28 页
1、二叉树的定义
? 二叉树是另一种树形结构：
Binary_Tree =( D,R)
其中,
D 是具有相同性质的数据元素的集合 ;
R 是在 D上某个两元关系的集合,且满足,
– D中存在唯一称为根的数据元素,没有前趋 ;
– D中其余元素都有且仅有一个前趋 ;
– 每个结点至多只有两个子树 ;
– D中元素,或有两个互不相交后继,或无后继 ;
– 左, 右子树分别又是一棵二叉树 。
下一页
上一页
停止放映
第 29 页
二叉树定义（二）
? 定义
n个结点的集合 （ n?0）
T 的度 ? 2
T = 所有子树都有左, 右之分
（ 次序不能任意颠到 ）
下一页
上一页
停止放映
第 30 页
二叉树的五种基本形态
（ a）
（ b）
（ c）
（ d）
（ e）
O 空结点
O 单个结点
O
O
右子树为空
的二叉树
O
O
左子树为空
的二叉树
O
O O
左、右子树
非空的二叉
树
下一页
上一页
停止放映
第 31 页
二叉树与树的区别
? 表达形式 （ 对 3个结点 ）
普通树
二叉树
（ a） （ b） （ c） （ d） （ e）
O
O O
O
O
O有两种不同形式
（ a） （ b）
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O有五种不同形式
下一页
上一页
停止放映
第 32 页
二叉树与树的区别 （二）
? 观念
– 二叉树是一种特定的树结构, 但
不是普通树的特殊情况；
– 二叉树可以为空；而树则不能为
空；
– 二叉树的结点的子树分左子树和
右子树, 而树则无此区分 。
下一页
上一页
停止放映
第 33 页
2、二叉树的性质
? 性质一
二叉树的第 i层上至多有 2i-1 个结点 （ i ? 1） 。
利用归纳法证明：
– i=1时, 只有一个结点, 对的；
– 假设对所有的 j,1? j ? i,命题成立,
即在第 j层上, 至多有 2j-1 个结点 。
– 由归纳假设, 第 i-1层上至多有 2i-2 个结点 。
由于二叉树的每个结点的度至多为 2,故第 i
层上的最大结点数为第 i-1层上的最大
结点数的 2倍, 即 2X2i-2 = 2i-1。
下一页
上一页
停止放映
第 34 页
二叉树的性质（二）
? 性质二
深度为 k的二叉树上最多含有 2k-1个结点
（ k ? 1） 。
由性质一可见, 深度为 k的二叉树的最大结
点数为：
? （ 第 i层上的最大结点数 ）
= ? 2i-1 = 2k - 1
k
i=1
i=1
k
下一页
上一页
停止放映
第 35 页
验证二叉树的性质
1
2 3
8
65 74
109 11 12 13 14 15
?该二叉树的第 3层有 23-1 个结点,
?该二叉树深度为 4,最多有 24 -1 个结点,
下一页
上一页
停止放映
第 36 页
3、二叉树的存储结构
? 顺序存储 （ 一维数组 ）
? 记录数组结构
? 链式存储结构
– 二叉链表
– 三叉链表
下一页
上一页
停止放映
第 37 页
顺序存储（一维数组）
? 用数组存放
存储描述为：
#define MAXSIZE 100；
typedef TElemType SBTree[MAXSIZE]；
SBTree bt；
? 查找不便 。
a1 a2 a3 a4,.,an
下一页
上一页
停止放映
第 38 页
记录数组结构
? 存储结构描述,
#define MAXSIZE 100;
typedef struct SBNode {
TElemType data ;
int Lchild,Rchild;
} SBNode;
typedef struct｛
SBNode nodes[MAXSIZE];
} SBTree;
下一页
上一页
停止放映
第 39 页
记录数组结构举例
1
2 6
3 4
5
1 2 6
2 3 4
3 0 5
4 0 0
5 0 0
6 0 0
结点 左子 右子
特点,
找子方便,找父
结点不便,
下一页
上一页
停止放映
第 40 页
二叉链表存储结构
data leftp rightp
左指针 数据 右指针
A
B
C D
E F
G
A
B
DC
E F
G
^
^^
^
^ ^
^ ^
特点,
找子易,找父难,
下一页
上一页
停止放映
第 41 页
三叉链表存储结构
parent data rightp
左指针 数据 父结点 右指针
A
B
C D
E F
G
C ^^
^
^
^ ^
特点,
找子、找父都易 。
leftp^^A
B
D
E
G ^
F
下一页
上一页
停止放映
第 42 页
4、特殊二叉树
? 满二叉树
? 完全二叉树
? 平衡二叉树
? 二叉排序树
下一页
上一页
停止放映
第 43 页
满二叉树
? 若 k为二叉树 T的深度, 且 T中共有 2k-1个
结点 （ k ? 1）, 则称 T为满二叉树 。
（ a） 满二叉树 （ b） 非满二叉树
O
O O
O O O O
O
O
O O
O
O
下一页
上一页
停止放映
第 44 页
满二叉树的性质
? 若对满二叉树从第 1层开始,自上而下, 从左至右
给每个结点从 1开始编号的话, 则称深度为 k的满
二叉树的结点编号满足：
– 对某结点 i（ 1? i ? 2k -1 -1）, 其左子树的
编号为 2*i（ 偶数 ）, 其右子树的编号为
2* i +1（ 奇数 ） ； （ 非叶结点 ）
– 若 i>1,则结点 i父结点的编号为 i/2(整除 )。
? 根据这一性质, 可用一维数组存储满二叉数的结
点数据 。 知道一个结点的编号, 经计算就能求出
左, 右子树的根及父结点的编号 。
下一页
上一页
停止放映
第 45 页
满二叉树存储举例
1
4
32
5 76
1 2 3 4 5 6 7
1 2 3 4 5 6 7
?第 i个结点就存放在第 i个位置上；
?第 i个结点（ i>1)的父结点就存放在第
i/2个位置 ;
?第 i个结点（ i?2k -1 - 1)的左子结点就存放
在 第 2*i的个位置 ;右子存放在第 2*i+1位置,
下一页
上一页
停止放映
第 46 页
完全二叉树
? 深度为 k的二叉树 T,每层结点数目若满足,
– 第 i层 (1 ? i ? k-1)上的结点个数均为 2i-1(非
叶结点 );
– 第 k层从右边连续缺若干个结点 (即只能从右
至左不间断缺少 );
称这样的树为完全二叉树 。
? （ a） 完全二叉树 （ b） 非完全二叉树
? 特点, 叶结点只可能出现在层次最大的两层上,
O
O O
O O O
O
O
O
O
O
下一页
上一页
停止放映
第 47 页
完全二叉树的性质
? 设完全二叉树的结点总数为 n,深度为 k,某结点
编号为 i（ 1 ?i ? n ）, 则有：
– 若 i>1,则结点 i的双亲结点的编号为 i /2;
– 若 2* i ? n,则结点 i 的左子结点的编号为 2*
i,否则,结点 i为叶结点 ;
– 若 2* i +1? n,则结点 i 的右子结点的编号为
2*i+1,否则,结点 i为叶结点,
? 同理,完全二叉树也可以采用一维树组作为存储
结构,且方法完全同满二叉树,只不过 n ? 2k -1
罢了,
下一页
上一页
停止放映
第 48 页
平衡二叉树
? 二叉树上任一结点的左子树深度减去右子
树深度的差值, 称为该结点的平衡因子 。
? 任意结点左, 右子树的深度之差的绝对值
?1, 这样的树称为平衡二叉树 。
? （ a） 平衡二叉树 （ b） 非平衡二叉树
O
O
O
O
O
O
O
O
O
O O
O
O
O
下一页
上一页
停止放映
第 49 页
二叉排序树定义（一）
? 二叉排序树
– 或者是空二叉树；
– 或者是：
?左子树上所有结点的值均小于
根结点的值；
?右子树上所有结点的值均大于
等于根结点的值；
– 左, 右子树本身又是一棵二叉排
序树 。
下一页
上一页
停止放映
第 50 页
二叉排序树定义（二）
? X是二叉排序树 T中的一个结点；
– 所有的左后裔小于 X；
– 所有的右后裔大于等于 X；
– T可以为空树；
? T称为二叉排序树 。
（ a） 二叉排序树 （ b） 非二叉排序树
10
5
7 12
14
18
15
15
14 18
5
10
12
13
7
下一页
上一页
停止放映
第 51 页
5、二叉树的 遍 历
? 遍 历 （ Traversing） 是树形结构的一种重
要运算, 即按一定的次序系统地访问结构
中的所有结点, 使每个结点只被访问一次 。
? 遍 历的方法很多, 常用的有：
– 前序法 （ PreOrder）
– 中序法 （ InOrder）
– 后序法 （ PostOrder）
下一页
上一页
停止放映
第 52 页
前序法（ PreOrder）
? 方法描述：
– 从根结点 a开始访问,
– 接着访问左子结点 b，
– 最后访问右子结点 c。
? 即：
根
左子 右子
a
b c
下一页
上一页
停止放映
第 53 页
中序法（ InOrder）
? 方法描述：
– 从左子结点 b开始访问,
– 接着访问根结点 a，
– 最后访问右子结点 c。
? 即：
根
左子 右子
a
b c
下一页
上一页
停止放映
第 54 页
后序法（ PostOrder）
? 方法描述：
– 从左子结点 b开始访问,
– 接着访问右子结点 c，
– 最后访问根结点 a。
? 即：
根
左子 右子
a
b c
下一页
上一页
停止放映
第 55 页
二叉树的遍历举例
o
o o
o o
o
o
o o
A
B C
D E F
G H I
?前序遍历序列,ABDEGCFHI
?中序遍历序列,DBGEACHFI
?后序遍历序列,DGEBHIFCA
下一页
上一页
停止放映
第 56 页
二叉树遍历算法
? 二叉树 遍 历方法分为：
– 递归算法
– 非递归算法
? 递归算法和非递归算法中又分：
– 前序法
– 中序法
– 后序法
下一页
上一页
停止放映
第 57 页
二叉树遍历算法 （递归算法）
?二叉链表的 C语言描述：
struct tnode {
int data；
struct tnode *lchild,*rchild ；
} ；
typedef struct tnode TNODE;
下一页
上一页
停止放映
第 58 页
二叉树遍历算法 （递归、前序法程序）
? void preorder_t (TNODE *root)
{ if ( root != NULL )
{ printf(“%d \n”,root->data);
if (root->lc!=NULL)
proorder_t(root->lc);
if (root->rc!=NULL)
proorder_t(root->rc);
}
}
? 前序遍历二叉树的序列为：
A B C D E F
A
B
C D
E F
下一页
上一页
停止放映
第 59 页
二叉树 遍 历算法 （递归、前序法程序验证）
? 打印 A
– 取 A?.左子 (B)
– 打印 B
? 取 B?.左子 (C)
? 打印 C
– 取 C?.左子 (空 )
– 取 C?.右子 (空 )
? 取 B?.右子 (D)
? 打印 D
– 取 D?.左子 (E)
– 打印 E
? 取 E?.左子 (空 )
? 取 E?.右子 (空 )
– 取 D?.右子 (F)
– 打印 F
? 取 F?.左子 (空 )
? 取 F?.右子 (空 )
– 取 A?.右子 (空 )
? 结束
A
B C
D E
F
下一页
上一页
停止放映
第 60 页
二叉树 遍 历算法 （非递归算法 -前序法）
? 算法步骤,
– step1 初始化,置栈为空 (top=-1),
工作变量 p指向 root;
– step2 p非空 (p!=NULL)
或栈非空 (top!=-1)循环 ;
– step3 p非空循环 ; 访问 p(打印 p->data);
– step4 当前元素进栈,p取 p->lc;
执行 step3；
– step5 p为空, 栈非空, 则出栈,
p取 p->rc,返回 step2.
下一页
上一页
停止放映
第 61 页
二叉树 遍 历算法 （非递归算法 -前序法程序）
#define N m
void preorder_t(TNODE * root)
{ TNODE *p,*stack[N]; int top=-1;
p=root;
while ((p!= NULL)||(top!= -1))
{ while ( P!=NULL)
{ printf(“%d\n”,p->data);
top ++; stack[top]=p;
p=p->lc;
}
if ( top !=-1)
{ p=stack[top]; top - - ;
p=p->rc;
}
}
}
下一页
上一页
停止放映
第 62 页
二叉树 遍 历算法 （非递归、前序法程序验证）
? 打印 A
– A进栈, 取 A?.左子 ( B )
– 打印 B
? B进栈，取 B?.左子 ( C )
? 打印 C
– C 进栈,取 C?.左子 ( 空 )
– C 退栈,取 C?.右子 ( 空 )
? B 退栈,取 B?.右子 ( D )
? 打印 D
– D进栈，取 D?.左子 ( E )
– 打印 E
? E进栈，取 E?.左子 ( 空 )
? E退栈,取 E?.右子 ( 空 )
– D退 栈，取 D?.右子 ( F )
– 打印 F
? F进栈，取 F?.左子 ( 空 )
? F退栈,取 F?.右子 ( 空 )
– A退 栈，取 A?.右子 ( 空 )
? 结束
F
E
D
CB
A
下一页
上一页
停止放映
第 63 页
6、表达式树及应用
? 在计算机中对表达式进行分析和计算是一项重要的任务 。
? 举例, 用二叉树表示表达式：
a + b * （ c - d ） － ｅ ／ｆ
前序遍历序列：－＋ａ＊ｂ－ｃｄ／ｅｆ
中序遍历序列：ａ＋ｂ＊ｃ－ｄ－ｅ／ｆ
后序遍历序列：ａｂｃｄ－＊＋ｅｆ／－
? 分析：
– 每个叶结点为运算对象；
– 每个非叶结点为运算符；
– 每个子树对应一个子表达式 。
? 表达式处理一般采用后序法, 也称, 逆波兰, 法 。
? 表达式处理规则：
– 见运算数入栈；
– 见运算符, 取两个栈顶元素运算后再压栈；
– 直到处理结束 。
－
＋ ／
－ e f＊
b －
c d
a
下一页
上一页
停止放映
第 64 页
表达式树应用举例
（ 1） a b c d 入栈,
（ 2） 遇 ‘ -’,c d 出栈,
运算后再压栈；
（ 3） 遇 ‘ *’, （ c - d） 和 b 出栈,
运算后再压栈；
（ 4） 遇 ‘ +’,b*（ c-d） 和 a出栈,
运算后再压栈；
（ 5） e f 入栈；
（ 6） 遇 ‘ /’,f e 出栈,
运算后再压栈；
（ 7） 遇 ‘ -’,a+b*（ c-d）
和 e/f出栈,
运算后再压栈 。
d
c
b
a
（ 1） （ 2） c - d
b
a
（ 3） b*（ c-d）a
（ 5）
a+b*（ c-d）（ 4）
a+b*（ c-d）
f
e （ 6） e/f
a+b*（ c-d）
（ 7） a+b*（ c-d） - e/f
下一页
上一页
停止放映
第 65 页
7、树、森林与二叉树的转换
? 由于二叉树的存储结构比较简单, 处
理起来也比较方便, 所以有时需要把
复杂的树, 转换为简单的二叉树后再
作处理 。
? 树转换成二叉树
? 森林转换成二叉树
下一页
上一页
停止放映
第 66 页
树转换成二叉树
? 操作算法：
– 保留一个结点的最左子结点；
– 抹掉其余兄弟结点与上级结点的连线；
– 将兄弟结点连在一起；
– 以根为轴, 顺时针旋转一个角度 。
? 举例,o
o
o
o
o o o
o
o o
o o o o
加线 抹线
o
o o
o o o o
旋转
o
o
o
o
o o
o
下一页
上一页
停止放映
第 67 页
森林转换成二叉树
? 操作算法：
– 将森林中每棵树的树根连接起来；
– 将每棵树转换成对应的二叉树；
– 以森林中第一棵树的根为轴顺时针旋转一个角度 。
? 举例 o
o o
o
o o
o o o
o
连线
o
o o
o
o o
o o o
o
抹线o o o
o o
o
o o o
o旋转
oo
o
oo oo
o
oo
下一页
上一页
停止放映
第 68 页
将二叉树还原成树
? 将二叉树还原成树的操作步骤为：
step1 若某结点是其双亲的左子，则
把该结点的右子、右子的右子,…,都
与该结点的双亲结点用线连起来；
step2 删除原二叉树中所有的双亲结
点与右子结点的连线；
step3 整理 1,2两步所得到的树或森
林，使之结构层次分明。
下一页
上一页
停止放映
第 69 页
举例
A
B
E C
F D
G
A
B
E C
F D
G
（ a）二叉树 （ b）加连线
A
B
E C
F D
G
（ c）删除与
右子的连线A
B
E
C
F
D
G （ d）还原后的树
下一页
上一页
停止放映
第 70 页
作业、思考题
1、本单元 作业：
5,6,7,9,11
2、作业要求：
– 提交数字化作业，按要求提交到
指定路径下
– 用 C语言描述
– 作业命名方式为：
学号,章数 _序号
下一页
上一页
停止放映
第 71 页
结束语
? 欢迎对数字化教学法提出意见，以利改进。
? 我的 E-mail地址：
fcliu@xjtu.edu.cn
? 数字化课件的路径,
jec254\user2\tools\lzq\软件基础
? 作业提交路径：
jec251\user\dataroom\homework\班级编号
谢谢，再见！
