Java教程

2021-09-13

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

关于二叉树递归与非递归遍历的出入栈情况

重温数据结构,发现第一次学的时候并没有对二叉树非递归与递归遍历时的栈进行区分,这两种情况是不一样的 一个简单的二叉树

以上图的二叉树的前序遍历为例,如果是递归遍历,则栈的变化如下左

左边是递归的栈,右边是非递归的栈
如果是非递归遍历(最普遍的前序遍历非递归算法),则栈的变化如上图右

还有一点要特别说明,递归进栈的是方法,而方法想要出栈必须全部执行完,因此递归遍历的栈中当某次调用方法传入的实参是非叶节点那么该次方法一定在它的子节点的那次方法后面出栈
而非递归进栈的是结点就没有那么多问题了

如果本文有什么问题欢迎在评论区指出,谢谢!

这篇关于2021-09-13的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!