C语言非递归后序遍历二叉树-创新互联

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

成都创新互联专注于西塞山企业网站建设,自适应网站建设,商城网站定制开发。西塞山网站建设公司,为西塞山等地区提供建站服务。全流程定制网站设计,专业设计,全程项目跟踪,成都创新互联专业和态度为您提供的服务

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

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

另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


新闻标题:C语言非递归后序遍历二叉树-创新互联
文章地址:http://myzitong.com/article/dheogj.html