数据结构 - 二叉树的广度优先遍历算法（C++）

超、凢脫俗 2022-04-22 05:08 123阅读 0赞

**分享一下我老师大神的人工智能教程！零基础，通俗易懂！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangjunshow]**

**也欢迎大家转载本篇文章。分享知识，造福人民，实现我们中华民族伟大复兴！**

#include <iostream>#define _OK 1#define _ERROR 0using namespace std;// Define node element type in binary tree.typedef char Element;// Binary tree.typedef struct BTNode{
          Element data; BTNode *lChild,*rChild; // Define left,right subtree.} BTNode, *BTree;// Define node element type in queue. (The node element type in queue is the pointer to binary tree node)typedef BTNode *QElementType;typedef int status;// --------------------------------------------------------------------// We need use queue to perform level traverse. So, define queue first.typedef struct QNode{
          QElementType data; QNode *next;} QNode, *QueuePtr;// Definition of queue.typedef struct{
          QueuePtr front; QueuePtr rear;} LinkQueue;status InitQueue(LinkQueue &Q){ Q.front = NULL; Q.rear = NULL; return _OK;}bool IsEmpty(LinkQueue Q){ return Q.front == NULL;}status EnQueue(LinkQueue &Q, QElementType e){ // Construct queue node. QNode *ptrNode = (QNode*) malloc(sizeof(QNode)); if(!ptrNode) {  return _ERROR; } ptrNode->data=e; ptrNode->next=NULL; if(IsEmpty(Q)) {  Q.front=Q.rear=ptrNode;  return _OK; } Q.rear->next=ptrNode; Q.rear = ptrNode; return _OK;}status DeQueue(LinkQueue &Q, QElementType &e){ if(IsEmpty(Q)) {  return _ERROR; } QNode *tempPtr = Q.front; e = tempPtr->data; Q.front = tempPtr->next; free(tempPtr); return _OK;}// ------------------------------------------int CreateBTree(BTree &T){ char ch; cout << "Please input a character:" << endl; cin >> ch; if(ch=='#') {  T = NULL; } else {  // Allocate memory for new node.  if(!(T = (BTNode*)malloc(sizeof(BTNode))))  {   return 0; // Allocation fails.  }  T->data = ch;  // Create left subtree.  CreateBTree(T->lChild);  // Create right subtree.  CreateBTree(T->rChild); } return 1;}void VisitBTNode(BTNode *BT){ cout << BT->data << endl;}void VisitQNode(QNode *Q){ VisitBTNode(Q->data);}void LevelTraverse(BTree T){ QElementType e; LinkQueue Q; InitQueue(Q); EnQueue(Q,T); while (!IsEmpty(Q)) {  VisitQNode(Q.front);  if(Q.front->data->lChild!=NULL)  {   EnQueue(Q,Q.front->data->lChild);  }  if(Q.front->data->rChild!=NULL)  {   EnQueue(Q,Q.front->data->rChild);  }  DeQueue(Q,e); }}// ------------------------------------------void main(){ BTree T; CreateBTree(T); LevelTraverse(T);}// Output:/*Please input a character:6Please input a character:gPlease input a character:#Please input a character:7Please input a character:fPlease input a character:gPlease input a character:8Please input a character:9Please input a character:#Please input a character:$Please input a character:#Please input a character:#Please input a character:#Please input a character:#Please input a character:cPlease input a character:#Please input a character:#Please input a character:#Please input a character:#6g7fgc89$*/

#### 给我老师的人工智能教程打call！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangjunshow] ####

![这里写图片描述][SouthEast]

[http_blog.csdn.net_jiangjunshow]: https://blog.csdn.net/jiangjunshow/article/details/77338485
[SouthEast]: /images/20220422/211f905576d347188471f60589499061.png