1. 原理图： 
  2.  
  3. 源程序代码： 
  4.  
  5. //PostOrderTraverse.cpp 
  6. //This function is to postorder BiTree 
  7. # include <malloc.h> 
  8. # include <iostream> 
  9. # include <conio.h> 
  10. # define OK 1 
  11. # define ERROR 0 
  12.  
  13. using namespace std; 
  14.  
  15. typedef char TElemType; 
  16.  
  17. typedef struct BiTNode  //define structure BiTree 
  18. {  TElemType data; 
  19.    struct BiTNode *lchild,*rchild; 
  20. }BiTNode, *BiTree; 
  21.  
  22. int CreateBiTree(BiTree &T) //createBiTree() sub-function 
  23. {  TElemType ch; 
  24.    cout<<"Please input data (/ for NULL node!) : "; 
  25.    cin>>ch; 
  26.    if(ch=='/')  T=NULL; 
  27.    else 
  28.    {  if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) 
  29.       {  cout<<"Overflow!"; //no alloction 
  30.   return (ERROR); 
  31.       } 
  32.       T->data=ch; 
  33.       CreateBiTree(T->lchild); //create lchild 
  34.       CreateBiTree(T->rchild);  //create rchild 
  35.    } 
  36.    return (OK); 
  37. } //CreateBiTree() end 
  38.  
  39. int PostOrderTraverse(BiTree T) //PostOrderTraverse() sub-function 
  40. { 
  41.    if(T) 
  42.    {  if (PostOrderTraverse(T->lchild))  //traverse lchild 
  43.      if(PostOrderTraverse(T->rchild)) //traverse rchild 
  44.      {    cout<<T->data<<"->";  //visite T 
  45.        return (OK); 
  46.         } 
  47.  return (ERROR); 
  48.    } 
  49.    else 
  50.       return (OK); 
  51. } //PostOrderTraverse() end 
  52. int   CentralOrderTraverse(BiTree  T) 
  53. { 
  54.   if(T) 
  55.      {  if (CentralOrderTraverse(T->lchild))  //traverse lchild 
  56.      {  cout<<T->data<<"->";  //visite T 
  57.        if(CentralOrderTraverse(T->rchild)) //traverse rchild 
  58.           return (OK); 
  59.      } 
  60.       return (ERROR); 
  61.      } //if end 
  62.    else 
  63.       return (OK); 
  64. } 
  65. int  preOrderTraverse(BiTree T) 
  66. { 
  67.   if(T) 
  68.    {    cout<<T->data<<"->";  //visite T 
  69.        if (PostOrderTraverse(T->lchild))  //traverse lchild 
  70.      if(PostOrderTraverse(T->rchild))  
  71.         return OK; //traverse rchild 
  72.       return (ERROR); 
  73.    } 
  74.    else 
  75.       return (OK); 
  76. } 
  77. int main()   //main() function 
  78. {  BiTree T; 
  79.    cout<<endl<<endl<<"PostOrderTraverse.cpp"; 
  80.    cout<<endl<<"========================="; 
  81.    cout<<endl<<endl<<"Please input data to create BiTree:"<<endl; 
  82.    CreateBiTree(T);  //call CreateBiTree 
  83.    std::cout<<"先序遍历:"<<endl; 
  84.    PostOrderTraverse(T); 
  85.    std::cout<<"中序遍历:"<<endl; 
  86.    CentralOrderTraverse(T);   
  87.    std::cout<<"后序遍历:"<<endl; 
  88.    preOrderTraverse(T);   
  89.    cout<<"End !"<<endl<<endl<<"...OK!..."; 
  90.    getch(); 
  91.    return 0; 
  92. } //main() 
  93.  
  94.