返回顶部

收藏

二叉树 的非递归遍历

更多

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

#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. 2012-11-06 09:31:31孪生素数 by 牛哥
  2. 2013-03-29 15:39:35背包问题动态规划详解 by moxia
  3. 2013-05-18 15:26:29c++实现K-MEANS算法 by 李兰军
  4. 2014-02-07 11:26:13C++算法之寻路算法 by 千万不要郁闷
  5. 2014-05-04 10:48:55C++算法之内存数据 by lucasli
  6. 2014-05-20 13:07:50各种排序算法 by walker30
  7. 2014-05-21 17:32:00排序之直接插入排序 by Kevin.
  8. 2014-05-21 21:44:10算法实现—磁盘调度 by niutao.linux
  9. 2014-06-07 11:54:45迭代算法的应用 by sxgkwei
  10. 2014-06-29 11:32:00用递归和非递归方法遍历二叉树的前,中,后序 by qqmmcc
  11. 2014-07-14 12:28:27顺序表操作 by 小项
相关聚客文章
  1. dianlujitao 发表 2013-10-31 01:04:46 搬运树苗 二分+贪心
  2. leaver 发表 2013-05-31 07:05:29 邻接表实现无向图(C++)
  3. wysaid 发表 2014-05-23 10:15:47 [EGE Net]跟风做个小demo,网格自由变化~
  4. 陆离 发表 2014-10-28 08:01:58 LeetCode OJ: Restore IP Addresses
  5. dianlujitao 发表 2013-10-14 14:23:32 数字游戏 动态规划 解题报告
  6. dianlujitao 发表 2013-10-14 02:23:16 WIKIOI 1501 二叉树最大宽度和高度
  7. leaver 发表 2013-06-02 07:44:22 阿里巴巴5月5日综合算法题详解
  8. dianlujitao 发表 2014-10-16 14:11:10 CodeForces 23A You’re Given a String…
  9. dianlujitao 发表 2014-10-17 13:14:36 CodeForces 23B Party
  10. dianlujitao 发表 2014-10-17 13:32:08 POJ 2339 Rock, Scissors, Paper
  11. bystander 发表 2013-04-11 10:50:25 模板栈以及中缀表达式求值(C++实现)
  12. dianlujitao 发表 2014-10-17 13:42:33 POJ 3844 Divisible Subsequences

发表评论