Morris中序遍历二叉树小结

关键词前驱结点predecessor线索原理中序遍历遍历二叉树有递归和迭代两种写法这两种写法都需要O(n)的空间复杂度都需要O(n)的栈来辅助算法的实现。但是Morris中序遍历只有O(n)的空间复杂度不需要额外的辅助空间。其本质在于在中序遍历顺序“左中右”时遍历左子树时在遍历左子树的同时建立线索遍历完左子树后根据线索退回当前结点访问当前结点时要将线索断开再遍历右子树。前驱结点predecessor此处predecessor专门指的是当前结点current左子树中最右边的结点在中序遍历顺序当中前驱结点的顺序在当前结点current的前一位。predecessor的右子树必然是空结点否则必然不是当前结点current的前驱结点。线索参考线索树在遍历左子树时是一个单程路线如果要返回当前结点current就要借助额外的空间进行记录。但是线索就是将前驱结点predecessor和当前链接起来防止在遍历左子树的时候不能退回到当前结点current。具体操作就是将前驱结点predecessor右孩子指向当前结点current。首先树的链接是单向的。其次中序遍历难就在于要先遍历左子树再访问当前结点。从根节点出发遍历左子树在不借助辅助空间记录根节点的时候是没办法返回根结点的。Morris中序遍历就将当前结点current的前驱结点predecessor与current建立线索即建立回程的路这样在中序遍历时就不需要借助额外的辅助空间。建立线索的同时也改变了二叉树的结构因此也要有断开线索的操作复原二叉树。Morris主要步骤找到current的predecessor建立线索遍历左子树退回current断开线索并访问current遍历右子树Morris算法模板1.current无左孩子访问currentcurrent current-right2.current有右孩子找predecessor1.predecessor无右孩子predecessor-right currentcurrent current-left2.predecessor有右孩子访问currentpredecessor-next NULLcurrent current-right你可能会问“刚才不是说predecessor一定没有右孩子吗那算法模板里怎么还要判断predecessor是否有右孩子并且有右孩子还要有相应的操作。”其实观察上面的模板会发现Morris中序遍历对于有左子树的current都是先找predecessor在进行相应的操作因此对于有左子树的同一个结点会找两次predecessor。第一次是在还没遍历左子树时找到predecessor建立线索然后进入左子树进行遍历第二次是在遍历完左子树后退回当前结点找到predecessor断开线索然后访问当前结点并进入右子树进行遍历。从另一个角度看判断predecessor是否有右孩子也是判断当前中序遍历到哪一个步骤predecessor无右孩子则当前还没遍历左子树因此要建立线索并遍历左子树predecessor有右子树则当前是已经遍历完左子树即已经建立了线索并退回到当前结点因此要断开线索访问当前结点遍历右子树。因此在找predecessor的时候有两个判断条件一个是右孩子是否为空不为空则继续往右边找另一个是右孩子是否指向current指向current则循环结束。