[데이터 구조] 이 진 트 리 의 재 귀 와 비 재 귀 옮 겨 다 니 기

입력                                   A
                           B                          C
                D               E           F             G
          H        I       J
선착순 으로 옮 겨 다 니 며 "\ #" 로 비 어 있 음 을 표시 하고 ABDH \ # \ # I \ # \ # EJ \ # \ # \ # CF \ # \ # G \ # \ # 를 입력 하 십시오.
앞 순서 옮 겨 다 니 기: 뿌리 - > 왼쪽 - > 오른쪽 ABDHIEJCFG
중간 순서: 왼쪽 - > 뿌리 - > 오른쪽 HDIBJEAFCG
뒤 순 옮 겨 다 니 기: 왼쪽 - > 오른쪽 - > 뿌리 HIDJEBFGCA

#include <iostream>
#include <stack>
#include <queue> 
using namespace std;  

typedef char Elementtype;

typedef struct node  
{  
    struct node *lchild;  
    struct node *rchild;  
    Elementtype data;
}BiTreeNode, *BTREE;  
      
void CreateBTree(BTREE &T) //          
{  
    char c;  
    cin >> c;  
    if('#' == c)  
      T = NULL;  
    else  
    {  
        T = new node;  
        T->data = c;
        CreateBTree(T->lchild);  //     
        CreateBTree(T->rchild);  
    }  
}  

int IsEmpty(BTREE root)
{
    if (root == NULL)
      return 1;
    else
      return 0;
}

void Visit(Elementtype data)
{
    printf("%c ",data);
}
void InOrder(BTREE root)//     
{
    if (IsEmpty(root) == 0)
    {
        InOrder(root->lchild);
        Visit(root->data);
        InOrder(root->rchild);
    }
}

void PreOrder(BTREE root){//     
    if(IsEmpty(root) == 0){
        Visit(root->data);
        PreOrder(root->lchild);
        PreOrder(root->rchild);
    }
}
void PostOrder(BTREE root){//     
    if(IsEmpty(root) == 0){
        PostOrder(root->lchild);
        PostOrder(root->rchild);
        Visit(root->data);
    }
}

void N_InOrder(BTREE T)//        
{
	stack<BTREE> STACK;
	if(IsEmpty(T))
    {
    	cout << "Empty Tree!" << endl;
    	return;
    }
    while(T || !STACK.empty())
	{
		while(T)
		{
			STACK.push(T);
			T=T->lchild;
		}
		T=STACK.top();
		STACK.pop();
		printf("%c ",T->data);
		T=T->rchild;
	}              
}

void N_PreOrder(BTREE T)
{
	stack<BTREE> STACK;
	if(IsEmpty(T))
    {
    	cout << "Empty Tree!" << endl;
    	return;
    }
    while(T || !STACK.empty())
	{
		while(T)
		{
			STACK.push(T);
			printf("%c ",T->data);
			T=T->lchild;
		}
		T=STACK.top();
		STACK.pop();		
        T=T->rchild;		
	}
} 

void N_PostOrder(BTREE T) //           
{  
    stack<BTREE> STACK;  
    BTREE curr = T ;           //           
    BTREE previsited = NULL;    //            
    while(curr != NULL || !STACK.empty())  //       
    {  
        while(curr != NULL)            //         
        {  
            STACK.push(curr);  
            curr = curr->lchild;  
        }  
        curr = STACK.top();
        
		//                   ，       
        if(curr->rchild == NULL || curr->rchild == previsited)  
        {  
            cout<<curr->data<<" ";  
            previsited = curr;  
            STACK.pop();  
            curr = NULL;  
        }  
        else
          curr = curr->rchild;//       
    }  
} 

void N_PostOrder_S(BTREE T)  //           
{  
    stack<BTREE> s1,s2;  
    BTREE curr ;        //          
    s1.push(T);
    while(!s1.empty())  //       
    {
        curr = s1.top();
        s1.pop();
        s2.push(curr);
        if(curr->lchild)
            s1.push(curr->lchild);
        if(curr->rchild)
            s1.push(curr->rchild);
    }
    while(!s2.empty())
    {
        printf("%c ", s2.top()->data);
        s2.pop();
    }
}

int visit(BTREE T)
{
    if(T)
    {
        printf("%c ",T->data);
        return 1;
    }
    else
        return 0;
}

void Traverse(BTREE T)//          
{
    queue<BTREE> Q;
    BTREE p;
    p = T;
    if(visit(p)==1)
        Q.push(p);
    while(!Q.empty())
    {
        p = Q.front();
        Q.pop();
        if(visit(p->lchild) == 1)
            Q.push(p->lchild);
        if(visit(p->rchild) == 1)
            Q.push(p->rchild);
    }
}

int main()  
{  
    BTREE T;  
    CreateBTree(T);  
    InOrder(T);
    cout << endl;
    N_InOrder(T);
    cout << endl;
    N_PreOrder(T);
    cout << endl;
    N_PostOrder(T); 
    cout << endl;
    N_PostOrder_S(T);
    cout << endl;
    Traverse(T);
    cout << endl;
    return 0;  
}