Java教程

线索二叉树介绍

本文主要是介绍线索二叉树介绍，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

产生原因：为了解决二叉树遍历的时间空间成本问题，本质上是优化算法。遍历可以使用函数递归，但这样调用堆栈时空效率低下。

 

问题描述：对二叉树的遍历本质上是把非线性结构映射到线性结构的方式

 

线性二叉树解决问题的方案：

利用左右子树为空的结点，将空的部分填充入指针，左节点指向前驱，右结点指向后继，不调用堆栈，从而完成效率优化。

按照遍历顺序不同可以分为前序线索树，中序线索树，后序线索树。

设置一个int类型数，来告诉程序目前的指针是指向儿子结点还是前后驱指针。

 

对于加入了新指针的结点，按照新指针去遍历，对于有儿子结点的结点，没空插入新指针，按照算法找他们对应的左右最底下的儿子，因为只有这些最底下的儿子结点才发生跳转，所以只需要给他们加入指针就可以啦。

 

这篇关于线索二叉树介绍的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航