线索二叉树介绍
2022/8/6 23:25:14
本文主要是介绍线索二叉树介绍,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
产生原因:为了解决二叉树遍历的时间空间成本问题,本质上是优化算法。遍历可以使用函数递归,但这样调用堆栈时空效率低下。
问题描述:对二叉树的遍历本质上是把非线性结构映射到线性结构的方式
线性二叉树解决问题的方案:
利用左右子树为空的结点,将空的部分填充入指针,左节点指向前驱,右结点指向后继,不调用堆栈,从而完成效率优化。
按照遍历顺序不同可以分为前序线索树,中序线索树,后序线索树。
设置一个int类型数,来告诉程序目前的指针是指向儿子结点还是前后驱指针。
对于加入了新指针的结点,按照新指针去遍历,对于有儿子结点的结点,没空插入新指针,按照算法找他们对应的左右最底下的儿子,因为只有这些最底下的儿子结点才发生跳转,所以只需要给他们加入指针就可以啦。
这篇关于线索二叉树介绍的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署
- 2024-04-14RAG应用开发实战02-相似性检索的关键 - Embedding
- 2024-04-14出海软件草根逆袭打法是什么?
- 2024-04-13鸿蒙原生应用再新丁!企查查 碧蓝航线 入局鸿蒙
- 2024-04-11RAG应用开发实战(01)-RAG应用框架和解析器
- 2024-04-10DevOps已死?2024年的DevOps将如何发展
- 2024-04-10码农必看:常见源代码混淆技术详解
- 2024-04-07以一当十丨TiDB 在东吴证券秀财 APP 的应用实践
- 2024-04-07月活超 1.1 亿,用户超 4 亿,你也在用的「知乎」是如何在超大规模 TiDB 集群上玩转多云多活的?来听听知乎代晓磊的答案!