第十二章 树一、教学内容：
1,树和森林的概念（树的定义、树的术语、性质及运算）；
2,二叉树的定义、性质及运算；
3,二叉树的存储结构（顺序、链式表示）；
4,遍历二叉树
5,树的存储结构；树、森林与二叉树的转换；遍历树；遍历森林二、教学要求：
1、了解树和森林的概念。包括树的定义、树的术语和性质；
2、熟练掌握二叉树的结构特性，熟悉二叉树的各种存储结构的特点及适用范围；
3、熟练掌握二叉树的遍历方法及遍历算法；
4、熟悉树的各种存储结构及其特点，掌握树、森林与二叉树的转换方法树是一类重要的非线性数据结构，是以分支关系定义的层次结构
12.1 树的定义定义定义：树 (tree)是 n(n>0)个结点的有限集 T,其中：
有且仅有一个特定的结点，称为树的 根 (root)
当 n>1时，其余结点可分为 m(m>0)个 互不相交的 有限集
T1,T2,…… Tm,其中每一个集合本身又是一棵树，称为根的 子树
(subtree)
特点：
树中至少有一个结点 —— 根
树中各子树是互不相交的集合
A
只有根结点的树
A
B C D
E F G H I J
K L M
有子树的树 根子树基本术语结点 (node)——表示树中的元素，包括数据项及若干指向其子树的分支结点的度 (degree)——结点拥有的子树数叶子 (leaf)——度为 0的结点孩子 (child)——结点子树的根称为该结点的孩子双亲 (parents)——孩子结点的上层结点叫该结点的 ~
兄弟 (sibling)——同一双亲的孩子树的度 ——一棵树中最大的结点度数结点的层次 (level)——从根结点算起，根为第一层，它的孩子为第二层 ……
深度 (depth)——树中结点的最大层次数森林 (forest)——m(m?0)棵互不相交的树的集合基本术语堂兄弟 ——双亲在同一层上的结点路径 ——若存在一个结点的序列 k1,k2,…,kj,可使 k1到达
kj，则称这个结点序列是 k1到 kj拥的一条路径子孙和祖先 ——若存在 k1到达 kj的一条路径 k1,k2,…,kj，
则 k1,k2,…,kj-1使为 kj的祖先，而 k2,…,kj为 k1的子孙有序树和无序树 ——若将树中每个结点的各个子树看成从左到右有次序，则称该树为有序树，否则为无序树
A
B C D
E F G H I J
K L M
结点 A的度,3
结点 B的度,2
结点 M的度,0
叶子,K,L,F,G,M,I,J
结点 A的孩子,B,C,D
结点 B的孩子,E,F
结点 I的双亲,D
结点 L的双亲,E
结点 B,C,D为兄弟结点 K,L为兄弟树的度,3
结点 A的层次,1
结点 M的层次,4
树的深度,4
结点 F,G为堂兄弟结点 A是结点 F,G的祖先树的表示树型表示
b
a
c
g hd e f
i j
图形表示法：
教师 学生 其他人员
99级 2000级 2001级 2002级
……
西安电子科技大学计算机学院通信工程学院 机电工程学院 ……
叶子根子树凹入表表示
a
b
d
e
i
j
f
c
g
h
嵌套集合表示嵌套括号表示
i jd f g h
a
b ce
a ( b ( d,e ( i,j ),c ( g,h ) ) )
12.2 二叉树定义定义：二叉树是 n(n?0)个结点的有限集，它或为空树 (n=0)，
或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成特点
每个结点至多有二棵子树 (即不存在度大于 2的结点 )
二叉树的子树有左、右之分，且其次序不能任意颠倒基本形态
A
只有根结点的二叉树
空二叉树
A
B
右子树为空
A
B
左子树为空
A
B C
左、右子树均非空二叉树性质性质 1,)1(2 1 ii i 个结点层上至多有在二叉树的第证明：用归纳法证明之
i=1时，只有一个根结点,是对的
假设对所有 j(1?j<i)命题成立，即第 j层上至多有 个结点那么，第 i-1层至多有 个结点又二叉树每个结点的度至多为 2
第 i层上最大结点数是第 i-1层的 2倍，即故命题得证
122 01i
12?j
22?i
12 222 ii
性质 2：深度为 k的二叉树至多有 个结点 (k?1)12?k
证明：由性质 1，可得深度为 k 的二叉树最大结点数是
122)(
1 1
1
kk
i
k
i
ii 层的最大结点数第性质 3：对任何一棵二叉树 T,如果其终端结点数为 n0，
度为 2的结点数为 n2,则 n0=n2+1
证明,n1为二叉树 T中度为 1的结点数因为：二叉树中所有结点的度均小于或等于 2
所以：其结点总数 n=n0+n1+n2
又二叉树中，除根结点外，其余结点都只有一个分支进入设 B为分支总数，则 n=B+1
又：分支由度为 1和度为 2的结点射出,?B=n1+2n2
于是,n=B+1=n1+2n2+1=n0+n1+n2
n0=n2+1
几种特殊形式的二叉树满二叉树
定义：
~12 个结点的二叉树称为且有一棵深度为?kk
特点：每一层上的结点数都是最大结点数完全二叉树定义：深度为 k,有 n个结点的二叉树当且仅当其每一个结点都与深度为 k的满二叉树中编号从 1至 n的结点一一对应时，称为 ~
特点叶子结点只可能在层次最大的两层上出现对任一结点，若其右分支下子孙的最大层次为 L，
则其左分支下子孙的最大层次必为 L 或 L+1
1
2 3
11
4 5
8 9 12 13
6 7
10 14 15
1
2 3
11
4 5
8 9 12
6 7
10
1
2 3
4 5
6 7
1
2 3
4 5 6
性质 4：
性质 5：如果对一棵有 n个结点的完全二叉树的结点按层序编号，则对任一结点 i(1?i?n),有：
(1) 如果 i=1,则结点 i是二叉树的根，无双亲；如果
i>1,则其双亲是?i/2?
(2) 如果 2i>n,则结点 i无左孩子；如果 2i?n,则其左孩子是 2i
(3) 如果 2i+1>n,则结点 i无右孩子；如果 2i+1?n，
则其右孩子是 2i+1
1l o g 2?nn 深度为个结点的完全二叉树的具有将树转换成二叉树加线：在兄弟之间加一连线抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系旋转：以树的根结点为轴心，将整树顺时针转 45°
A
B C D
E F G H I
A
B C D
E F G H I
A
B C D
E F G H I
A
B C D
E F G H I
A
B
C
D
E
F
G H
I树转换成的二叉树其右子树一定为空将 二叉 树转换成树加线：若 p结点是双亲结点的左孩子，则将 p的右孩子，右孩子的右孩子,…… 沿分支找到的所有右孩子，都与 p的双亲用线连起来抹线：抹掉原二叉树中双亲与右孩子之间的连线调整：将结点按层次排列，形成树结构
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
IA
B C D
E F G H I
树与二叉树转换
A
CB E
D
树 A
B
C
D E
二叉树
A ^
^ B
C
^ D ^
^ E ^
A ^
^ B C
^ D ^
^ E ^
A ^
^ B
C
^ D ^ ^ E ^
对应
12.3 二叉树的存储结构顺序存储结构
实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素
特点：
结点间关系蕴含在其存储位置中
浪费空间，适于存满二叉树和完全二叉树
a
b c
d e
f g
a b c d e 0 0 0 0 f g
1 2 3 4 5 6 7 8 9 10 11
链式存储结构
二叉链表
typedef struct node
{ datatype data;
struct node *lchild,*rchild;
}JD;
lchild data rchild
A
B
C D
E F
G
在 n个结点的二叉链表中，有 n+1个空指针域
A
B
C D
E F
G
^
^ ^
^ ^ ^
^ ^
空指针个数,2*n0+1*n1+0*n2
=2n0+n1
=n0+n1+n0
=n0+n1+n2+1
=n+1
三叉链表
typedef struct node
{ datatype data;
struct node *lchild,*rchild,*parent;
}JD;
lchild data parent rchild
A
B
C D
E F
G
A
B
C D
E F
G
^ ^
^ ^
^ ^ ^
^ ^
12.4 二叉树的遍历二叉树的遍历方法
先序遍历：先访问根结点,然后分别先序遍历左子树、右子树
中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树
后序遍历：先后序遍历左、右子树，然后访问根结点
按层次遍历：从上到下、从左到右访问各结点
D
L R
LDR,LRD,DLR
RDL,RLD,DRL
A
D
B C
D L R
A
D L R
D L R
B
D
C
D L R
先序遍历序列,A B D C
先序遍历,
A
D
B C
L D R
B
L D R
L D R
A
D
C
L D R
中序遍历序列,B D A C
中序遍历,
A
D
B C
L R D
L R D
L R D
A
D
C
L R D
后序遍历序列,D B C A
后序遍历,
B
-
+ /
a *
b -
e f
c d
先序遍历,
中序遍历：
后序遍历：
层次遍历,
- + a * b - c d / e f
-+a *b -c d /e f
- + a * b - c d/ e f
-+a *b -c d /e f
算法
递归算法
void preorder(JD *bt)
{ if(bt!=NULL)
{ printf("%d\t",bt->data);
preorder(bt->lchild);
preorder(bt->rchild);
}
}
主程序
Pre( T )
返回返回
pre(T R);
返回返回
pre(T R);
A
CB
D
T B
printf(B);
pre(T L);
T A
printf(A);
pre(T L);
T D
printf(D);
pre(T L);
T C
printf(C);
pre(T L);
返回
T
左是空返回
pre(T R);
T
左是空返回
T
右是空返回
T
左是空返回
T
右是空返回
pre(T R);
先序序列,A B D C
非递归算法
A
B
C D
E F
G
p
i
P->A
(1)
A
B
C D
E F
G
p
i
P->A
P->B
(2)
A
B
C D
E F
G
p i
P->A
P->B
P->C
(3)
p=NUL
L
A
B
C D
E F
G
i
P->A
P->B
访问,C(4)
p A
B
C D
E F
G
i
P->A
访问,C B(5)
A
B
C D
E F
G
i
P->A
P->D
访问,C B
p
(6)
A
B
C D
E F
G
i
P->A
P->D
P->E
访问,C B
p
(7)
A
B
C D
E F
G
i
P->A
P->D
访问,C B
Ep (8)
A
B
C D
E F
G
i
P->A
P->D
P->G
访问,C B E
P=NULL
(9)
A
B
C D
E F
G
i
P->A
访问,C B E G D
p
(11)
A
B
C D
E F
G
i
P->A
P->F
访问,C B E G D
p
(12)
A
B
C D
E F
G
i
P->A
P->D
访问,C B E G
p
(10)
A
B
C D
E F
G
i
P->A
访问,C B E G D F
p=NULL
(13)
A
B
C D
E F
G
i
访问,C B E G D F A
p
(14)
A
B
C D
E F
G
i
访问,C B E G D F A
p=NULL
(15)
中序遍历非递归算法遍历算法应用按先序遍历序列建立二叉树的二叉链表，已知先序序列为：
A B C D E? G FA
B
C D
E F
G
A ^
B
^ C ^ D
^ E ^ F ^
^ G ^二叉树的建立演示遍历算法应用统计二叉树中叶子结点个数算法遍历算法应用求二叉树深度算法用队列实现层次遍历下面的 C语言函数是实现对给定的二叉树 T的层次遍历。函数使用一个顺序存储的队列 q[100],存放还没有处理的子树的根结点的地址。注意,队首和队尾指针分别指向队首结点和下次进队结点的存放位置。
void lev_ traverse(T)
NODE *T;
{NODE *q[100],p;
int head,tai l,i;
q[0]=T;head=0;tail=1;
while(head<tail)
{p=q[head++];
printf(“%c”,p->data);
if(p->lchild!=NULL)
q[tail++]=p->lchild;
if(p->rchild!=NULL)
q[tail++]=p->rchild;
}}
从遍历序列恢复二叉树二叉树的先序遍历是先访问根结点，然后按先序遍历方式遍历根结点的左子树和右子树，所以在 先序遍历序列中第一个结点必定是二叉树的根结点。中序遍历是先按中序遍历方式遍历根结点的左子树，如何访问根结点，最后按中序遍历方式遍历根结点的右子树，所以在中先序遍历序列中已知的根结点将中序序列分割称两个子序列。
所以，在一棵任意二叉树的先序遍历和中序遍历或者中序遍历序列和后序遍历序列的条件下，可以唯一确定这棵二叉树。
例,已知一棵二叉树的先序序列为 A,B,D,G,C,E,F,H,而中序序列为：
D,G,B,A,E,C,H,F，试确定此二叉树。
A
DGB ECHF
A
B
HFDG
C
E
A
B C
E
G
D F
H
练习：已知一颗二叉排序树的中序序列和后序序列分别为
D,G,B,A,E,C,H,F和 G,D,B,E,H,F,C,A，画出这颗二叉树。
12.5 二叉排序树定义：二叉排序树或是一棵空树，或是具有下列性质的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
它的左、右子树也分别为二叉排序树二叉排序树的插入
插入原则：若二叉排序树为空，则插入结点应为新的根结点；否则，继续在其左、右子树上查找，直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子
二叉排序树生成：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树
插入算法例 {10,18,3,8,12,2,7,3}
10 10
18
10
183
10
183
8
10
183
8 12
10
183
8 122
10
183
8 122
7
10
183
8 122
7
3
中序遍历二叉排序树可得到一个关键字的有序序列Ch5_9.c
二叉排序树的删除要删除二叉排序树中的 p结点，分三种情况：
p为叶子结点，只需修改 p双亲 f的指针 f->lchild=NULL f-
>rchild=NULL
p只有左子树或右子树
p只有左子树，用 p的左孩子代替 p (1)(2)
p只有右子树，用 p的右孩子代替 p (3)(4)
p左、右子树均非空
沿 p左子树的根 C的右子树分支找到 S,S的右子树为空，将 S的左子树成为 S的双亲 Q的右子树，用 S取代 p (5)
若 C无右子树，用 C取代 p (6)
S
Q
PL
P
中序遍历,Q S PL P
S
Q PL
中序遍历,Q S PL
(2)
S
P
PL
Q
中序遍历,PL P S Q
S
PL Q
中序遍历,PL S Q
(1)
中序遍历,P PR S Q
S
PR Q
中序遍历,PR S Q
(3)
S
P
PR
Q
中序遍历,Q S P PR
S
Q PR
中序遍历,Q S PR
(4)
S
Q
PR
P
F
P
C PR
CL Q
QL S
SL
中序遍历,CL C ……Q L Q SL S P PR F
F
S
C PR
CL Q
QL SL
中序遍历,CL C ……Q L Q SL S PR F(5)
F
P
C PR
CL
中序遍历,CL C P PR F
F
C
PRCL
中序遍历,CL C PR F
(6)
删除算法例 80
50 120
60 110 150
55 70
53
删除 50
80
60 120
110 15055 70
53
删除 60
80
55 120
110 15053 70
10
4 25
8 13
5
4
删除 10
8
4 25
5 13
4
删除 5
8
4 25
4 13
Ch5_10.c
作业：
1,请做教材 P171的 1,6,7,8,16。
1,树和森林的概念（树的定义、树的术语、性质及运算）；
2,二叉树的定义、性质及运算；
3,二叉树的存储结构（顺序、链式表示）；
4,遍历二叉树
5,树的存储结构；树、森林与二叉树的转换；遍历树；遍历森林二、教学要求：
1、了解树和森林的概念。包括树的定义、树的术语和性质；
2、熟练掌握二叉树的结构特性，熟悉二叉树的各种存储结构的特点及适用范围；
3、熟练掌握二叉树的遍历方法及遍历算法；
4、熟悉树的各种存储结构及其特点，掌握树、森林与二叉树的转换方法树是一类重要的非线性数据结构，是以分支关系定义的层次结构
12.1 树的定义定义定义：树 (tree)是 n(n>0)个结点的有限集 T,其中：
有且仅有一个特定的结点，称为树的 根 (root)
当 n>1时，其余结点可分为 m(m>0)个 互不相交的 有限集
T1,T2,…… Tm,其中每一个集合本身又是一棵树，称为根的 子树
(subtree)
特点：
树中至少有一个结点 —— 根
树中各子树是互不相交的集合
A
只有根结点的树
A
B C D
E F G H I J
K L M
有子树的树 根子树基本术语结点 (node)——表示树中的元素，包括数据项及若干指向其子树的分支结点的度 (degree)——结点拥有的子树数叶子 (leaf)——度为 0的结点孩子 (child)——结点子树的根称为该结点的孩子双亲 (parents)——孩子结点的上层结点叫该结点的 ~
兄弟 (sibling)——同一双亲的孩子树的度 ——一棵树中最大的结点度数结点的层次 (level)——从根结点算起，根为第一层，它的孩子为第二层 ……
深度 (depth)——树中结点的最大层次数森林 (forest)——m(m?0)棵互不相交的树的集合基本术语堂兄弟 ——双亲在同一层上的结点路径 ——若存在一个结点的序列 k1,k2,…,kj,可使 k1到达
kj，则称这个结点序列是 k1到 kj拥的一条路径子孙和祖先 ——若存在 k1到达 kj的一条路径 k1,k2,…,kj，
则 k1,k2,…,kj-1使为 kj的祖先，而 k2,…,kj为 k1的子孙有序树和无序树 ——若将树中每个结点的各个子树看成从左到右有次序，则称该树为有序树，否则为无序树
A
B C D
E F G H I J
K L M
结点 A的度,3
结点 B的度,2
结点 M的度,0
叶子,K,L,F,G,M,I,J
结点 A的孩子,B,C,D
结点 B的孩子,E,F
结点 I的双亲,D
结点 L的双亲,E
结点 B,C,D为兄弟结点 K,L为兄弟树的度,3
结点 A的层次,1
结点 M的层次,4
树的深度,4
结点 F,G为堂兄弟结点 A是结点 F,G的祖先树的表示树型表示
b
a
c
g hd e f
i j
图形表示法：
教师 学生 其他人员
99级 2000级 2001级 2002级
……
西安电子科技大学计算机学院通信工程学院 机电工程学院 ……
叶子根子树凹入表表示
a
b
d
e
i
j
f
c
g
h
嵌套集合表示嵌套括号表示
i jd f g h
a
b ce
a ( b ( d,e ( i,j ),c ( g,h ) ) )
12.2 二叉树定义定义：二叉树是 n(n?0)个结点的有限集，它或为空树 (n=0)，
或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成特点
每个结点至多有二棵子树 (即不存在度大于 2的结点 )
二叉树的子树有左、右之分，且其次序不能任意颠倒基本形态
A
只有根结点的二叉树
空二叉树
A
B
右子树为空
A
B
左子树为空
A
B C
左、右子树均非空二叉树性质性质 1,)1(2 1 ii i 个结点层上至多有在二叉树的第证明：用归纳法证明之
i=1时，只有一个根结点,是对的
假设对所有 j(1?j<i)命题成立，即第 j层上至多有 个结点那么，第 i-1层至多有 个结点又二叉树每个结点的度至多为 2
第 i层上最大结点数是第 i-1层的 2倍，即故命题得证
122 01i
12?j
22?i
12 222 ii
性质 2：深度为 k的二叉树至多有 个结点 (k?1)12?k
证明：由性质 1，可得深度为 k 的二叉树最大结点数是
122)(
1 1
1
kk
i
k
i
ii 层的最大结点数第性质 3：对任何一棵二叉树 T,如果其终端结点数为 n0，
度为 2的结点数为 n2,则 n0=n2+1
证明,n1为二叉树 T中度为 1的结点数因为：二叉树中所有结点的度均小于或等于 2
所以：其结点总数 n=n0+n1+n2
又二叉树中，除根结点外，其余结点都只有一个分支进入设 B为分支总数，则 n=B+1
又：分支由度为 1和度为 2的结点射出,?B=n1+2n2
于是,n=B+1=n1+2n2+1=n0+n1+n2
n0=n2+1
几种特殊形式的二叉树满二叉树
定义：
~12 个结点的二叉树称为且有一棵深度为?kk
特点：每一层上的结点数都是最大结点数完全二叉树定义：深度为 k,有 n个结点的二叉树当且仅当其每一个结点都与深度为 k的满二叉树中编号从 1至 n的结点一一对应时，称为 ~
特点叶子结点只可能在层次最大的两层上出现对任一结点，若其右分支下子孙的最大层次为 L，
则其左分支下子孙的最大层次必为 L 或 L+1
1
2 3
11
4 5
8 9 12 13
6 7
10 14 15
1
2 3
11
4 5
8 9 12
6 7
10
1
2 3
4 5
6 7
1
2 3
4 5 6
性质 4：
性质 5：如果对一棵有 n个结点的完全二叉树的结点按层序编号，则对任一结点 i(1?i?n),有：
(1) 如果 i=1,则结点 i是二叉树的根，无双亲；如果
i>1,则其双亲是?i/2?
(2) 如果 2i>n,则结点 i无左孩子；如果 2i?n,则其左孩子是 2i
(3) 如果 2i+1>n,则结点 i无右孩子；如果 2i+1?n，
则其右孩子是 2i+1
1l o g 2?nn 深度为个结点的完全二叉树的具有将树转换成二叉树加线：在兄弟之间加一连线抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系旋转：以树的根结点为轴心，将整树顺时针转 45°
A
B C D
E F G H I
A
B C D
E F G H I
A
B C D
E F G H I
A
B C D
E F G H I
A
B
C
D
E
F
G H
I树转换成的二叉树其右子树一定为空将 二叉 树转换成树加线：若 p结点是双亲结点的左孩子，则将 p的右孩子，右孩子的右孩子,…… 沿分支找到的所有右孩子，都与 p的双亲用线连起来抹线：抹掉原二叉树中双亲与右孩子之间的连线调整：将结点按层次排列，形成树结构
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
IA
B C D
E F G H I
树与二叉树转换
A
CB E
D
树 A
B
C
D E
二叉树
A ^
^ B
C
^ D ^
^ E ^
A ^
^ B C
^ D ^
^ E ^
A ^
^ B
C
^ D ^ ^ E ^
对应
12.3 二叉树的存储结构顺序存储结构
实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素
特点：
结点间关系蕴含在其存储位置中
浪费空间，适于存满二叉树和完全二叉树
a
b c
d e
f g
a b c d e 0 0 0 0 f g
1 2 3 4 5 6 7 8 9 10 11
链式存储结构
二叉链表
typedef struct node
{ datatype data;
struct node *lchild,*rchild;
}JD;
lchild data rchild
A
B
C D
E F
G
在 n个结点的二叉链表中，有 n+1个空指针域
A
B
C D
E F
G
^
^ ^
^ ^ ^
^ ^
空指针个数,2*n0+1*n1+0*n2
=2n0+n1
=n0+n1+n0
=n0+n1+n2+1
=n+1
三叉链表
typedef struct node
{ datatype data;
struct node *lchild,*rchild,*parent;
}JD;
lchild data parent rchild
A
B
C D
E F
G
A
B
C D
E F
G
^ ^
^ ^
^ ^ ^
^ ^
12.4 二叉树的遍历二叉树的遍历方法
先序遍历：先访问根结点,然后分别先序遍历左子树、右子树
中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树
后序遍历：先后序遍历左、右子树，然后访问根结点
按层次遍历：从上到下、从左到右访问各结点
D
L R
LDR,LRD,DLR
RDL,RLD,DRL
A
D
B C
D L R
A
D L R
D L R
B
D
C
D L R
先序遍历序列,A B D C
先序遍历,
A
D
B C
L D R
B
L D R
L D R
A
D
C
L D R
中序遍历序列,B D A C
中序遍历,
A
D
B C
L R D
L R D
L R D
A
D
C
L R D
后序遍历序列,D B C A
后序遍历,
B
-
+ /
a *
b -
e f
c d
先序遍历,
中序遍历：
后序遍历：
层次遍历,
- + a * b - c d / e f
-+a *b -c d /e f
- + a * b - c d/ e f
-+a *b -c d /e f
算法
递归算法
void preorder(JD *bt)
{ if(bt!=NULL)
{ printf("%d\t",bt->data);
preorder(bt->lchild);
preorder(bt->rchild);
}
}
主程序
Pre( T )
返回返回
pre(T R);
返回返回
pre(T R);
A
CB
D
T B
printf(B);
pre(T L);
T A
printf(A);
pre(T L);
T D
printf(D);
pre(T L);
T C
printf(C);
pre(T L);
返回
T
左是空返回
pre(T R);
T
左是空返回
T
右是空返回
T
左是空返回
T
右是空返回
pre(T R);
先序序列,A B D C
非递归算法
A
B
C D
E F
G
p
i
P->A
(1)
A
B
C D
E F
G
p
i
P->A
P->B
(2)
A
B
C D
E F
G
p i
P->A
P->B
P->C
(3)
p=NUL
L
A
B
C D
E F
G
i
P->A
P->B
访问,C(4)
p A
B
C D
E F
G
i
P->A
访问,C B(5)
A
B
C D
E F
G
i
P->A
P->D
访问,C B
p
(6)
A
B
C D
E F
G
i
P->A
P->D
P->E
访问,C B
p
(7)
A
B
C D
E F
G
i
P->A
P->D
访问,C B
Ep (8)
A
B
C D
E F
G
i
P->A
P->D
P->G
访问,C B E
P=NULL
(9)
A
B
C D
E F
G
i
P->A
访问,C B E G D
p
(11)
A
B
C D
E F
G
i
P->A
P->F
访问,C B E G D
p
(12)
A
B
C D
E F
G
i
P->A
P->D
访问,C B E G
p
(10)
A
B
C D
E F
G
i
P->A
访问,C B E G D F
p=NULL
(13)
A
B
C D
E F
G
i
访问,C B E G D F A
p
(14)
A
B
C D
E F
G
i
访问,C B E G D F A
p=NULL
(15)
中序遍历非递归算法遍历算法应用按先序遍历序列建立二叉树的二叉链表，已知先序序列为：
A B C D E? G FA
B
C D
E F
G
A ^
B
^ C ^ D
^ E ^ F ^
^ G ^二叉树的建立演示遍历算法应用统计二叉树中叶子结点个数算法遍历算法应用求二叉树深度算法用队列实现层次遍历下面的 C语言函数是实现对给定的二叉树 T的层次遍历。函数使用一个顺序存储的队列 q[100],存放还没有处理的子树的根结点的地址。注意,队首和队尾指针分别指向队首结点和下次进队结点的存放位置。
void lev_ traverse(T)
NODE *T;
{NODE *q[100],p;
int head,tai l,i;
q[0]=T;head=0;tail=1;
while(head<tail)
{p=q[head++];
printf(“%c”,p->data);
if(p->lchild!=NULL)
q[tail++]=p->lchild;
if(p->rchild!=NULL)
q[tail++]=p->rchild;
}}
从遍历序列恢复二叉树二叉树的先序遍历是先访问根结点，然后按先序遍历方式遍历根结点的左子树和右子树，所以在 先序遍历序列中第一个结点必定是二叉树的根结点。中序遍历是先按中序遍历方式遍历根结点的左子树，如何访问根结点，最后按中序遍历方式遍历根结点的右子树，所以在中先序遍历序列中已知的根结点将中序序列分割称两个子序列。
所以，在一棵任意二叉树的先序遍历和中序遍历或者中序遍历序列和后序遍历序列的条件下，可以唯一确定这棵二叉树。
例,已知一棵二叉树的先序序列为 A,B,D,G,C,E,F,H,而中序序列为：
D,G,B,A,E,C,H,F，试确定此二叉树。
A
DGB ECHF
A
B
HFDG
C
E
A
B C
E
G
D F
H
练习：已知一颗二叉排序树的中序序列和后序序列分别为
D,G,B,A,E,C,H,F和 G,D,B,E,H,F,C,A，画出这颗二叉树。
12.5 二叉排序树定义：二叉排序树或是一棵空树，或是具有下列性质的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
它的左、右子树也分别为二叉排序树二叉排序树的插入
插入原则：若二叉排序树为空，则插入结点应为新的根结点；否则，继续在其左、右子树上查找，直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子
二叉排序树生成：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树
插入算法例 {10,18,3,8,12,2,7,3}
10 10
18
10
183
10
183
8
10
183
8 12
10
183
8 122
10
183
8 122
7
10
183
8 122
7
3
中序遍历二叉排序树可得到一个关键字的有序序列Ch5_9.c
二叉排序树的删除要删除二叉排序树中的 p结点，分三种情况：
p为叶子结点，只需修改 p双亲 f的指针 f->lchild=NULL f-
>rchild=NULL
p只有左子树或右子树
p只有左子树，用 p的左孩子代替 p (1)(2)
p只有右子树，用 p的右孩子代替 p (3)(4)
p左、右子树均非空
沿 p左子树的根 C的右子树分支找到 S,S的右子树为空，将 S的左子树成为 S的双亲 Q的右子树，用 S取代 p (5)
若 C无右子树，用 C取代 p (6)
S
Q
PL
P
中序遍历,Q S PL P
S
Q PL
中序遍历,Q S PL
(2)
S
P
PL
Q
中序遍历,PL P S Q
S
PL Q
中序遍历,PL S Q
(1)
中序遍历,P PR S Q
S
PR Q
中序遍历,PR S Q
(3)
S
P
PR
Q
中序遍历,Q S P PR
S
Q PR
中序遍历,Q S PR
(4)
S
Q
PR
P
F
P
C PR
CL Q
QL S
SL
中序遍历,CL C ……Q L Q SL S P PR F
F
S
C PR
CL Q
QL SL
中序遍历,CL C ……Q L Q SL S PR F(5)
F
P
C PR
CL
中序遍历,CL C P PR F
F
C
PRCL
中序遍历,CL C PR F
(6)
删除算法例 80
50 120
60 110 150
55 70
53
删除 50
80
60 120
110 15055 70
53
删除 60
80
55 120
110 15053 70
10
4 25
8 13
5
4
删除 10
8
4 25
5 13
4
删除 5
8
4 25
4 13
Ch5_10.c
作业：
1,请做教材 P171的 1,6,7,8,16。
