二叉树中序遍历的递归和非递归写法及特点

题目介绍

题目连接

本题中用到的知识点包括排序二叉树的中序遍历为一个有序序列,如果按照原始得中序遍历得话,得到得是一个递增的序列,但是本题中需要得是第大的数,所以可以采用先访问右子树的方法得到递减的序列。

下面介绍两种二叉树中序遍历的写法。一种是递归写法和非递归写法。

递归写法

递归写法比较容易理解,由于对于每个结点的访问都是按照同样的套路,先访问其右子树,再访问自己,最后访问左子树,所以使用递归的思想就很自然。实现代码如下:

但是再本题中使用递归写法好像不是那么方便,因为本题需要一个int返回值,但是使用递归写法传递这个返回值存在很多问题,所以这里采用的另一种方法是使用引用的方法,实现如下:

 

然后使用另一个函数调用该函数,返回res的值。

非递归写法

非递归写法中用到的数据结构为栈,核心思想如下:

由于栈的两个操作为入栈和出栈。入栈时,检查入栈结点是否有右节点,有的话将其右节点入栈,重复上述过程,如果没有右节点,则将其出栈。出栈操作如下:输出栈顶元素的值,将其弹出栈,并检查其是否有左子树,如果没有左子树的话,重复上述过程,有左子树的话,将其入栈,程序转到入栈操作部分。实现代码如下:

 

非递归写法在本题中就非常的适合,实现如下:

 

综上我们可以看出,当需要访问排序二叉树中某一个特殊的值的时候,可以考虑使用非递归写法,这样可以使程序更加简洁。还是需要加强一些基础算法的练习。

Leave a Reply

发表评论

电子邮件地址不会被公开。 必填项已用*标注

本站所有文章均为原创,若需转载,请注明出处©twn29004 | 陕ICP备 20000896 网站备案号

总访问量:9064400    今日访问量:164    您是今天第:164 个访问者