二叉树的层次遍历详解（C语言版） |
您所在的位置：网站首页 › c语言队列的实现以及操作图片 › 二叉树的层次遍历详解（C语言版） |
二叉树的层次遍历详解（C语言版）
|
什么是层次遍历呢？
按照我的理解，层次遍历就是从上到下，从左往右，一层层的遍历 如下图，层次遍历的结果是：ABCDEF 图片来源于https://blog.csdn.net/hansionz/article/details/81947834 算法思想先定义一个循环队列，使这个队中的数据域能存放二叉树中的元素。元素入队后，就输出队头元素的值，然后让队头元素出队，并将其的左右孩子依次入队…周而复始地进行同样的操作，直到队为空。最终，出队的顺序就是层次遍历的顺序。 听完是不是还是有点蒙？没事，我们来看核心代码帮助理解 核心代码 void Leave (BT* t) { LinkQueue Q; //定义一个循环队列 Q.head = 0; Q.rear = 0; //循环队列初始化 //队为空的条件：队头等于队尾 BT* temp; //定义一个二叉树类型的指针 PushQueue (&Q, *t); //根节点入队 while (EmptyQueue (&Q)) //当队不为空时，循环 { *temp = Q.data[Q.head+1]; //将队头元素赋值给变量*temp printf ("%c", temp->data); //输出队头元素的值 PopQueue (&Q); //队头元素出队 if (temp->lchild != NULL) //如果左孩子不为空，则左子树入队 { PushQueue (&Q, *temp->lchild); } //如果右孩子不为空，则右子树入队 if (temp->rchild != NULL) { PushQueue (&Q, *temp->rchild); } } } 测试代码以图片中的字母为二叉树的元素，则运行结果应该为ABCDEF # include # include # define MAX 100 //定义数组的长度为100 //二叉树的结点定义 typedef struct node { struct node *lchild, *rchild; char data; }BT; //循环队列的结点定义 typedef struct { int head; //head为头 int rear; //rear为尾 BT data[MAX]; //data为二叉树类型的数组,能存放二叉树中的元素 }LinkQueue; //创建一个二叉树 BT* CreateTree () { BT* t; char ch; scanf ("%c", &ch); getchar (); if (ch == '#') { t = NULL; } else { t = (BT*) malloc (sizeof (BT)); t->data = ch; printf ("请输入%c的左子树：", t->data); t->lchild = CreateTree (); printf ("请输入%c的右子树：", t->data); t->rchild = CreateTree(); } return t; } //判断队是否为空 //队不为空则返回1，队空则返回0 int EmptyQueue (LinkQueue* Q) { if (Q->head == Q->rear) { return 0; } else { return 1; } } //入队 void PushQueue (LinkQueue* Q, BT t) { Q->rear = (Q->rear+1)%MAX; Q->data[Q->rear] = t; } //出队 void PopQueue (LinkQueue* Q) { Q->head = (Q->head+1)%MAX; } //层次遍历二叉树 void Leave (BT* t) { LinkQueue Q; //定义一个循环队列 Q.head = 0; Q.rear = 0; //循环队列初始化 //队为空的条件：队头等于队尾 BT* temp; //定义一个二叉树类型的指针 PushQueue (&Q, *t); //根节点入队 while (EmptyQueue (&Q)) //当队不为空时，循环 { *temp = Q.data[Q.head+1]; //将队头元素赋值给变量*temp printf ("%c", temp->data); //输出队头元素的值 PopQueue (&Q); //队头元素出队 if (temp->lchild != NULL) //如果左孩子不为空，则左子树入队 { PushQueue (&Q, *temp->lchild); } //如果右孩子不为空，则右子树入队 if (temp->rchild != NULL) { PushQueue (&Q, *temp->rchild); } } } int main (void) { BT* t; printf ("请按先序依次输入树的结点！！！\n"); printf ("请输入根节点："); t = CreateTree (); Leave (t); return 0; } 运行结果注意：#表示空的意思 |
【本文地址】