如果能使用额外的空间的话那还比较容易,但如果要求O(1)的空间,那就需要提供指向父节点的指针来帮助回溯
p = T; while(p) { while(p->left) p = p->left; Visit(p); if(p->right) p = p->right; else { while(p->parent) { if(p->parent->left == p) { Visit(p->parent); if(!p->parent->right) p = p->parent; else { p = p->parent->right; break; } } else p = p->parent; } } if(!p->parent) p = p->parent;//p=null }
这里有两篇非递归遍历的总结帖:
http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html