// 树的孩子兄弟链表创建.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<malloc.h>
#include<iostream.h>
#define null 0
typedef struct CSNode
{  
    char data;
    struct CSNode *firstchild, *nextsibling;
 } CSNode, *CSTree;
typedef struct QNode{
    CSTree data;
    struct QNode *next;
}QNode, *QueuePtr;

typedef struct{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

int InitQueue(LinkQueue &Q){
    Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
    if(!Q.front)
        printf("初始化失败！");
    Q.front->next=null;
    return 1;
}


int EnQueue(LinkQueue &Q,CSTree e){
    QueuePtr p;
    p=(QueuePtr)malloc(sizeof(QNode));
    if(!p)  return 0;
    p->data=e;
    p->next=null;
    Q.rear->next=p;
    Q.rear=p;
    return 1;
}

int DeQueue(LinkQueue &Q,CSTree &e)
{
    QueuePtr p;
    if(Q.front=Q.rear)
        printf("队列为空！");
    p=Q.front->next;
    e=p->data;
    Q.front->next=p->next;
    if(Q.rear==p)
        Q.rear=Q.front;
    free(p);
    return 1;
}

void GetHead(LinkQueue &Q,CSTree &e){
    QueuePtr p;
    if(Q.front=Q.rear)
        printf("队列为空！");
    p=Q.front->next;
    e=p->data;
}

void CreatTree( CSTree &T ) 
{  
    LinkQueue Q;
    InitQueue(Q);
    char ch,fa;
    CSTree p,s,r;
    T = NULL;
    for( scanf("%C,%C",&fa, &ch); ch!=' '; scanf("%C,%C",&fa, &ch)) 
      { 
        p->data = ch;    // 创建结点
        EnQueue(Q, p);       // 指针入队列
        if (fa ==' ')  T = p;     // 所建为根结点
        else 
        {
            GetHead(Q,s);  // 取队列头元素(指针值)
            while (s->data != fa ) // 查询双亲结点
            { 
                DeQueue(Q,s);  GetHead(Q,s);
            }   
           if (!(s->firstchild)) 
           { 
               s->firstchild = p; r = p; 
           }// 链接第一个孩子结点
           else 
           { 
               r->nextsibling = p;  r = p; 
           } // 链接其它孩子结点 
        }     // 非根结点的情况
      } // for
} // CreateTree


int main(int argc, char* argv[])
{
    CSTree T;
    CreatTree( T ) ;
    printf("Hello World!\n");
    return 0;
}[em18][em18][em18][em18][em18]