二叉树层次遍历（用队列实现）

 核心思想：首先根节点入队，若队列非空则做循环，若根节点有左右孩子，则左右孩子入队，第一个节点出队，循环直到队列为空。

#ifndef _BTREE_H_
#define _BTREE_H_typedef char BTDataType;typedef struct BinaryTreeNode{BTDataType data;struct BinaryTreeNode* lchild;struct BinaryTreeNode* rchild;
}BTNode;void BinaryTreeDestory(BTNode* root);void BinaryTreeLevelOrder(BTNode* root);#endif/*_BTREE_H_*/

#ifndef _QUEUE_H_
#define _QUEUE_H_
#include "BTree.h"typedef BTNode * QuDataType;typedef struct QueueNode
{QuDataType _data;struct QueueNode* _next;
}QueueNode;typedef struct Queue {QueueNode * _head;QueueNode * _rear;
}Queue;void QueueInit(Queue* plist);
void QueueDestory(Queue* plist);void QueuePop(Queue* plist);
void QueuePush(Queue* plist, QuDataType x);
QuDataType QueueTop(Queue* plist);int QueueIsEmpty(Queue* plist);#endif //_QUEUE_H_

#include "queue.h"#include 
#include 
#include void QueueInit(Queue* plist)
{assert(plist);plist->_head = NULL;plist->_rear = NULL;
}void QueueDestory(Queue* plist)
{QueueNode * tmp;while (plist->_head){tmp = plist->_head;plist->_head = plist->_head->_next;free(tmp);}
}void QueuePop(Queue* plist)
{assert(plist);QueueNode * tmp;if (plist->_head){tmp = plist->_head;plist->_head = plist->_head->_next;free(tmp);}
}void QueuePush(Queue* plist, QuDataType x)
{QueueNode * cur = (QueueNode *)malloc(sizeof(QueueNode));cur->_data = x;cur->_next = NULL;if (QueueIsEmpty(plist)){plist->_head = plist->_rear = cur;return;}plist->_rear->_next = cur;//尾部下一个是插入的curplist->_rear = cur;//cur是最后一个元素
}int QueueIsEmpty(Queue* plist)
{return plist->_head == NULL;
}QuDataType QueueTop(Queue* plist)
{if (QueueIsEmpty(plist)){return (QuDataType)0;}return plist->_head->_data;
}

#include"BTree.h"
#include"queue.h"#include
#includevoid BinaryTreeLevelOrder(BTNode* root)//用队列层次遍历
{Queue qu;BTNode* cur;QueueInit(&qu);//有初始化就要销毁QueuePush(&qu, root);//根节点入队while (!QueueIsEmpty(&qu)){cur = QueueTop(&qu);//把队首元素给curputchar(cur->data);if (cur->lchild){QueuePush(&qu, cur->lchild);//有左孩子入队}if (cur->rchild){QueuePush(&qu, cur->rchild);//有右孩子入队}QueuePop(&qu);}QueueDestory(&qu);
}

#include "BTree.h"
#include "queue.h"int main()
{BTNode * root = BinaryTreeCreate("ABD#GI##J###CE#HK###F##");BinaryTreeLevelOrder(root);putchar('\n');BinaryTreeDestory(root);system("pause");return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！