Chinaunix首页 | 论坛 | 博客
  • 博客访问: 288336
  • 博文数量: 90
  • 博客积分: 41
  • 博客等级: 民兵
  • 技术积分: 400
  • 用 户 组: 普通用户
  • 注册时间: 2011-12-07 11:52
文章分类
文章存档

2014年(11)

2013年(3)

2012年(69)

2011年(7)

分类:

2012-09-26 16:38:03

  二叉树的遍历方式有前序遍历,中序遍历和后序遍历这三种方式,我们现在就定义一个数据结构树,如下:
struct Tree{
 Tree * lchild;
Tree * rchild;
Element data;//数据域
}
为了实现树的非递归遍历,这里我们需要增加一个数据结构站stack,其实,递归的实现是用系统自带的栈来实现的。
对应的前序遍历如下:
void preTraverse(Tree * t){
 if(t!=null){
  print(t->data);
  preTraverse(t->lchild);
 preTraverse(t->rchild);
}
}
非递归形式的实现如下:
void preTraverse(Tree* t){
  if(t==null)
   return ;
 Stack s ;
while(t!=null){
s.push(t);
print(t->data);
t= t->lchild;
}

while(!s.empty()){

Tree * temp = s.top()->rchild;
s.pop();
   while(temp!=null){
  s.push(temp);
     print(temp->data);
     temp= temp->lchild;
   }
;
}
}
中序遍历的递归形式如下:
void inOrderTraverse(Tree * t){

    if(t!=null){
     inOrderTraverse(t->lchild);
   print(t->data);
inOrderTraverse(t->rchild);
 }
}

中序遍历对应的非递归形式如下:
void inOrderTraverse(Tree * t){
if(t==null)
return;
Stack s;
 s.push(t);
Tree curr = t->lchild;
while(curr!=null || !s.empty()){
   
    while(curr!=null){
      s.push(t);
    curr = curr->lchild;
   }
curr = s.top();
s.pop();
print(cur->data);
curr = curr->rchild;
}
}
后序遍历对应的递归程序如下:
void postOrderTraverse(Tree * t){
  if(t!=null){
   postOrderTraverse(t->lchild);
  postOrderTraverse(t->rchild);
   print(t->data);
}
}
后序遍历对应的非递归程序如下:
void postOrder(Tree * t){
 if(t == null)
 return;
Stack s;
s.push(t);
Tree curr = t-lchild;
while(!s.empty()){
  while(curr ! = null){
    s.push(curr);
    curr = curr - > lchild;
   } 
curr = s.top();
if(curr->rchild == nulll ||curr->rchild == previsited ){
 print(curr->data);
prvisited = curr;
s.pop();
curr = null; //
}else{
curr = curr->right;
}

}


}
阅读(940) | 评论(0) | 转发(0) |
0

上一篇:Nginx Location配置总结

下一篇:快速排序

给主人留下些什么吧!~~