查看完整版本: 遍历二叉树（数据结构）

遍历二叉树（数据结构）

一、复习二叉树的定义
[indent]二叉树由三个基本单元组成：根结点、左子树、右子树
问题：如何不重复地访问二叉树中每一个结点？
[/indent]二、遍历二叉树的三种方法：
[indent][table=75%][tr=#ffcccc][td=1,3,25%][align=center]先序[/align][/td][td=1,1,7%]1[/td][td=1,1,68%]访问根结点[/td][/tr][tr][td=1,1,7%]2[/td][td=1,1,68%]先序访问左子树[/td][/tr][tr][td=1,1,7%]3[/td][td=1,1,68%]先序访问右子树[/td][/tr][tr=#ccffcc][td=1,3,25%][align=center]中序[/align][/td][td=1,1,7%]1[/td][td=1,1,68%]中序访问左子树[/td][/tr][tr][td=1,1,7%]2[/td][td=1,1,68%]中序访问根结点[/td][/tr][tr][td=1,1,7%]3[/td][td=1,1,68%]中序访问右子树[/td][/tr][tr=#ffcccc][td=1,3,25%][align=center]后序[/align][/td][td=1,1,7%]1[/td][td=1,1,68%]后序访问左子树[/td][/tr][tr][td=1,1,7%]2[/td][td=1,1,68%]后序访问右子树[/td][/tr][tr][td=1,1,7%]3[/td][td=1,1,68%]访问根结点[/td][/tr][/table][/indent]三、递归法遍历二叉树
[indent]先序：
Status(PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){
[indent]if(T){
[indent]if(Visit(T->data))
[indent]if(PreOrderTraverse(t->lchild,Visit))
[indent]if(PreOrderTraverse(T->rchild,Visit)) return OK;
[/indent][/indent]return ERROR;
[/indent]}else return OK;
[/indent]}
[img=273,164]http://www.bccn.net/Article/UploadFDL05/200411/20041112072833195.jpg[/img]遍历结果：1,2,4,5,6,7,3
[/indent]四、非递归法遍历二叉树
[indent][indent][img=328,524]http://www.bccn.net/Article/UploadFDL05/200411/20041112072834264.jpg[/img]
[/indent]中序一：
Status InorderTraverse(BiTree T,Status(*Visit)(TElemType e)){
[indent]InitStack(S);Push(S,T);
while(!StackEmpty(S)){
[indent]while(GetTop(S,p)&&p)Push(S,p->lchild);
Pop(S,p);
if(!StackEmpty(S)){
[indent]Pop(S,p); if(!Visit(p->data)) return ERROR;
Push(S,p->rchild);
[/indent]}
[/indent]}
return OK;
[/indent]}
中序二：
Status InorderTraverse(BiTree T,Status(*Visit)(TElemType e)){
InitStack(S);p=T;
[indent]while(p||!StackEmpty(S)){
[indent]if(p){Push(S,p);p=p->lchild;}
else{
[indent]Pop(S,p); if(!Visit(p->data)) return ERROR;
p=p->rchild);
[/indent]}//else
[/indent]}//while
return OK;
[/indent]}
[/indent]五、总结
[indent]二叉树遍历的意义

[/indent]