返回顶部

收藏

二叉树 的非递归遍历

更多

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

#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

发表评论