ツリーのリニアストレージ
2732 ワード
/***************************************************
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<