数据结构教程第二十四课遍历二叉树

文章作者 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