데이터 구조 트 리 계층 은 이 진 트 리 C 언어 판 을 옮 겨 다 닌 다.

2642 단어 데이터 구조
//               
#include 
#include 
typedef struct NNode
{
	char data;
	struct NNode *LChild;
	struct NNode *RChild;
} BiTNode,*BiTree;   //            

typedef BiTree QueueElementType;
typedef struct Node
{
    QueueElementType data;
    struct Node  *next;
} LinkQueueNode;  //      
typedef struct
{
    LinkQueueNode *front; //       
    LinkQueueNode *rear;  //       
} LinkQueue;  //    

int InitQueue(LinkQueue *Q )  //     
{
    Q->front=(LinkQueueNode * )malloc(sizeof(LinkQueueNode));
    if(Q->front != NULL)
    {
        Q->rear=Q->front;
        Q->front->next=NULL;
        return 1;
    }
    else return 0;//  
}

int EnterQueue(LinkQueue *Q,QueueElementType x) //  x        
{
    LinkQueueNode * newnode;
    newnode=(LinkQueueNode *) malloc(sizeof(LinkQueueNode));
    if(newnode != NULL)
    {

        newnode->data=x;
        newnode->next=NULL;
        Q->rear->next=newnode;
        Q->rear=newnode;
        return 1;
    }
    else return 0;
}

int DeleteQueue(LinkQueue *Q,QueueElementType *x ) //              
{
    LinkQueueNode *p;
    if(Q->front==Q->rear)
        return 0;
    p=Q->front->next;
    Q->front->next=p->next;
    if(Q->rear==p )
         Q->rear=Q->front;  //      p ,              
    *x=p->data;
    free(p);
    return 1;
}

int IsEmpty(LinkQueue *Q) //      1       0
{
    if(Q->front==Q->rear ) return 1;
    else return 0;
}


void CreateBiTree(BiTree *bt)  //          
{
	char ch;
	ch=getchar();
	if(ch=='.') (*bt)=NULL;
	else
	{
		*bt=(BiTree)malloc(sizeof(BiTNode));
		(*bt)->data=ch;
		CreateBiTree(&((*bt)->LChild));
		CreateBiTree(&((*bt)->RChild));
	}
}

void PreOrder(BiTree root) //       
{
	if(root!=NULL)
	{
		printf("%c",root->data);
		PreOrder(root->LChild);
		PreOrder(root->RChild);
	}

}

int LayerOrder(BiTree bt)   //              1     0
{
    LinkQueue Q;
    BiTree p;
    InitQueue(&Q);
    if(bt==NULL) return 0;
    EnterQueue(&Q,bt);
    while(!IsEmpty(&Q))
    {
        if(DeleteQueue(&Q,&p));
            printf("%c ",p->data);
        if(p->LChild) EnterQueue(&Q,p->LChild);
        if(p->RChild) EnterQueue(&Q,p->RChild);
    }
    return 1;
}

int main()
{
    BiTree bt;
	printf("                       AB..CD...   
") ; CreateBiTree(&bt); PreOrder(bt); printf("
"); if(LayerOrder(bt)) printf("
"); else printf("
"); return 0; }

좋은 웹페이지 즐겨찾기