//定義二叉樹的函數
#include "stdafx.h"
#include "BiTree.h"
#include "Queue.h"
#include "GlobalDefining.h"
#include <iostream.h>
//二叉排序樹的插入操作
void Insert_SortTree (BiTree &ST, int x)
{ 		   
	BiTNode *s,*t; 
	BiTNode* p = new BiTNode;
    p->data = x;
	p->lchild = NULL;
	p->rchild = NULL;
	if(ST == NULL)
		ST = p;
	s = ST; 
	while(s != NULL)
	{  
		 t = s;               //t用來記錄s的雙親結點
		 if(s->data > x)
		 s = s->lchild;
		 else if(s->data < x)
		 s = s->rchild;
		 else
            return;

	}
    if(t->data > x)             //比較x與t的data的大小確定插入的位置
		t->lchild = p;
	else
	    t->rchild = p;
}
		
//二叉樹的中序遍歷算法
void InOrderTraverse (BiTree  ST)
{
        if (ST)
        {   
        	InOrderTraverse (ST->lchild);   //利用遞歸算法實現遍歷
	        cout<<ST->data<<",";
        	InOrderTraverse (ST->rchild);
        }

}


//定義隊列的操作
STATUS InitQueue (SqQueue &Q)
{
    if (Q.base == NULL) 
		return OVERFLOW;  
    Q.queuesize = MAXQSIZE;
    Q.front = 0;
    Q.rear = 0;
    return OK;
}// 構造一個最大存儲空間為 maxsize 的空循環隊列 Q


STATUS EnQueue (SqQueue &Q, BiTNode *e)
{  
    if ((Q.rear+1) % Q.queuesize == Q.front) 
        return ERROR;                        //隊列滿則返回ERROR
    Q.rear = (Q.rear+1) % Q.queuesize;
    Q.base[Q.rear] = e;
    return OK;
}// 插入元素e為Q的新的隊尾元素

STATUS DeQueue (SqQueue &Q, BiTNode *&e)
{  
    if (Q.front == Q.rear)                   //隊列空則返回ERROR
		return ERROR;
    Q.front = (Q.front+1) % Q.queuesize;
    e = Q.base[Q.front];
    return OK;
}// 若隊列不空，則刪除Q的隊頭元素，用e返回其值，并返回OK;  否則返回ERROR

//二叉樹的層次遍歷函數
void LevelTraverse (BiTree T)
{
	SqQueue Q;
    InitQueue(Q);               //定義一循環隊列并初始化
    if(T != NULL)  
	   EnQueue(Q, T);
    BiTNode *p = T;
    while (Q.rear != Q.front)
    {
        DeQueue(Q, p);
        cout<<p->data<<",";

        if(p->lchild != NULL) 
	    EnQueue(Q, p->lchild);  //左兒子入隊

        if(p->rchild != NULL)
	    EnQueue(Q, p->rchild); //右兒子入隊
    }
}