数据结构--二叉树的非递归遍历_树的非递归后序遍历

系列文章目录

第八话 数据结构之二叉树

前言

对于同一个二叉树来说，其先序、中序、后序遍历都是从根节点开始的，且在遍历过程中经过节点的路线也是一样的，只是访问的时机不同而已。

一、非递归遍历的路线

路线图如下：

沿着该路线：

按 ▲ 标记的节点读得的序列为先序序列

按  *  标记的节点读得的序列为中序序列

按  #  标记的节点读得的序列为后序序列

1、首先创建一个二叉树: 

#include <stdio.h>
#include <stdlib.h>
#define maxsize 100
//先序遍历非递归实现
typedef char Elemtype;
typedef struct node{
    Elemtype date;
    struct node *lchild,*rchild;
}bitree;
 
bitree *createtree()
{
    bitree *pA = (bitree*)malloc(sizeof(bitree));
    bitree *pB = (bitree*)malloc(sizeof(bitree));
    bitree *pC = (bitree*)malloc(sizeof(bitree));
    bitree *pD = (bitree*)malloc(sizeof(bitree));
    bitree *pE = (bitree*)malloc(sizeof(bitree));
    bitree *pF = (bitree*)malloc(sizeof(bitree));
    bitree *pG = (bitree*)malloc(sizeof(bitree));
 
    pA->date = 'A';
    pB->date = 'B';
    pC->date = 'C';
    pD->date = 'D';
    pE->date = 'E';
    pF->date = 'F';
    pG->date = 'G';
 
    pA->lchild = pB;
    pA->rchild = pC;
 
    pB->lchild = NULL;
    pB->rchild = pD;
 
    pC->lchild = NULL;
    pC->rchild = pE;
 
    pD->lchild = pF;
    pD->rchild = pG;
 
    pE->lchild = NULL;
    pE->rchild = NULL;
 
    pF->lchild = NULL;
    pF->rchild = NULL;
 
    pG->lchild = NULL;
    pG->rchild = NULL;
    return pA;
}

二、先序遍历的非递归实现

1、实现方法如下：

在沿左子树搜索时，当搜索的节点不为空时，先访问节点，然后再进栈，在搜索左节点，不为空时继续访问并且入栈，继续以此规律搜索

当搜索的节点为空时，让一个节点出栈，然后搜索节点的右节点，再为空时再出栈一个节点，并且继续搜索右子树

2、实现代码如下： 

//先序遍历非递归实现
void preorder(bitree *t)
{
   bitree *Stack[maxsize];
   int top = -1;
   bitree *p;
   if(t==NULL){
    printf("树为空\n");
   }
   p = t;
   while(p!=NULL||top!=-1){
    while(p!=NULL){
        printf("%c ",p->date);//访问节点的数据域
        if(top<maxsize-1){
            top++;
            Stack[top] = p;//入栈
        }else{
            printf("错误\n");
        }
        p = p->lchild;//指向左孩子
    }
    if(top==-1){
        printf("空");
    }else{
        p = Stack[top];//出栈
        top--;
        p = p->rchild;//指向右孩子
    }
   }
}

3、在主函数中实现如下：

int main()
{
    bitree *t;
    t = createtree();
    printf("先序遍历非递归实现：");
    preorder(t);
    printf("\n");
    return 0;
}

三、中序遍历的非递归实现

1、实现方法如下： 

在沿左子树搜索时，当搜索的节点不为空时，先进栈，在搜索左节点，不为空时继续入栈，继续以此规律搜索

当搜索的节点为空时，让一个节点出栈，并且访问该节点，然后搜索节点的右节点，再为空时再出栈一个节点并访问该节点，且继续搜索右子树

2、实现代码如下：

//中序遍历非递归实现
void inorder(bitree *t)
{
   bitree *Stack[maxsize];
   int top = -1;
   bitree *p;
   if(t==NULL){
       printf("树为空\n");
   }
   p = t;
   while(p!=NULL||top!=-1){
    while(p!=NULL){
        if(top<maxsize-1){
            top++;
            Stack[top] = p;//入栈
        }else{
            printf("错误\n");
        }
        p = p->lchild;//指向左孩子
    }
    if(top==-1){
        printf("空\n");
    }else{
        p = Stack[top];//出栈
        printf("%c ",p->date);//访问节点的数据域
        top--;
        p = p->rchild;//指向右孩子
    }
   }
}

四、后序遍历的非递归实现  

 1、实现方法如下

在沿左子树搜索时，当搜索的节点不为空时，先进栈，在搜索左节点，不为空时继续入栈，继续以此规律搜索

当搜索的节点为空时，让一个节点出栈，节点标记为1，第一次出栈，节点不能访问，继续让该节点入栈,然后搜索节点的右节点，再为空时再出栈一个节点，且继续搜索右子树,

