第二十四课 遍历二叉树

来源：百度文库 编辑：神马文学网 时间：2024/04/25 23:00:48
教学目的： 掌握二叉树遍历的三种方法
教学重点： 二叉树的遍历算法
教学难点： 中序与后序遍历的非递归算法
授课内容：
一、复习二叉树的定义
二叉树由三个基本单元组成：根结点、左子树、右子树
问题：如何不重复地访问二叉树中每一个结点？
二、遍历二叉树的三种方法：
先序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
四、非递归法遍历二叉树

中序一：
Status InorderTraverse(BiTree T,Status(*Visit)(TElemType e)){
InitStack(S);Push(S,T);
while(!StackEmpty(S)){
while(GetTop(S,p)&&p)Push(S,p->lchild);
Pop(S,p);
if(!StackEmpty(S)){
Pop(S,p); if(!Visit(p->data)) return ERROR;
Push(S,p->rchild);
}
}
return OK;
}
中序二：
Status InorderTraverse(BiTree T,Status(*Visit)(TElemType e)){
InitStack(S);p=T;
while(p||!StackEmpty(S)){
if(p){Push(S,p);p=p->lchild;}
else{
Pop(S,p); if(!Visit(p->data)) return ERROR;
p=p->rchild);
}//else
}//while
return OK;
}
五、总结
二叉树遍历的意义
第二十四课 遍历二叉树 二叉树及其遍历 二叉树及其遍历 二叉树的遍历 第二十七课 实验六 二叉树实验 第二十四课 20080429 第五章 二叉树 汇编实现简单二叉树 第六章 树和二叉树 编程论坛-平衡二叉树[原创] 编程论坛-关于平衡二叉树 编程论坛-平衡二叉树[原创] 第二十四章　战争 第二十四章 血气形志篇第二十四 第二十四章　修四念处 议对第二十四 大连市第二十四中学 ●卷第二十四 三辈往生第二十四 地雷复第二十四 第二十四课 一切皆在你心中 求！！建立平衡二叉树的源程序1 曹相国世家　第二十四