栈存储

1.利用递归前序遍历创建二叉树，利用栈存储的方式，中序遍历二叉树并输出。

1 #include
     
       2 using namespace std; 3 #include
      
         4 #include
       
         5  6 typedef struct BiTNode{ 7 char data; 8     struct BiTNode *lchild,*rchild; 9 }BiTNode,*BiTree;10 11 typedef struct{12 BiTree *base;13 BiTree  *top;14     int stacksize;15 }SqStack;16 17 void creat(BiTree &T){18     char ch;19     cin>>ch;20     T=(BiTree )malloc(sizeof(BiTNode));21 22         if(ch=='#')T=NULL;23         else{24             T->data=ch;25             creat(T->lchild);26             creat(T->rchild);27         }28                 29 }30 31 32 void     InitStack(SqStack &S){33     S.base=S.top=(BiTree *)malloc(100*sizeof(BiTree));34     S.stacksize=100;35 }36 void Push(SqStack &S,BiTree T){37 38     *S.top++=T;39     40 }41 void Pop(SqStack &S,BiTree &T){42     if(S.top!=S.base)43     T=*--S.top;44 }45 void GetPop(SqStack &S,BiTree &e){46     e=*(S.top-1);47 }48 49 void Inoder(BiTree T){50     BiTree p;51     SqStack S;52 InitStack(S);53     Push(S,T);54     while(S.base!=S.top){55         GetPop(S,p);56         while(p){57             Push(S,p->lchild);58             GetPop(S,p);59             60         }61         Pop(S,p);62         if(S.base!=S.top){63             Pop(S,p);64             cout<
        
         data;65             Push(S,p->rchild);66             67         }68     }69     cout<
        
       
      
     

 

 

运行截图：输入树，叶子节点以#结束

 

二 递归遍历

此外，利用递归的方式对二叉树，进行前序中序和后序遍历

 

2.使用递归的前序遍历，中序遍历代码。void PreOrder(BinTree T)//前序遍历二叉树  {      if(T!=NULL)      {          cout<
     
      data;          PreOrder(T->lchild);          PreOrder(T->rchild);      }  }    void InOrder(BinTree T)//中序遍历二叉树  {      if(T!=NULL)      {          InOrder(T->lchild);          cout<
      
       data;          InOrder(T->rchild);      }  }    void PostOrder(BinTree T)//后序遍历二叉树  {      if(T!=NULL)      {          PostOrder(T->lchild);          PostOrder(T->rchild);          cout<
       
        data;      }  }