学步园

在树的中序遍历中需要用到栈，在层次遍历中需要用到队列，下面就是树的结构：

代码实现：

#include <stdio.h>
#include <stdlib.h>

// TreeNode
//////////////////////////////////////////////////////////////////////////
typedef struct TreeNode
{
    char m_cVal;
    TreeNode* m_pLeft;
    TreeNode* m_pRight;

    TreeNode(char cVal);
    ~TreeNode();
};

TreeNode::TreeNode(char cVal)
{
    m_cVal = cVal;
    m_pLeft = 0;
    m_pRight = 0;
}

TreeNode::~TreeNode()
{

}

//Stack
//////////////////////////////////////////////////////////////////////////
class Stack
{
public:
    Stack(int iAmount = 10);
    ~Stack();

//return 1 means succeeded, 0 means failed.
    int Pop(TreeNode* &pVal);
    int Push(TreeNode* pVal);
    int Top(TreeNode* &pVal);

//1 means not null, 0 means null.
    int NotNull();
private:
    TreeNode **m_ppData;
    int m_iCount;
    int m_iAmount;
};

Stack::Stack(int iAmount)
{
    m_ppData = new TreeNode*[iAmount];
    m_iCount = 0;
    m_iAmount = iAmount;
}

Stack::~Stack()
{
    delete m_ppData;
}

int Stack::Pop(TreeNode* &pVal)
{
    if(m_iCount>0)
    {
        --m_iCount;
        pVal = m_ppData[m_iCount];
        return 1;
    }
    return 0;
}

int Stack::Push(TreeNode* pVal)
{
    if(m_iCount<m_iAmount)
    {
        m_ppData[m_iCount] = pVal;
        ++m_iCount;
        return 1;
    }
    return 0;
}

int Stack::Top(TreeNode* &pVal)
{
    if(m_iCount>0 && m_iCount<=m_iAmount)
    {
        pVal = m_ppData[m_iCount-1];
        return 1;
    }
    return 0;
}

int Stack::NotNull()
{
    if(m_iCount!=0)
        return 1;
    return 0;
}

//Queue
//////////////////////////////////////////////////////////////////////////
class Queue
{
public:
    Queue(int nMounts);
    ~Queue();
    
    //operator
    int EnQueue(TreeNode *node);
    int DeQueue(TreeNode *&node);
    int IsFull();
    int IsEmpty();
    
private:
    TreeNode **Q;
    int front;
    int rear;
    int totalNode;
};

Queue::Queue(int nMounts = 10){
	Q = new TreeNode*[nMounts];
	totalNode = nMounts;
	rear = 0;
	front = 0;
}

Queue::~Queue(){
	delete Q;
}

int Queue::EnQueue(TreeNode *node){
	if(!IsFull()){
		Q[rear] = node;
		rear = (rear + 1) % totalNode;
	}else{
		//printf("Queue is full!\n");
		return 0;
	}
	
	return 1;
}

int Queue::DeQueue(TreeNode *&node){
	if(!IsEmpty()){
		node = Q[front];
		front = (front + 1) % totalNode;
	}else{
		//printf("Queue is empty!\n");
		return 0;
	}
	return 1;
}

int Queue::IsFull(){
	if((rear + 1) % totalNode == front){
		return 1;
	}
	return 0;
}

int Queue::IsEmpty(){
	if(rear == front){
		return 1;
	}
	return 0;
}


int main(int argc, char* argv[])
{
    TreeNode nA('A');
    TreeNode nB('B');
    TreeNode nC('C');
    TreeNode nD('D');
    TreeNode nE('E');
    TreeNode nF('F');
    TreeNode nG('G');
    TreeNode nH('H');
    TreeNode nI('I');
    TreeNode nJ('J');
    TreeNode nK('K');
    TreeNode nL('L');

    nA.m_pLeft = &nB;
    nA.m_pRight = &nC;
    nB.m_pRight = &nD;
    nD.m_pRight = &nG;
    nC.m_pLeft = &nE;
    nC.m_pRight = &nF;
    nF.m_pRight = &nH;
    nH.m_pLeft = &nI;
    nH.m_pRight = &nJ;
    nI.m_pLeft = &nK;
    nI.m_pRight = &nL;

    Stack st;
	
	//非递归中序遍历 
    TreeNode *pVal = &nA;
    int iPopped = 0;
    while(pVal!=0)
    {
        if(pVal->m_pLeft!=0 && iPopped==0)
        {
            st.Push(pVal);
            pVal = pVal->m_pLeft;
            iPopped = 0;
        }
        else if(pVal->m_pRight!=0)
        {
            printf("%c ", pVal->m_cVal);
            pVal = pVal->m_pRight;
            iPopped = 0;
        }
        else
        {
            printf("%c ", pVal->m_cVal);
            if(0==st.Pop(pVal))
                break;
            iPopped = 1;
        }
    }
    
    printf("\n");
    
    //层次遍历 
    pVal = &nA;
    Queue queue;
    while(pVal != NULL){
    	if(pVal->m_pLeft != NULL && pVal->m_pRight != NULL){
	    	queue.EnQueue(pVal->m_pLeft);
			queue.EnQueue(pVal->m_pRight);
	    }else if(pVal->m_pLeft != NULL){
    		queue.EnQueue(pVal->m_pLeft);
    	}else if(pVal->m_pRight != NULL){
	    	queue.EnQueue(pVal->m_pRight);
	    }
   		printf("%c ", pVal->m_cVal);
   		if(0 == queue.DeQueue(pVal)){
		   	break;
   		}
    }
	printf("\n");
    return 0;
}