(32)王道数据结构-二叉树的层次遍历

基本思想

①初始化一个辅助队列
②根节点入队
③若队列非空，则队头结点出队，访问该节点，并将其左、右孩子插入队尾(存在的话)
④重复③直到队列为空

实现代码

#include <stdio.h>
#include <stdlib.h>
//二叉树 
typedef struct BiTNode {
	BiTNode* lchild, * rchild;
	char data;
}BiTNode, * BiTree;
//队列
typedef struct LinkNode {
	BiTNode* data;
	LinkNode* next;
}LinkNode;

typedef struct {
	LinkNode* front, * rear;
}LinkQueue;

//初始化 
int InitQueue(LinkQueue& L) {
	L.front = L.rear = (LinkNode*)malloc(sizeof(LinkNode));
	if (L.front == NULL) {
	    return 0;
	}
	L.front->next = NULL;
}

//出队列 
void PushNode(LinkQueue& L, BiTree T) {
	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = T;
	s->next = NULL;
	L.rear->next = s;
	L.rear = s;
}

//入队列
void PopNode(LinkQueue& L, BiTree& T1) {
	T1 = L.front->next->data;
	printf("%c ", L.front->next->data->data);
	L.front = L.front->next;
}

void LevelTraversal(BiTree& T) {
	BiTree T1;
	LinkQueue L;
	InitQueue(L);
	PushNode(L, T);
	while (L.front != L.rear) {
		PopNode(L, T1);
		if (T1->lchild != NULL) {
            PushNode(L, T1->lchild);
        }
		if (T1->rchild != NULL) {
            PushNode(L, T1->rchild);
        }
	}
}

//为树的当前节点添加左子节点
bool addLeftChild(BiTree root, char leftData) {
  //分配新节点
  BiTree leftNode = (BiTree)malloc(sizeof(BiTNode));
  //为新节点挂载数据
  leftNode->data = leftData;
  //新节点暂时无子节点
  leftNode->lchild = NULL;
  leftNode->rchild = NULL;
  //将新节点挂到当前节点下
  root->lchild = leftNode;
  return true;
}

//为树的当前节点添加右子节点
bool addRightChild(BiTree root, char rightData) {
  //分配新节点
  BiTree rightNode = (BiTree)malloc(sizeof(BiTNode));
  //为新节点挂载数据
  rightNode->data = rightData;
  
  //新节点暂时无子节点
  rightNode->lchild = NULL;
  rightNode->rchild = NULL;
  
  //将新节点挂到当前节点下
  root->rchild = rightNode;
  return true;
}

int main() {
	//设定根节点
    BiTree root;
    root = (BiTree)malloc(sizeof(BiTNode));
  
    //根节点A
    root->data = 'A';
    addLeftChild(root, 'B');
    addRightChild(root, 'C');
  
    //为B节点增加子节点
    addLeftChild(root->lchild, 'D');
    addRightChild(root->lchild, 'E');
  
    //为C节点增加子节点
    addLeftChild(root->rchild, 'F');
    addRightChild(root->rchild, 'G');

	LevelTraversal(root);
}