数据结构之链式结构二叉树的实现（进阶版）

本篇文章重要讲解链式二叉树的层序遍历以及判断是否为一棵完全二叉树
二者将会用到之前学过的队列知识，是将队列和二叉树的整合
一、如何将之前已经写好的文件加入当前的编译界面

如图所示，打开我们必要加入文件所在的文件夹，找到我们要加入的文件，按ctrl+c将其复制下来，在本文中，我们必要将queue.h和queue.c复制下来.

然后在找到我们当前文件所在的文件夹，将其粘贴进去，如图所示

 
之后在vs的办理方案栏中找到 头文件，右键，添加，现有项，进入这个界面

长按ctrl并且鼠标左键选择queue.h和queue.c,之后点添加，之后这个栏是这样的

此时在鼠标左键按住queue.c文件，拖到源文件处即可

好了，条件条件已经具备了，下面准备写代码了
二、层序遍历及判断完全二叉树

这里由于我们是要将二叉树的各个结点入队列，以是前面的typedef应该改一下

queue文件根本上不必要改动！
接下来我们将实现 层序遍历及判断完全二叉树，这里仅展示与其相干的代码，其余的代码前往上一篇文章检察！
这是tree.h文件

1. // 层序遍历
2. void LevelOrder(btnode* root);
3. // 判断⼆叉树是否是完全⼆叉树
4. bool BinaryTreeComplete(btnode* root);

复制代码

这是tree.c文件

1. #include"queue.h"
2. //层序遍历
3. void LevelOrder(btnode* root)
4. {
5.         queue q;
6.         queueinit(&q);
7.         queuepush(&q, root);
8.         while (!queueempty(&q))
9.         {
10.                 //取队头,出队头
11.                 btnode* top = queuefront(&q);
12.                 queuepop(&q);
13.                 printf("%c", top->data);        //注意不要写成%d!!!!!
14.                 //将队头的左右孩子入队列（不为空）
15.                 if (top->left)
16.                 {
17.                         queuepush(&q, top->left);
18.                 }
19.                 if (top->right)
20.                 {
21.                         queuepush(&q, top->right);
22.                 }
23.         }
24.         queuedestroy(&q);
25. }
26. //判断二叉树是否为完全二叉树
27. bool BinaryTreeComplete(btnode* root)
28. {
29.         queue q;
30.         queueinit(&q);
31.         queuepush(&q,root);
32.         while (!queueempty(&q))
33.         {
34.                 //取队头，出队头
35.                 btnode* top = queuefront(&q);
36.                 queuepop(&q);
37.                 if (top == NULL)
38.                 {
39.                         //只要取到空结点就跳出while循环
40.                         break;
41.                 }
42.                 //把不为空的头结点的左右孩子入队列
43.                 queuepush(&q, top->left);
44.                 queuepush(&q, top->right);
45.         }
46.         //此时队列可能为空，也可能不为空，故继续取，若取到不为空的结点，则证明不是完全二叉树
47.         while (!queueempty(&q))
48.         {
49.                 btnode* top = queuefront(&q);
50.                 queuepop(&q);
51.                 if (top != NULL)
52.                 {
53.                         queuedestroy(&q);
54.                         return false;
55.                 }
56.         }
57.         queuedestroy(&q);
58.         return true;
59. }

复制代码

这是test.c文件

1.         //层序遍历
2.         LevelOrder(root);
3.         printf("\n");
4.         //判断是否为完全二叉树
5.         if (BinaryTreeComplete(root))
6.         {
7.                 printf("It is a complete binary tree!");
8.         }
9.         else
10.         {
11.                 printf("It is not a complete binary tree!");
12.         }
13.         BinaryTreeDestory(&root);

复制代码

运行结果附上：

 


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。