C语言非递归后序遍历二叉树

本文实例为大家分享了C语言非递归后序遍历二叉树的具体代码,供大家参考,具体内容如下

法一:实现思路:一个栈 先按 根->右子树->左子树的顺序访问二叉树。访问时不输出。另一个栈存入前一个栈只进栈的结点。
最后输出后一个栈的结点数据。

#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode{
  char element;
  struct TreeNode *left,*right;
}Tree,*BTree;
typedef struct StackNode{
  BTree data;
  struct StackNode *next;
}Stack,*PStack;
typedef struct{
  PStack top;
}LinkStack,*PLinkStack;
//初始化空栈
PLinkStack Init_Stack(void){
  PLinkStack S;
  S=(PLinkStack)malloc(sizeof(LinkStack));
  if(S){
    S->top=NULL;
  }
  return S;
}
//压栈
void Push_Stack(PLinkStack S,BTree T){
  PStack p;
  p=(PStack)malloc(sizeof(Stack));
  p->data=T;
  p->next=S->top;
  S->top=p;
}
//判空
int empty_Stack(PLinkStack S){
  if(S->top){
    return 0;
  }else{
    return 1;
  }
}
//出栈
PStack Pop_Stack(PLinkStack S){
  PStack q;
  if(empty_Stack(S)){
    return S->top;
  }else{
    q=S->top;
    S->top=S->top->next;
  }
  return q;
}
//销毁栈
void DestroyStack(PLinkStack S){
  PStack del;
  while(S->top!=NULL){
    del=S->top;
    S->top=S->top->next;
    free(del);
  }
  free(S);
}
BTree BuildTree(void){
  char ch;
  BTree node;
  ch=getchar();
  if(ch=='#'){
    node=NULL;
  }else{
    node=(BTree)malloc(sizeof(Tree));
    node->element=ch;
    node->left=BuildTree();
    node->right=BuildTree();
  }
  return node;
}
void NotRecursionPostOrder(BTree T){
  PLinkStack S,CS;
  S=Init_Stack();
  CS=Init_Stack();
  while(T || !empty_Stack(S)){
    if(T){
      Push_Stack(S,T);
      Push_Stack(CS,T);
      T=T->right;
    }else{
      T=Pop_Stack(S)->data;
      T=T->left;
    }
  }
  while(CS->top!=NULL){
    printf("%c",CS->top->data->element);
    CS->top=CS->top->next;
  }
  DestroyStack(CS);
}
int main(void){
  BTree T;
  T=BuildTree();
  NotRecursionPostOrder(T);
  return 0;
} 

法二:实现思路。按先序遍历访问每一个结点。存入栈中,当为空时,就出立即栈(第一次出栈)。出栈后应该立即进栈,去访问进栈结点的右结点,这样可以保证先输出左、右结点,再输出根结点。二次进栈利用flag标记。

