/***************************************************
二叉树的线性存储
by Rowandjj
2014/5/23
***************************************************/
#include<iostream>
#include<MATH.H>
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=http://www.mamicode.com/=NIL && T[index*2+1]!=-1||T[index*2+2]!=-1)//子节点不为空但是当前节点为空>