从上到下遍历二叉树

从上到下遍历二叉树

思路：

即二叉树的层序遍历。可以使用一个辅助队列，首先将二叉树的根节点入队，然后打印根结点的值，接着判断根结点

是否有左右孩子，如果有，将左右孩子入队。如此循环直到队列为空。

二叉树的常见问题及其解决程序

【递归】二叉树的先序建立及遍历

在JAVA中实现的二叉树结构

【非递归】二叉树的建立及遍历

二叉树递归实现与二重指针

二叉树先序中序非递归算法

轻松搞定面试中的二叉树题目

代码：

/*
从上到下遍历二叉树
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;
}

测试：

本文永久更新链接地址：