当前位置: 首页 > ops >正文

【数据结构】使用队列解决二叉树问题

1.层序遍历

A先进队列,迭代-》队列不为空,拿出队头的数据然后将队头的左右节点放入队列,不断拿出放入,又队列满足先进先出的特性,无论这棵树多大都能实现层序遍历;

我们这里需要用到队列,可以在我的这篇文章中获取:

【数据结构】队列-CSDN博客

修改一下队列的数据类型

//层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root == NULL)return;QueuePush(&q, root);  // 根节点先入队while (!QueueEmpty(&q))  // 队列不为空时循环{BTNode* front = QueueFront(&q);  // 获取队头节点QueuePop(&q);  // 队头节点出队printf("%c ", front->_data);  // 访问节点(打印数据)// 左右子节点入队(如果存在)if (front->_left)QueuePush(&q, front->_left);if (front->_right)QueuePush(&q, front->_right);}QueueDestroy(&q);printf("\n");
}

假设我们有如下二叉树:

        A/ \B   C/ \   \D   E   F

执行流程如下:

  1. 初始化队列,将 A 入队 → 队列:[A]

  2. 队列非空,取出 A 并打印,将 B、C 入队 → 队列:[B, C],输出:A

  3. 队列非空,取出 B 并打印,将 D、E 入队 → 队列:[C, D, E],输出:A B

  4. 队列非空,取出 C 并打印,将 F 入队 → 队列:[D, E, F],输出:A B C

  5. 队列非空,取出 D 并打印,无子女入队 → 队列:[E, F],输出:A B C D

  6. 队列非空,取出 E 并打印,无子女入队 → 队列:[F],输出:A B C D E

  7. 队列非空,取出 F 并打印,无子女入队 → 队列:[],输出:A B C D E F

  8. 队列为空,循环结束,销毁队列

最终输结果为:A B C D E F ,正好是按层序访问的结果。

2.判断二叉树是否为完全二叉树

遇到NULL就break跳出循环,然后接着判断剩下队列的数据,如果都是空,说明这个是完全二叉树;

//判断二叉树是否为满二叉树
//是返回1,不是返回0
int BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root == NULL)return;QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL){break;}QueuePush(&q, front->_left);QueuePush(&q, front->_right);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front){QueueDestroy(&q);return 0;}}QueueDestroy(&q);return 1;
}

相关文章:

【数据结构】树的概念及结构-CSDN博客

【数据结构】二叉树概念及结构 -CSDN博客

【数据结构】堆-“此堆非比堆”-CSDN博客

http://www.xdnf.cn/news/18161.html

相关文章:

  • 4.pod生命周期和健康检测以及使用kubectl管理Kubernetes容器平台
  • B站 韩顺平 笔记 (Day 23)
  • 力扣(电话号码的字母组合)
  • 理解JavaScript中的函数赋值和调用
  • 0.开篇简介
  • 添加右键菜单项以管理员权限打开 CMD
  • CMake进阶: CMake Modules---简化CMake配置的利器
  • 决策树(2)
  • 火山引擎,燃起了Agent的星星之火
  • Python数据分析:DataFrame,reindex,重建索引。有时候整型变浮点型,有时候又不变?
  • Unity进阶--C#补充知识点--【C#各版本的新功能新语法】C#1~4与C#5
  • 基于多级缓存架构的Redis集群与Caffeine本地缓存实战经验分享
  • BEV:隐式相机视角转换-----BEVFormer
  • JVM 面试精选 20 题(续)
  • 面试经验分享-某电影厂
  • 黎阳之光:以数字之力,筑牢流域防洪“智慧防线”
  • 图像采集卡与工业相机:机器视觉“双剑合璧”的效能解析
  • 【ASP.NET Core】ASP.NET Core中间件解析
  • 如何安全删除GitHub中的敏感文件?git-filter-repo操作全解析
  • PowerBI VS FineBI VS QuickBI实现帕累托分析
  • [WiFi]RealTek RF MP Tool操作说明(RTL8192ES)
  • 编排之神--Kubernetes中的认证授权详解
  • PyTorch数据加载利器:torch.utils.data 详解与实践
  • RNN深层困境:残差无效,Transformer为何能深层?
  • 【RustFS干货】RustFS的智能路由算法与其他分布式存储系统(如Ceph)的路由方案相比有哪些独特优势?
  • MySQL深分页性能优化实战:大数据量情况下如何进行优化
  • 阿里云参数配置化
  • C++入门自学Day14-- deque类型使用和介绍(初识)
  • 私有化部署全攻略:开源模型本地化改造的性能与安全评测
  • IPD流程执行检查表