/images/1.jpg

lf_Initative

人心惟危,道心惟微,惟精惟一,允执厥中

树的遍历之Morris遍历

有一种巧妙的方法可以在线性时间内,只占用常数空间来实现树的遍历。这种方法由 J. H. Morris 在 1979 年的论文「Traversing Binary Trees Simply and Cheaply」中首次提出,因此被称为 Morris 遍历。核心思想是利用树的大量空闲指针,实现空间开销的极限缩减(和线索二叉树底层原理相同)