C語言非遞歸實現二叉樹的先序、中序、後序遍歷

C語言非遞歸實現二叉樹的先序、中序、後序遍歷

#include     
#include     
#define INIT_STACK_SIZE 100    
#define STACKINCREMENT 10    
    
//*****二叉樹的二叉鏈表存儲結構*****//
typedef struct BiNode    
{    
    char data;    
    struct BiNode *lchild, *rchild;   
    int visitcount;					//訪問次數(後序遍歷會用到)
}BiNode, *BiTree;    
    
typedef struct    
{    
    BiNode **base;    
    BiNode **top;    
    int stacksize;    
}SqStack;    

//*****初始化棧*****//   
void InitStack(SqStack &S)                 
{    
    if (!(S.base = (BiNode **)malloc(sizeof(BiTree) * INIT_STACK_SIZE)))    
    {    
        return;    
    }    
    S.top = S.base;    
    S.stacksize = INIT_STACK_SIZE;    
    
    return;    
}    
    
//*****元素進棧*****//
void Push(SqStack &S, BiNode *e)           
{    
    if (S.top - S.base >= S.stacksize)    
    {    
        if (!(S.base = (BiNode **)realloc(S.base, sizeof(BiTree) * (STACKINCREMENT + S.stacksize))))  
        {    
            return;    
        }    
        S.stacksize += STACKINCREMENT;    
    }    
    *S.top++ = e;    
    
    return;    
}    
    
//*****元素出棧*****//
void Pop(SqStack &S, BiNode **e)           
{    
    if (S.base == S.top)    
    {    
        return;    
    }    
    *e = *--S.top;    
    
    return;    
}    

//*****取棧頂元素*****//    
int GetTop(SqStack S, BiNode **e)    
{    
    if (S.base == S.top)    
    {    
        return 0;    
    }    
    *e = *(S.top - 1);    
        
    return 1;    
}    
    
//*****判斷棧是否為空*****//  
int StackEmpty(SqStack S)         
{    
    if (S.top == S.base)    
        return 1;    
    else    
        return 0;    
}    

//*****按先序次序輸入二叉樹中結點的值(一個字符)，空格字符表示空樹構造二叉鏈表表示的二叉樹T*****//    
void CreateBiTree(BiTree &T)            
{                                       
    char ch;      
    scanf("%c", &ch);      
    if(ch == ' ')      
    {      
        T = NULL;      
    }      
    else      
    {      
        if(!(T = (BiNode *)malloc(sizeof(BiNode))))       
        {      
            return;      
        }      
        T->data = ch;                    //生成根結點      
        CreateBiTree(T->lchild);     //構造左子樹      
        CreateBiTree(T->rchild);     //構造右子樹      
    }      
        
    return;      
}      

//*****先序遍歷二叉樹方法1*****// 
void PreorderTraverse_1(BiTree T)                       
{  
    BiTree p;  
    SqStack S;  
    InitStack(S);  
    Push(S, T);                                         //根指針進棧  
    while(!StackEmpty(S))  
    {  
        while(GetTop(S, &p) && p)   
        {                                                 
            printf("%c ", p->data);                        
            Push(S, p->lchild);   
        }  
        Pop(S, &p);                                     //空指針退棧    
        if(!StackEmpty(S))  
        {  
            Pop(S, &p);                                 //根結點出棧  
            Push(S,p->rchild);                           //右孩子進棧  
        }  
    }  
	
    return;  
}  

//*****先序遍歷二叉樹方法2*****// 
void PreorderTraverse_2(BiTree T)                         
{    
    BiTree p = T;    
    SqStack S;    
    InitStack(S);    
	
    while (p || !StackEmpty(S))    
    {    
        if (p)    
        {    
            printf("%c ", p->data);  
            Push(S,p);    
            p = p->lchild;    
        }    
        else    
        {    
            Pop(S, &p);    
            p = p->rchild;    
        }    
    }    
} 

//*****中序遍歷二叉樹方法1*****// 
void InOrderTraverse_1(BiTree T)                        
{  
    SqStack S;  
    BiTree p;  
    InitStack(S);  
    Push(S,T);     
    while (!StackEmpty(S))  
    {  
        while (GetTop(S,&p) && p)    
        {  
            Push(S,p->lchild);                           //向左走到盡頭  
        }  
        Pop(S,&p);                                      //空指針退棧    
        if (!StackEmpty(S))  
        {    
            Pop(S,&p);    
            printf("%c ", p->data);  
            Push(S,p->rchild);  
        }  
    }  
	
    return;  
}  

//*****中序遍歷二叉樹方法2*****// 
void InOrderTraverse_2(BiTree T)                         
{    
    BiTree p = T;    
    SqStack S;    
    InitStack(S);    
	
    while (p || !StackEmpty(S))    
    {    
        if (p)    
        {    
            Push(S,p);    
            p = p->lchild;    
        }    
        else    
        {    
            Pop(S, &p);    
            printf("%c ", p->data);    
            p = p->rchild;    
        }    
    }   
	
    return;  
}         

//*****後序遍歷二叉樹*****// 
void PostOrderTraverse(BiTree T)  
{  
    SqStack S;  
    BiTree p = T;  
    InitStack(S);  
      
    while (p || !StackEmpty(S))  
    {  
        if(p)  
        {  
            if (p->visitcount != 2)  
            {  
                p->visitcount = 1;  
                Push(S, p);  
            }  
            p = p->lchild;  
        }  
        else   
        {             
            Pop(S, &p);    
            if(p->visitcount == 2)  
            {  
                printf("%c ", p->data);    
            }  
            else   
            {   
                p->visitcount++;   
                Push(S, p);  
            }  
            p = p->rchild;  
        }  
    }  
      
    return;  
}  
  
int main(void)    
{    
    BiTree T;    
    printf("請按先序次序輸入二叉樹中結點的值(字符)，空格字符表示空樹:\n");
	CreateBiTree(T);    
    
	printf("先序遍歷方法1結果為:");
	PreorderTraverse_1(T);
	printf("\n\n"); 

	printf("先序遍歷方法2結果為:");
	PreorderTraverse_2(T);
	printf("\n\n"); 

	printf("中序遍歷方法1結果為:");
	InOrderTraverse_1(T);
	printf("\n\n"); 
	
	printf("中序遍歷方法2結果為:");
	InOrderTraverse_2(T);
	printf("\n\n"); 

	printf("後序遍歷結果為:");
	PostOrderTraverse(T);    
    printf("\n\n");    
    
    return 0;    
}    

以如下二叉樹為例，給出按先序次序輸入二叉樹中結點的值（字符），從而按照本文給出的算法構造二叉樹。

輸入字符的順序是：-+a空格空格*b空格空格-c空格空格d空格空格/e空格空格f空格空格，即可驗證本文給出的遍歷算法。