postorder.cpp

来自「数据结构的一些简单编程题,二叉树结构」· C++ 代码 · 共 55 行

#include<stdio.h>
#include<malloc.h>
typedef struct BiTNode{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
bool CreateBiTree(BiTree &T){
	char ch;
	scanf("%c",&ch);
	if (ch=='0') T=NULL;
	else {
	       T=(BiTNode *)malloc(sizeof(BiTNode));
		   T->data=ch;
		   CreateBiTree(T->lchild);
		   CreateBiTree(T->rchild);
	}return 1;
}
void postorder( BiTree  &T){
     BiTree stack[100],p;
     int tag[100], top=0; 
     p=T;
     do
       { while (p!=NULL)                   //扫描左结点
            { top++;
               stack[top]=p;
               tag[top]=0;
               p=p->lchild;
            }
          
               //p所指结点为无左子树的结点或其左子树已遍历过
	      if(top>0){
		     if(tag[top]==1)
			 {                                     // p的左右子树都访问过
				 printf("%c",stack[top]->data);top--;
			 }
		   else{p=stack[top];
		        if(top>0){p=p->rchild; tag[top]=1;}//访问结点
		   }
		  }
	  
	  
	   
                                                 //扫描右子树
                      //表示当前结点的右子树已访问过
                 } while ((p!=NULL)&&(top!=0));
	 
   }

void main(){
    BiTree T=NULL;
	CreateBiTree(T); 
	printf("后序序列为：");
   postorder(T);
	printf("\n");
}