#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode {
  char element;
  int flag;
  struct TreeNode *left, *right;
}Tree, *BTree;
typedef struct StackNode {
  BTree data;
  struct StackNode *next;
}Stack, *PStack;
typedef struct {
  PStack top;
}LinkStack, *PLinkStack;
//初始化空栈
PLinkStack Init_Stack(void) {
  PLinkStack S = (PLinkStack)malloc(sizeof(LinkStack));
  if (S) {
    S->top = NULL;
  }
  return S;
}
//压栈
void Push_Stack(PLinkStack S, BTree T) {
  PStack p;
  p = (PStack)malloc(sizeof(Stack));
  p->data = T;
  p->next = S->top;
  S->top = p;
}
//判空
int empty_Stack(PLinkStack S) {
  if (S->top) {
    return 0;
  }
  else {
    return 1;
  }
}
//出栈
PStack Pop_Stack(PLinkStack S) {
  PStack q = S->top;
  S->top = S->top->next;
  return q;
}
BTree BuildTree(void) {
  BTree t;
  char ch;
  ch = getchar();
  if (ch == '#') {
    t = NULL;
  }
  else {
    t = (BTree)malloc(sizeof(Tree));
    t->element = ch;
    t->left = BuildTree();
    t->right = BuildTree();
  }
  return t;
}
void DestroyStack(PLinkStack S){
  PStack p;
  while(S->top){
    p=S->top;
    free(p);
    S->top=S->top->next;
  }
}
void NotRecursionPostOrder(BTree T) {
  PLinkStack S;
  S = Init_Stack();
  while (T || !empty_Stack(S)) {
    if (T) {
      T->flag = 0;
      Push_Stack(S, T);
      T = T->left;
    }
    else {
      T = Pop_Stack(S)->data;
      if (T->flag == 0) {
        T->flag = 1;
        Push_Stack(S, T);
        T = T->right;
      }
      else {
        if (T->flag == 1) {
          printf("%c", T->element);
          T = NULL;
        }
      }
    }
  }
  DestroyStack(S);//销毁栈
}
int main(void) {
  BTree T;
  T = BuildTree();
  NotRecursionPostOrder(T);
  return 0;
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • c语言版本二叉树基本操作示例(先序 递归 非递归)

    复制代码 代码如下: 请按先序遍历输入二叉树元素(每个结点一个字符,空结点为'='):ABD==E==CF==G== 先序递归遍历:A B D E C F G中序递归遍历:D B E A F C G后序递归遍历:D E B F G C A层序递归遍历:ABCDEFG先序非递归遍历:A B D E C F G中序非递归遍历:D B E A F C G后序非递归遍历:D E B F G C A深度:请按任意键继续. . . 复制代码 代码如下: #include<stdio.h>#include&

  • C语言数据结构之二叉树的非递归后序遍历算法

    C语言数据结构之二叉树的非递归后序遍历算法 前言: 前序.中序.后序的非递归遍历中,要数后序最为麻烦,如果只在栈中保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈中. 方法有很多,这里只举一种,先定义栈结点的数据结构 typedef struct{Node * p; int rvisited;}SNode //Node 是二叉树的结点结构,rvisited==1代表p所指向的结点的右结点已被访问过. lastOrderTraverse(BiTree bt){ //首先,从根节点开始,

  • C语言二叉树的非递归遍历实例分析

    本文以实例形式讲述了C语言实现二叉树的非递归遍历方法.是数据结构与算法设计中常用的技巧.分享给大家供大家参考.具体方法如下: 先序遍历: void preOrder(Node *p) //非递归 { if(!p) return; stack<Node*> s; Node *t; s.push(p); while(!s.empty()) { t=s.top(); printf("%d\n",t->data); s.pop(); if(t->right) s.pus

  • C语言非递归后序遍历二叉树

    本文实例为大家分享了C语言非递归后序遍历二叉树的具体代码,供大家参考,具体内容如下 法一:实现思路:一个栈 先按 根->右子树->左子树的顺序访问二叉树.访问时不输出.另一个栈存入前一个栈只进栈的结点. 最后输出后一个栈的结点数据. #include<stdio.h> #include<stdlib.h> typedef struct TreeNode{ char element; struct TreeNode *left,*right; }Tree,*BTree;

  • C#非递归先序遍历二叉树实例

    本文实例讲述了C#非递归先序遍历二叉树的方法.分享给大家供大家参考.具体如下: using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace ConsoleApplication5 { class Program { static void Main(string[] args) { Node treeRoo

  • 二叉树的非递归后序遍历算法实例详解

    前序.中序.后序的非递归遍历中,要数后序最为麻烦,如果只在栈中保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈中.方法有很多,这里只举一种,先定义栈结点的数据结构 复制代码 代码如下: typedef struct{Node * p; int rvisited;}SNode //Node 是二叉树的结点结构,rvisited==1代表p所指向的结点的右结点已被访问过. lastOrderTraverse(BiTree bt){ //首先,从根节点开始,往左下方走,一直走到头,将路径上

  • 探讨:C++实现链式二叉树(用非递归方式先序,中序,后序遍历二叉树)

    如有不足之处,还望指正! 复制代码 代码如下: // BinaryTree.cpp : 定义控制台应用程序的入口点.//C++实现链式二叉树,采用非递归的方式先序,中序,后序遍历二叉树#include "stdafx.h"#include<iostream>#include<string>#include <stack>using namespace std;template<class T>struct BiNode{ T data; 

  • PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例

    本文实例讲述了PHP基于非递归算法实现先序.中序及后序遍历二叉树操作.分享给大家供大家参考,具体如下: 概述: 二叉树遍历原理如下: 针对上图所示二叉树遍历: 1. 前序遍历:先遍历根结点,然后遍历左子树,最后遍历右子树. ABDHECFG 2.中序遍历:先遍历左子树,然后遍历根结点,最后遍历右子树. HDBEAFCG 3.后序遍历:先遍历左子树,然后遍历右子树,最后遍历根节点. HDEBFGCA 实现方法: 先序遍历:利用栈先进后出的特性,先访问根节点,再把右子树压入,再压入左子树.这样取出的

  • C++ 非递归实现二叉树的前中后序遍历

    目录 二叉树的前序遍历 二叉树的中序遍历 二叉树的后序遍历 二叉树的前序遍历 在不使用递归的方式遍历二叉树时,我们可以使用一个栈模拟递归的机制.二叉树的前序遍历顺序是:根 → 左子树 → 右子树,我们可以先将二叉树的左路结点入栈,在入栈的同时便对其进行访问,此时就相当于完成了根和左子树的访问,当左路结点入栈完毕后再从栈顶依次取出结点,并用同样的方式访问其右子树即可. 具体步骤如下: 将左路结点入栈,入栈的同时访问左路结点. 取出栈顶结点top. 准备访问top结点的右子树. struct Tre

  • 二叉树递归迭代及morris层序前中后序遍历详解

    目录 分析二叉树的前序,中序,后序的遍历步骤 1.层序遍历 方法一:广度优先搜索 方法二:递归 2.前序遍历 3.中序遍历 4.后序遍历 递归解法 前序遍历--递归 迭代解法 前序遍历--迭代 核心思想: 三种迭代解法的总结: Morris遍历 morris--前序遍历 morris--中序遍历 morris--后序遍历: 分析二叉树的前序,中序,后序的遍历步骤 1.层序遍历 方法一:广度优先搜索   (以下解释来自leetcode官方题解) 我们可以用广度优先搜索解决这个问题. 我们可以想到最

  • 先序遍历二叉树的递归实现与非递归实现深入解析

    1.先序遍历二叉树  递归实现思想:若二叉树为空,返回.否则 1)遍历根节点:2)先序遍历左子树:3)先序遍历右子树: 代码: 复制代码 代码如下: template<typename elemType> void PreOrder(nodeType<elemType> *root)  {      if(root==NULL)          return ;      visit(root->data); // visit the data    PreOrder(ro

  • java非递归实现之二叉树的前中后序遍历详解

    二叉树的前中后序遍历 核心思想:用栈来实现对节点的存储.一边遍历,一边将节点入栈,在需要时将节点从栈中取出来并遍历该节点的左子树或者右子树,重复上述过程,当栈为空时,遍历完成. 前序遍历 //非递归 //根 左 右 class Solution { public List<Integer> preorderTraversal(TreeNode root) { //用数组来存储前序遍历结果 List<Integer> list = new ArrayList<>(); i

随机推荐