Never wasting an hour, never letting one moment go cold. 不要虚度光阴,即使是一瞬,也要用力把握。 问题描述 之前介绍过二叉树的前中后,以及DFS和BFS等遍历方式,并且每种都写了递归和非递归的解法。有的说二叉树的前中后遍历方式都属于DFS的一种,其实也可以这样理解。关于这几种遍历方式具体可以看下373,数据结构-6,树。 对于二叉树的遍历除了前面介绍的几种常见的以外,还有Morris的前中后3种遍历方式。前面讲的二叉树的几种遍历方式,如果使用的是非递归方式,我们要么需要一个栈,要么需要一个队列来维护节点之间的关系。如果使用Morris遍历就不需要了,他的实现过程其实就是把叶子节点的指针给利用起来,因为一般情况下,二叉树的叶子节点是没有子节点的,也就是说他们是指向空,这样总感觉有点浪费,Morris的实现原理其实就是把叶子节点的指针给利用了起来。Morris的后续遍历方式稍微有点复杂,这个以后再讲,这里主要看一下Morris的前序和中序遍历方式。 Morris的中序遍历 对于Morris的中序遍历可以把它看做是把二叉树拉直变成了链表,我们先来看一下他的实现步骤: 记当前节点为cur,从根节点开始遍历。 1,判断cur是否为空,如果为空就停止遍历。 2,如果cur不为空 1)如果cur没有左子节点,打印cur的值,然后让cur指向他的右子节点,即cur=cur.right 2)如果cur有左子节点,则从左子节点中找到最右边的结点pre。 1))如果pre的右子节点为空,就让pre的右子节点指向cur,即pre.right=cur,然后cur指向他的左子节点,即cur=cur.left。 2))如果pre的右子节点不为空,就让他指向空,即pre.right=null,然后输出cur节点的值,并将节点cur指向其右子节点,即cur=cur.right。 3,重复步骤2,直到节点cur为空为止。 上面叙述了一大堆,懂的一眼就能看明白,不懂的肯定会绕晕。我来一条条解释一下。 1,首先第一条,cur为空就停止遍历,这没什么好说的,为空了当然就没法遍历了。 2,cur不为空,cur的左子节点为空,打印当前节点cur的值,然后让cur=cur.right,我们来画个图看一下 2,cur不为空,他的左子节点也不为空,我们要找到他左子节点中的最右子节点pre,其实也就是中序遍历中cur的前一个节点,我们随便画两棵树来看一下,很明显就是要找到当前节点cur在中序遍历的前一个节点。 然后判断pre的右子节点是否为空,这一步可能是大家最疑惑的地方,这还需要判断吗,其实是需要的,第一次查找的时候,pre的右子节点肯定是为空的,我们让他指向cur即可,也就是pre.right=cur。如下图所示 然后再让cur指向他的左子节点,如下图所示 虽然节点1和他的左子节点没有断开,但我们可以认为他是断开了(实际上没有断开),我们可以把它想象成这样 最终我们可以把它想象成转化为一个链表(实际上并没有)。 如果pre的右子节点不为空,那么他肯定是指向cur节点的,也就表示cur节点的左子节点都已经遍历完了,只需要打印当前节点cur的值,然后让cur指向右子节点,以同样的操作开始遍历右子节点。 文字描述比较绕,我们就随便举个例子画个图来看下 搞懂了上面的原理,代码就简单多了
Morris的前序遍历 前序遍历和中序遍历的方式是一样的,只不过访问节点的时机不一样。图就不在画了,代码中有注释,可以看下
总结 上面就是Morris的中序和前序遍历,关于后续遍历有一点复杂,后面单独有一篇文章来讲。 |
|