二叉树的层序遍历

全部代码
  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <assert.h>
  4 
  5 typedef struct node
  6 {
  7     int nValue;
  8     struct node *pLeft;
  9     struct node *pRight;
 10 }BiTree;
 11 
 12 typedef struct node2
 13 {
 14     BiTree *nValue;
 15     struct node2 *pNext;
 16 }MyQueue;
 17 
 18 typedef struct node3
 19 {
 20     int nCount;
 21     MyQueue *pHead;
 22     MyQueue *pTail;
 23 }Queue;
 24 
 25 void q_Init(Queue **ppQueue)
 26 {
 27     assert(ppQueue != NULL);
 28 
 29     *ppQueue = (Queue *)malloc(sizeof(Queue));
 30     if(NULL == *ppQueue)
 31     {
 32         printf("队列空间分配失败！
");
 33         exit(-1);
 34     }
 35     (*ppQueue)->nCount = 0;
 36     (*ppQueue)->pHead = NULL;
 37     (*ppQueue)->pTail = NULL;
 38 }
 39 
 40 void q_Push(Queue *pQueue, BiTree *nNum)
 41 {
 42     MyQueue *pTemp = NULL;
 43 
 44     assert(pQueue!=NULL);
 45 
 46     //临时节点开辟空间
 47     pTemp = (MyQueue *)malloc(sizeof(MyQueue));
 48     if(NULL == pTemp)
 49     {
 50         printf("临时节点空间分配失败！
");
 51         exit(-1);
 52     }
 53     pTemp->nValue = nNum;
 54     pTemp->pNext = NULL;
 55 
 56     //尾添加
 57     if(NULL == pQueue->pHead)
 58     {
 59         pQueue->pHead = pTemp;
 60     }
 61     else
 62     {
 63         pQueue->pTail->pNext = pTemp;
 64     }
 65     pQueue->pTail = pTemp;
 66 
 67     //更新队列中的元素
 68     ++pQueue->nCount;
 69 }
 70 
 71 //递归创建二叉树
 72 void RecCreateBiTree(BiTree **ppRoot)
 73 {
 74     int nNum;
 75 
 76     assert(ppRoot!=NULL);
 77 
 78     //输入节点的值
 79     scanf("%d", &nNum);
 80 
 81     //检测是否是结束标志
 82     if(0 == nNum)
 83     {
 84         return;
 85     }
 86 
 87     *ppRoot = (BiTree *)malloc(sizeof(BiTree));
 88     if(NULL == *ppRoot)
 89     {
 90         printf("*ppRoot空间分配失败！");
 91         exit(-1);
 92     }
 93     (*ppRoot)->nValue = nNum;
 94     (*ppRoot)->pLeft = NULL;
 95     (*ppRoot)->pRight = NULL;
 96 
 97     //处理当前节点的左和右
 98     RecCreateBiTree(&(*ppRoot)->pLeft);
 99     RecCreateBiTree(&(*ppRoot)->pRight);
100 }
101 
102 BiTree *q_Pop(Queue *pQueue)
103 {
104     BiTree *nNum = NULL;
105     MyQueue *pDel = NULL;
106 
107     assert(pQueue!=NULL && pQueue->pHead!=NULL);
108 
109     //头删除
110     pDel = pQueue->pHead;
111     nNum = pDel->nValue;
112     //头下移
113     pQueue->pHead = pQueue->pHead->pNext;
114 
115     //释放空间
116     free(pDel);
117     pDel = NULL;
118 
119     //更新队列中的元素
120     --pQueue->nCount;
121 
122     //尾置空
123     if(0 == pQueue->nCount)
124     {
125         pQueue->pTail = NULL;
126     }
127 
128     return nNum;
129 }
130 
131 int q_IsEmpty(Queue *pQueue)
132 {
133     assert(pQueue!=NULL);
134 
135     return 0==pQueue->nCount ? 1:0;
136 }
137 
138 //层序遍历
139 void LevelTraversal(BiTree *pRoot)
140 {
141     Queue *pQueue = NULL;
142     BiTree *pTemp = NULL;
143 
144     assert(pRoot!=NULL);
145 
146     //队列的初始化
147     q_Init(&pQueue);
148 
149     //入队
150     q_Push(pQueue, pRoot);
151 
152     //队列空，遍历结束
153     while(!q_IsEmpty(pQueue))
154     {
155         //出队打印
156         pTemp = q_Pop(pQueue);
157         printf("%d ", pTemp->nValue);
158 
159         if(pTemp->pLeft != NULL)
160         {
161             q_Push(pQueue, pTemp->pLeft);
162         }
163         if(pTemp->pRight != NULL)
164         {
165             q_Push(pQueue, pTemp->pRight);
166         }
167     }
168 }
169 
170 int main(void)
171 {
172     BiTree *pRoot = NULL;
173     RecCreateBiTree(&pRoot);
174     LevelTraversal(pRoot);
175 
176     return 0;
177 }