代码:
/* 从上到下遍历二叉树 by Rowandjj 2014/8/1 */ #include<iostream> using namespace std; typedef struct _BNODE_ { int data; struct _BNODE_ *lChild; struct _BNODE_ *rChild; }BNode,*pTree,*pNode; typedef struct _QUEUENODE_ { pNode data; struct _QUEUENODE_ *next; }QNode,*pQNode; typedef struct _QUEUE_ { pQNode pHead; pQNode pTail; }Queue,*pQueue; void InitQueue(pQueue pQ) { pQ->pHead = pQ->pTail = (pQNode)malloc(sizeof(QNode)); if(pQ->pHead == NULL) { exit(-1); } pQ->pHead->next = NULL; } void Enqueue(pQueue pQ,pNode data) { if(pQ == NULL || data == NULL) { return; } pQNode pNew = (pQNode)malloc(sizeof(QNode)); if(!pNew) { exit(-1); } pNew->data = data; pNew->next = NULL; pQ->pTail->next = pNew; pQ->pTail = pNew; } pNode Dequeue(pQueue pQ) { if(pQ == NULL) { return NULL; } pQNode pDel = pQ->pHead->next; if(pDel == NULL) { return NULL; } pNode data = pDel->data; if(pDel == pQ->pTail) { pQ->pTail = pQ->pHead; } pQ->pHead->next = pDel->next; free(pDel); return data; } void Destroy(pQueue pQ) { if(pQ == NULL) { return; } pNode pTemp; while((pTemp = Dequeue(pQ)) != NULL) { free(pTemp); } free(pQ->pHead); } //层次遍历 void LevelTraverse(pTree pT) { if(pT == NULL) { return; } Queue q; InitQueue(&q); Enqueue(&q,pT); pNode pTemp; while((pTemp = Dequeue(&q)) != NULL) { cout<<pTemp->data<<" "; if(pTemp->lChild) { Enqueue(&q,pTemp->lChild); } if(pTemp->rChild) { Enqueue(&q,pTemp->rChild); } } Destroy(&q); } void Create(pTree *pT) { int data; cin>>data; if(data != -1) { *pT = (pTree)malloc(sizeof(BNode)); if(*pT == NULL) { exit(-1); } (*pT)->lChild = NULL; (*pT)->rChild = NULL; (*pT)->data = data; Create(&(*pT)->lChild); Create(&(*pT)->rChild); } } int main() { pTree pT= NULL; Create(&pT); LevelTraverse(pT); return 0; }
原文:http://blog.csdn.net/chdjj/article/details/38341289