"C语言非递归后序遍历二叉树"
本文主要介绍了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;
}
```
二、法二：标记思路
在法二中，我们使用标记来实现非递归后序遍历二叉树。我们首先按照先序遍历访问每一个结点，并将结点存入栈中。当为空时，就出栈立即。出栈后应该立即进栈，去访问进栈结点的右结点，这样可以保证先输出左、右结点，再输出根结点。我们使用标记来标记结点的访问顺序。
代码示例：
```c
#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;
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;
S=Init_Stack();
Push_Stack(S,T);
while(!empty_Stack(S)){
BTree p=Pop_Stack(S)->data;
if(p->flag){
printf("%c",p->element);
}else{
Push_Stack(S,p);
p->flag=1;
if(p->right){
Push_Stack(S,p->right);
}
if(p->left){
Push_Stack(S,p->left);
}
}
}
DestroyStack(S);
}
int main(void){
BTree T;
T=BuildTree();
NotRecursionPostOrder(T);
return 0;
}
```
非递归后序遍历二叉树可以使用栈或标记来实现，这两种方法都可以实现非递归后序遍历二叉树，但它们之间有一些差异。在实际应用中，我们可以根据具体情况选择合适的方法。
