> 文档中心 > 二叉树的讲解《六》(二叉树的层序遍历)

二叉树的讲解《六》(二叉树的层序遍历)


  个人主页:欢迎大家光临——>沙漠下的胡杨

  各位大帅哥,大漂亮

 如果觉得文章对自己有帮助

 可以一键三连支持博主

 你的每一分关心都是我坚持的动力

 

 ☄: 本期重点:二叉树的层序遍历

  希望大家每天都心情愉悦的学习工作。 


什么是层序遍历:

层序遍历的实现思路:

代码实现:

判断是否为完全二叉树:

遍历创建二叉树:


今天我们重点说一下二叉树的层序遍历。

什么是层序遍历:

就是一层一层的遍历二叉树,如图:

 我们层序遍历的结果是:ABCDEFGH。一层一层的,这个本质是广度优先遍历。

层序遍历的实现思路:

一般来说我们会使用队列来辅助实现层序遍历。

 这样重复,一直到所有的节点没有孩子为止,我们也就层序遍历完所有节点了。

代码实现:

我们使用C语言来实现,由于C语言没有库,所以我们要先手写一个队列,进行操作。

在使用队列时我们有一个注意的点:

就是把队列中的元素类型改为二叉树的节点,这时我们的队列表示没有二叉树的节点的声明,就会报错,我们要先在队列前放置二叉树的声明,才可以使用。如下图所示:

代码实现:

void LevelOrder(BTNode *root){Queue q;//创建队列QueueInit(&q);//初始化队列if (root)//如果根节点不为空{QueuePush(&q, root);//根节点放入队列}while (!QueueEmpty(&q))//如果队列不为空{BTNode* front = QueueFront(&q);//保存节点值printf("%c ", front->data);//打印QueuePop(&q);//出队列if (front->left)//如果不为空,左节点放入队列{QueuePush(&q, front->left);}if (front->right)//如果不为空,左节点放入队列{QueuePush(&q, front->right);}}printf("\n");QueueDestroy(&q);//销毁队列}

我们在层序遍历时,我们把数据出队列了,只是把队列中的数据删除了,但是我们另一个二叉树的结构上的值没有销毁,所以我们依旧可以使用二叉树的值来访问左右子树。

判断是否为完全二叉树:

首先我们判断一棵树是否为完全二叉树的话,我们可以采用层序遍历的思路:

1.我们直接向队列中入数据,为NULL停止。

2.我们判断队列中是否都为空,如果还有非空的数据,那么就不是完全二叉树。

 代码如下:

int TreeComplete(BTNode* root){Queue q;QueueInit(&q);if (root){QueuePush(&q, root);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front)//不为空,一直进数据{QueuePush(&q, front->left);QueuePush(&q, front->right);}else//为空就停止。{break;}}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front)//如果非空{QueueDestroy(&q);//销毁队列return false;//返回假}}QueueDestroy(&q);return true;//返回之前销毁队列。}

我们要注意的一点是:

任何时候返回,都要销毁队列,否则会导致内存泄漏。

遍历创建二叉树:

我们学了这么久二叉树了,好像还没有学创建吧?下面用一道例题来学习创建二叉树

牛客:二叉树的遍历

要求我们首先先序遍历创建树,然后使用中序遍历打印。

思路:

1.我们首先就用数组接收传过来的值。

2.创建树的结构体和创建树的节点的函数。

3.我们编写创建树的函数,要注意的是我们要通过数组的下标访问,并且每一次的下标值会发生变化,所以我们应该传入数组下标的地址,我们以后修改都可以直接修改下标值了。

4.我们进行中序的打印即可。

代码如下:

#include #include #include typedef char BTDataType;typedef struct BinaryTreeNode//创建树{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;}BTNode;BTNode* BuyNode(BTDataType x)//创建树的节点{BTNode* node = (BTNode *)malloc(sizeof(BTNode));assert(node);node->data = x;node->left = node->right = NULL;return node;}BTNode* CreatBinaryTree(char* arr,int* pi)//传入数组和下标的地址{    if(arr[(*pi)] == '#')    { (*pi)++; return NULL;    } BTNode* root = BuyNode(arr[(*pi)++]);//先序    root->left = CreatBinaryTree(arr,pi);    root->right = CreatBinaryTree(arr,pi); return root;}void InOrder(BTNode* root)//中序打印{    if(root == NULL)    { return ;    }    InOrder(root->left);    printf("%c ",root->data);    InOrder(root->right);}int main (){    char arr[101];    scanf("%s",arr);//接收值    int i = 0;    BTNode* root = CreatBinaryTree(arr,&i);    InOrder(root);    }

二叉树的学习就告一段落啦,明天我们将学习排序。