Java教程

线索二叉树介绍

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

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

 

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

 

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

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

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

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

 

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

 

这篇关于线索二叉树介绍的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!