如何实现C语言中非递归的后序二叉树遍历算法？

本文共计1234个文字，预计阅读时间需要5分钟。

本文以一个实例展示了如何使用C语言实现非递归后序遍历二叉树的整体代码。以下是大致的思路和代码实现：

法一：实现思路

使用一个栈来模拟递归过程，具体步骤如下：

1. 初始化一个栈。

2.从根节点开始，依次将左子树节点和右子树节点压入栈中。

3.当栈不为空时，从栈顶取出节点，访问该节点。

4.如果该节点有右子树，则将右子树节点压入栈中。

5.如果该节点有左子树，则将左子树节点压入栈中。

6.重复步骤3-5，直到栈为空。

代码实现

c

#include #include

// 定义二叉树节点结构体typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right;} TreeNode;

// 创建新节点TreeNode* createNode(int val) { TreeNode* newNode=(TreeNode*)malloc(sizeof(TreeNode)); newNode->val=val; newNode->left=NULL; newNode->right=NULL; return newNode;}

// 非递归后序遍历二叉树void postorderTraversal(TreeNode* root) { if (root==NULL) return;

TreeNode* stack[100]; // 定义一个栈，大小为100 int top=-1; // 栈顶指针

// 将根节点压入栈中 stack[++top]=root;

while (top >=0) { TreeNode* node=stack[top--]; // 取出栈顶节点 printf(%d , node->val); // 访问节点

// 先将右子树压入栈中，因为后序遍历需要先访问左子树 if (node->right) stack[++top]=node->right; if (node->left) stack[++top]=node->left; }}

int main() { // 创建二叉树示例 TreeNode* root=createNode(1); root->left=createNode(2); root->right=createNode(3); root->left->left=createNode(4); root->left->right=createNode(5);

// 执行非递归后序遍历 postorderTraversal(root);

return 0;}

总结

本文介绍了使用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; }

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持自由互联。