数据结构教程第二十四课遍历二叉树
文章作者 100test 发表时间 2007:03:10 18:29:01
来源 100Test.Com百考试题网
教学目的: 掌握二叉树遍历的三种方法
教学重点: 二叉树的遍历算法
教学难点: 中序与后序遍历的非递归算法
授课内容:
一、复习二叉树的定义
二叉树由三个基本单元组成:根结点、左子树、右子树
问题:如何不重复地访问二叉树中每一个结点?
二、遍历二叉树的三种方法:
先序 |
1 |
访问根结点 |
2 |
先序访问左子树 |
3 |
先序访问右子树 |
中序 |
1 |
中序访问左子树 |
2 |
中序访问根结点 |
3 |
中序访问右子树 |
后序 |
1 |
后序访问左子树 |
2 |
后序访问右子树 |
3 |
访问根结点 |
三、递归法遍历二叉树
先序:
Status(PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){
if(T){
if(Visit(T->data))
if(PreOrderTraverse(t->lchild,Visit))
if(PreOrderTraverse(T->rchild,Visit)) return OK.
return ERROR.
}else return OK.
}
遍历结果:1,2,4,5,6,7,3