C 언어 비 재 귀적 후 순서 로 이 진 트 리 를 옮 겨 다 닙 니 다.

본 논문 의 사례 는 C 언어 가 재 귀적 이지 않 은 후 순서 로 이 진 트 리 를 옮 겨 다 니 는 구체 적 인 코드 를 공유 하여 여러분 께 참고 하 시기 바 랍 니 다.구체 적 인 내용 은 다음 과 같 습 니 다.
법 1:사고 실현:한 스 택 은 뿌리->오른쪽 하위 트 리->왼쪽 하위 트 리 의 순서 로 이 진 트 리 에 접근 합 니 다.접근 할 때 출력 하지 않 습 니 다.다른 스 택 은 이전 스 택 에 저장 하고 스 택 의 결산 점 에 만 들 어 갑 니 다.
마지막 으로 다음 스 택 의 결산 데 이 터 를 출력 합 니 다.

#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;
} 

법 2:사고 실현.모든 노드 에 선착순 으로 접근 합 니 다.스 택 에 저장 하고 비어 있 을 때 바로 스 택 을 나 갑 니 다(처음 스 택 을 나 갑 니 다).스 택 을 나 간 후에 바로 스 택 에 들 어가 서 스 택 노드 의 오른쪽 결산 점 을 방문 해 야 합 니 다.그러면 먼저 왼쪽,오른쪽 결산 점 을 출력 한 다음 에 루트 결산 점 을 출력 할 수 있 습 니 다.2 차 창고 에 들 어가 서 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;
}

이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.