Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2091716
  • 博文数量: 288
  • 博客积分: 10594
  • 博客等级: 上将
  • 技术积分: 3469
  • 用 户 组: 普通用户
  • 注册时间: 2006-10-27 19:27
文章分类

全部博文(288)

文章存档

2012年(4)

2011年(30)

2010年(40)

2009年(32)

2008年(71)

2007年(79)

2006年(32)

分类: C/C++

2007-11-15 09:34:09

二叉树的遍历可以大致分为递归遍历和层序遍历。
递归遍历依次遍历左子树和右子树,递归遍历时,每个节点会经过三次。按照访问节点时机的的不同,分为先序,中序和后序遍历。
先序遍历:
1.访问根节点
2.先序遍历左子树
3.先序遍历右子树

//二叉树定义  本例代码为类C伪码 不能直接运行
typedef struct BiTree {
 DataType Data; //定义数据域
 struct BiTree *LChild,*RChild; //定义左右子树的指针
} *BiTree;

//二叉树先序遍历
void PreTraverse(BiTree root) {
 if(root!=NULL) {
  Visit(root->data); //访问根节点
  PreTraverse(root->LChild); //先序遍历左子树
  PreTraverse(root->RChild); //先序遍历右子树
 )
}

中序遍历:
1.中序遍历左子树
2.访问根节点
3.中序遍历右子树

//二叉树中序遍历
void InTraverse(BiTree root) {
 if(root!=NULL) {
  InTraverse(root->LChild);  //中序遍历左子树
  Visit(root->data); //访问根节点
  InTraverse(root->RChild);  //中序遍历右子树
 }
}

后序遍历:
1.后序遍历左子树
2.后序遍历右子树
3.访问根节点

//二叉树后序遍历
void PostTraverse(BiTree root) {
 if(root!=NULL) {
  PostTraverse(root->LChild); //后序遍历左子树
  PostTraverse(root->RChild); //后序遍历右子树
  Visit(root->data); //访问根节点
 }
}

基于栈的递归消除
递归操作隐式地调用系统栈,使时间和空间性能有比较大的损耗。我们可以根据自己的需要调用合适的栈结构,从而提高效率。
以中序遍历为例:
void InOrderTraverse(BiTree root) {
 InitStack(&s); //初始化栈s
 p=root;
 while( p!=NULL || !IsEmpty(s) ) { //当前访问节点存在或栈不空
  if(p!=NULL) { //当前节点存在
   Push(&s,p); //把当前节点压入栈顶
   p=p->LChild; //继续遍历左子树
  }
  else { //当前节点不存在,回溯
   Pop(&s,&p); //将栈顶赋给p,出栈
   Visit(p->data); //访问节点p
   p=p->RChild; //转而访问右子树
  }
 }
}

二叉树的层序遍历 借助队列结构,先把根节点入队,如果队列不为空,则让队首节点出队,访问该节点并把它的左右孩子分别入队列,然后再出队,再访问,再左右孩子入队,直到队列为空。这样在遍历过程中,是以树的深度为顺序的。
void Traverse(BiTree root) {
 if(root!=null)
  EnQueue(&q,root); //根节点入队
 while(!IsEmpty(q)) {
  BiTree temp = DeQueue(&q); //出队
  Visite(temp);  //访问出队节点
  if(temp->LChild)
   EnQueue(&q,temp->LChild); //出队节点左孩子入队
  if(temp->RChild)
   EnQueue(&q,temp->RChild); //出队节点右孩子入队
 }
}

阅读(4075) | 评论(0) | 转发(0) |
0

上一篇:GRUB 学习笔记

下一篇:遗忘往事!.....

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