当节点第二次出栈时，该节点标记为2，此时访问该节点，第二次出栈,节点可以访问,然后搜索节点的右节点，再为空时再出栈一个节点，且继续搜索右子树

 该树的先序遍历结果为：ABDFGCE

_代表空格

在输入时应该输入成:AB_DF_ _G_ _C_E_ _

 2、实现代码如下

#include<stdio.h>
#include<stdlib.h>
#define  MAX 100             // 栈中最后存储的结点数
typedef  char  ElemType;   // 为结点数据类型起别名
typedef struct    node    // 二叉树中结点存储结构
{
      ElemType data;        //  存储结点数据
      struct node * lchild;  // 指向结点左孩子指针
      struct node * rchild;  // 指向结点右孩子指针
}BSTree;                   //为二叉树中结点存储结构起别名
typedef struct                //二叉树结点顺序栈结构体定义
{
      BSTree* data[MAX];       //数组存储二叉树各个结点
      int top;                   //用于指示栈顶
}Stack;                 //二叉树顺序栈结构体类型的别名
int flag[MAX];        //用于标识每个结点是第几次入栈
//初始化顺序栈
Stack * Init()
{
      Stack * S;
      //为通讯录顺序栈分配内存
      S=(Stack *)malloc(sizeof(Stack ));
      if(S==NULL)                    //判断内存分配是否成功
      {
            printf("内存分配失败，结束程序\n");
            exit(0);
      }
      else
      {
            S->top=-1;                //当栈为空时，顺序栈的栈顶位置设置为-1
            return S;                 //返回顺序栈的地址
      }
}
//顺序栈的入栈
void  Push(Stack *S, BSTree*  x)
{
      if(S->top<MAX) //判断顺序栈中是否已满
      {
            S->top ++;       //将栈顶位置加1，为入栈元素做好准备
            //将入栈的元素的数据放置在栈顶位置
            S->data[S->top ]=x;
      }
      else
            printf("栈已满，无法入栈！\n");
}
//顺序栈出栈
void Pop(Stack *S, BSTree **x)
{
      if(S->top!=-1)    //判断栈是否为空
      {
            //将栈顶元素的数据赋值给x指针所指向的变量
            (*x)=S->data[S->top];
            S->top--;             //将栈顶位置减1
      }
      else
            printf("栈为空，无法出栈!\n");
}
//创建二叉树
BSTree * Create()
{
      ElemType  ch;
      BSTree * root;
      scanf("%c",&ch); // 输入要创建二叉树的根结点数据
      if(ch==' ')    // 判断二叉树是否为空的二叉树
            root=NULL;  //  如果是空的二叉树则二叉树的根结点指针为空
      else            // 如果不是则创建二叉树的根结点
      {
            //为二叉树的根结点分配存储空间
            root=(BSTree*)malloc(sizeof(BSTree));
            root->data=ch;   // 将输入的数据存储在根结点的数据域中
      //通过递归调用创建根结点的左孩子结点，并使根结点左孩子指针指向该结点
            root->lchild=Create();
      //通过递归调用创建根结点的右孩子结点，并使根结点右孩子指针指向该结点
            root->rchild=Create();
      }
      return  root;
}
//非递归后序遍历二叉树
 void  Postorder(BSTree *root)
 {
      Stack *s1;   //定义一个指向栈的指针
      s1=Init();  //初始化栈
      //判断二叉树是否遍历完了，当二叉树结点指针为空并且栈为空时表示
      //二叉树遍历完了
      while(root!=NULL || s1->top>-1)
      {
            if(root!=NULL)   //当结点不为空时
            {
                  Push(s1,root);     // 将遍历中遇到的结点入栈
                  flag[s1->top]=1;  //标识该结点第1次入栈
                  root=root->lchild;     // 得到该结点的左孩子结点
            }
            else     //当结点为空时，
            {
                  Pop(s1,&root);   //从栈中出栈得到一个结点
                  if(flag[s1->top+1]==1)//判断出栈的结点是不是第1次入栈
                  {
                        Push(s1,root);//如果是第1次入栈则再次入栈
                        flag[s1->top]=2;  //标识该结点第2次入栈
                        root=root->rchild;     // 得到该结点的左孩子结点
                  }
    //如果出栈的结点是2次入栈，则输出该结点数据，并设置指向结点指针为空
                  else
                  {
                        printf("%3c",root->data);  //输出结点数据
                        root=NULL;    // 设置指针为空
                  }
            }
      }
 }
 int main()
 {
     BSTree *t;
     printf("输入要创建的树的根节点数据：\n");
     t =Create();
     printf("后序遍历非递归实现：");
     Postorder(t);
     printf("\n");
 return 0;
}

 3、实现如下

五、总结

无论是递归还是非递归遍历二叉树，由于每个节点仅被访问一次，则无论按哪一种次序进行遍历，对含n个节点的二叉树，其时间复杂性均为O（n）。所需辅助空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为n，即空间复杂度也为O（n）。