返回顶部

收藏

二叉树 的非递归遍历

更多

递归算法相对简单直观,容易写出,但效率低,相比之下非递归算法效率更高

#include "stdafx.h"
#include "malloc.h"
#define M 100
typedef struct tree
{
  char data;
  struct tree *lchild;
  struct tree *rchild;
}bitree,*linktree;

linktree createtree()
{
   char ch;
   linktree bt;
   scanf("%c",&ch);
   if(ch=='.')              //为‘.’时结束
       return NULL;
   else
   {
       bt=(linktree)malloc(sizeof(bitree));
       bt->data=ch;
       bt->lchild=createtree();
       bt->rchild=createtree();
   }
   return bt;
}

void preorder(linktree bt)
{
   linktree stack[M];     //定义一维数字stack[M]作为栈
   int top=0;
   while(bt)                
   {
       while(bt)                    //搜索到最左树
       {
           printf("%c",bt->data);   //输出结点
           stack[top++]=bt;
           bt=bt->lchild;           //搜索左树
       }
       while(top>0)
       {
           bt=stack[--top];         
           bt=bt->rchild;           //搜索右树
           if(bt)                   //若存在右树,跳出该循环
               break;
       }
   }
}
void inorder(linktree bt)
{
   linktree stack[M];   //定义一维数字stack[M]作为栈
   int top=0;
   while(bt)
   {
      while(bt)
      {
         stack[top++]=bt;       
         bt=bt->lchild;
      }
      while(top>0)
      {
         bt=stack[--top];
         printf("%c",bt->data);
         bt=bt->rchild;
         if(bt)
             break;
      }
   }
}
/*后序遍历时,当指针第一次指向某一结点的时候,不能立即访问,要将该结点入栈,然后遍历该节点的左树,当左树遍历完毕再次搜索到该节点的时候,还不能立即访问,要将节点入栈,接着遍历右树,左右树都遍历完毕,第三次遇到该节点的时候,才将该节点出栈并访问。所以附加了一个栈s用来记录节点的访问次数,设定标志值为0时该节点首次入栈,为1时第二次入栈*/
void postorder(linktree bt)
{
  linktree stack[M];      
  int top=0,flag,s[M];   //s[]为标志结点入栈次数
  do{
    while(bt!=NULL)
    {
       stack[top]=bt;
       s[top++]=0;
       bt=bt->lchild;
    }
    if(top>0)
    {
       flag=s[--top];
       bt=stack[top];
       if(flag==0)
       {
          stack[top]=bt;
          s[top++]=1;            //第二次入栈
          bt=bt->rchild;         //遍历右树
       }
       else
       {
          printf("%c",bt->data);   //第3次遇到该节点,输出该节点
          bt=NULL;
       }
    }
  }while(top>0);

}
void main()
{
   linktree bt;
   bt=createtree();         //递归创建二叉树
   printf("先序遍历:");
   preorder(bt);            
   printf("\\n中序遍历:");
   inorder(bt);
   printf("\\n后序遍历:");
   postorder(bt);
}
//该片段来自于http://outofmemory.cn

标签:c++,算法

收藏

0人收藏

支持

0

反对

0

»更多 您可能感兴趣的代码
  1. 2014-07-22 21:15:21斐波那契数列 by lucasli
  2. 2014-07-31 11:37:40二叉树 by 蟋蟀哥
  3. 2014-09-12 12:23:42求32768以内的质数 by walker30
  4. 2014-10-11 10:46:46c++实现欧拉回路问题 by 蟋蟀哥
  5. 2014-10-14 20:34:02二叉树的建立、存储与遍历 by 千万不要郁闷
  6. 2014-10-17 10:56:47求素数 by 童学芬
  7. 2014-10-20 10:44:19余弦曲线 by walker30
  8. 2014-10-26 11:58:41小字库DIY一 by sxgkwei
  9. 2014-12-03 10:48:48KMP算法实现字符串搜索 by 千万不要郁闷
  10. 2013-10-31 09:05:17C语言找出大于一个数的最小回文数 by walker30
  11. 2014-03-03 17:55:22每对结点之间最短路径的C++实现 by 千万不要郁闷
相关聚客文章
  1. dianlujitao 发表 2014-10-17 13:45:25 POJ 3122 Pie
  2. bystander 发表 2013-04-16 00:42:58 模板优先级队列及堆排序(C++实现)
  3. dianlujitao 发表 2014-10-17 13:52:22 POJ 2388 Who’s in the Middle
  4. surgesoft 发表 2014-10-28 08:01:58 LeetCode OJ: Restore IP Addresses
  5. espace 发表 2015-07-18 17:43:14 Two Sum
  6. abyssss 发表 2014-05-20 03:23:39 数据结构 最小堆 数组实现
  7. dianlujitao 发表 2014-10-17 13:56:48 POJ 1611 The Suspects
  8. bystander 发表 2013-05-15 10:37:24 倒水问题求解(C++)
  9. dianlujitao 发表 2014-10-17 14:11:26 POJ 1328 Radar Installation
  10. bystander 发表 2013-04-01 10:12:37 [藏]关于B树的一篇文章
  11. lvfuyu 发表 2015-04-12 08:53:30 [hihocoder]矩阵快速幂
  12. lvfuyu 发表 2015-04-18 09:13:32 [hihocoder]二分查找

发表评论