ツリーのリニアストレージ


/***************************************************
 
by Rowandjj
2014/5/23
***************************************************/
#include
#include
using namespace std;

#define MAX 255
#define NIL -1
typedef struct _POSITION_
{
    int level;// 
    int order;// 
    
}Position,*pPosition;

// i, (i+1)/2-1
// i, i*2+1,i*2+2
// i, j, pow(2,i-1)+j-2
void InitTree(int *T);
void CreateTree(int *T);
int GetDepth(int *T);
bool GetRoot(int *T,int *e);
bool IsEmpty(int *T);
bool GetValue(int *T,Position pos,int *e);
bool Assign(int *T,Position pos,int iValue);
void MidTravel(int *T,int i);
void PreTravel(int *T,int i);
void PosTravel(int *T,int i);
void LevelTravel(int *T);
int GetParent(int *T,int e);
int GetLeftChild(int *T,int e);
int GetRightChild(int *T,int e);
int GetLeftSibling(int *T,int e);
int GetRightSibling(int *T,int e);
void InsertNode(int *T,);

void InitTree(int *T)
{
    int i;
    for(i = 0; i < MAX; i++)
    {
        *(T + i) = NIL;
    }
}

void CreateTree(int *T)
{
    int i = 0;
    int a;
    while(true)
    {
        cin>>a;
        if(a == NIL)
        {
            break;
        }
        if(i!=0 && T[(i+1)/2-1]==NIL && a!=NIL)
        {
            return;    
        }
        
        T[i] = a;
        i++;
    }
}
int GetDepth(int *T)
{
    int i = MAX - 1;
    while(T[i] == NIL)
    {
        i--;    
    }
    i++;
    int j = 0;
    while(i >= pow(2,j))
    {
        j++;
    }
    return j;
}
bool IsEmpty(int *T)
{
    return T[0]!=NIL ? false : true;
}

bool GetRoot(int *T,int *e)
{
    if(IsEmpty(T))
    {
        return false;
    }else
    {
        *e = T[0];
        return true;
    }
}

bool GetValue(int *T,Position pos,int *e)
{
    int index = pow(2,pos.level-1)+pos.order-2;
    if(T[index] == NIL)
    {
        return false;
    }
    else
    {
        *e = T[index];
        return true;
    }
}

bool Assign(int *T,Position pos,int iValue)
{
    int index = pow(2,pos.level-1)+pos.order-2;
    if(iValue!=NIL && T[(index+1)/2-1]==-1)// 
    {
        return false;
    }
    if(iValue==NIL && T[index*2+1]!=-1||T[index*2+2]!=-1)// 
    {
        return false;
    }
    T[index] = iValue;
    return true;
}

void MidTravel(int *T,int i)
{
    if(IsEmpty(T))
    {
        return;
    }else
    {
        if(T[i*2+1] != NIL)
        {
            MidTravel(T,i*2+1);
        }
        cout<