#include
#include
typedef struct csnode
{
int data;
int in;
struct csnode *lchild;
struct csnode *nextsibling;
}CSNode;
CSNode *t,*q;
int preoder()//通過先序周遊的方式輸出該樹一條從根到葉子的路徑
{ //順便求樹的深度
CSNode *stact[1001],*p;
int i,high=-1;
int top=-1;
p=t;
while(p||top!=-1)
{
while(p)
{
top++;
stact[top]=p;
p=p->lchild;
}
if((stact[top]->in)==0)
{
for(i=0;i<=top;i++)
printf("%d ",stact[i]->data);
if(top>high)
high=top;
printf("\n");
}
if(top<0)
break;
else
{
p=stact[top];
top--;
p=p->nextsibling;
}
}
return high;
}
// 建立“孩子-兄弟連結清單”方式存儲的樹
int CreatTree( int n)
{
int k,i,j,h; // 父節點編号，子節點編号
t = NULL;
CSNode *queue[1001],*p;
int head,tail;
head=0;
tail=-1;
for(k=1; k<=n;k++)
{
scanf("%d%d",&i,&j);
p=(CSNode*)malloc(sizeof(CSNode)); // 建立結點
p->lchild=NULL;
p->nextsibling=NULL;
p->data=j;
(p->in)=0;
tail++;
queue[tail]=p; //最終 tail+1 為樹的總結點的數目
if(i==-1)// 所建為根結點
t=p;//
else // 非根結點的情況
{
for(h=head;h<=tail;h++) //當然這裡可以添加條件
//防止 相同的節點的再次出現
if(queue[h]->data==i)
{
queue[h]->in++;
break;
}
q=queue[h];
if (!(q->lchild) ) // 連結第一個孩子結點
q->lchild = p;
// r = p;
else // 連結其它孩子結點
{
q=q->lchild;
while(q->nextsibling)
q=q->nextsibling;
q->nextsibling = p;
}
}
} // for
return tail;
} // CreateTree
int main()
{ //freopen("1.txt","r",stdin);
int high, n;;
scanf("%d",&n);
printf("樹一條從根到葉子的路徑:\n");
n=CreatTree(n);
high= preoder();
printf("樹的深度：%d 樹的節點數：%d\n",high+1,n+1);
return 0;
}
/*
n=7
i=fa j -1 1 1 2 1 3 1 4 3 5 3 6 5 7