文档介绍：数据结构与算法分析
沈阳建筑大学 赵明
第六章 树和二叉树
知识点一 树的定义和基本术语
知识点二 二叉树
知识点三 遍历二叉树
知识点四 线索二叉树
知识点五 树和森林
知识点六 赫弗曼树及其应用
知识点三
T
>
右是空返回
T
>
左是空返回
T
>
右是空返回
pre(T R);
先序序列：A B D C
遍历二叉树——递归遍历算法
中序遍历算法
void inorder(bitree *bt){
if(bt!=NULL){
inorder(bt->lchild);
printf("%d\t",bt->data);
inorder(bt->rchild);
}
}
遍历二叉树——递归遍历算法
中序遍历二叉树
若二叉树为空，则空操作；否则
（1）中序遍历左子树；
（2）访问根结点；
（3）中序遍历右子树。
后序遍历算法
void postorder(bitree *bt){
if(bt!=NULL){
postorder(bt->lchild);
postorder(bt->rchild);
printf("%d\t",bt->data);
}
}
遍历二叉树——递归遍历算法
后序遍历二叉树
若二叉树为空，则空操作；否则
（1）后序遍历左子树；
（2）后序遍历右子树；
（3）访问根结点。
以中序遍历为例，从中序遍历递归算法的工作过程中栈的状态可见：
工作记录中的指针包含两项，一个是递归调用的语句编号，一个是指向根节点的指针，则当栈顶记录的指针非空时，应遍历左子树，即指向左子树的根进栈；
若栈顶记录中的指针值为空，则应退至上一层，
若从左子树返回，则应访问当前层即栈顶记录中指针所指的根节点后，遍历右子树。
若从右子树放回，则表明当前遍历结束，应继续退栈。从另一角度看，这意味着遍历右子树时，不需再保存当前层的根节点，可直接修改栈顶记录中的指针即可。
遍历二叉树——非递归遍历算法
Status InOrderTraverse(T){
InitStack(S); p=T;
while (p||StackEmpty(S)){
if(p){//当前指针不为空,进栈,遍历左
Push(S,p);p=p->lchild;
}
else{//为空,从左,访问根,返回上一层
Pop(S,p); //从右，直接退栈
printf(p->data)
p=p->rchild;
}
return OK;}
S
A
B
C
D
E
F
G
p
访问：
遍历二叉树——非递归遍历算法
Status InOrderTraverse(T){
InitStack(S); p=T;
while (p||StackEmpty(S)){
if(p){
Push(S,p);p=p->lchild;
}
else{
Pop(S,p);
printf(p->data)
p=p->rchilde;
}
return OK;}
S
A
B
C
D
E
F
G
p
访问：
P－>A
遍历二叉树——非递归遍历算法
Status InOrderTraverse(T){
InitStack(S); p=T;
while (p||StackEmpty(S)){
if(p){
Push(S,p);p=p->lchild;
}
else{
Pop(S,p);
printf(p->data)
p=p->rchilde;
}
return OK;}
S
A
B
C
D
E
F
G
p
访问：
P－>A
P－>B
遍历二叉树——非递归遍历算法
Status InOrderTraverse(T){
InitStack(S); p=T;
while (p||StackEmpty(S)){
if(p){
Push(S,p);p=p->lchild;
}
else{
Pop(S,p);
printf(p->data)
p=p->rchilde;
}