我们知道遍历一棵二叉树,无论是先序遍历、中序遍历、后序遍历都需要一个O(n)大小的栈空间(系统栈或程序员控制的栈),或层次遍历需要一个O(n)大小的队列。那么如何在常量空间内遍历呢?
本文介绍Deutsch-Schorr-Waite算法,可以使用常量空间、线性时间遍历任意图。本文主要以二叉树为例(二叉树是特殊的有向图)。
算法的关键是指针反转。当访问过程向下遍历子树时,它“反转”它所经过的指针:在当前结点的某个指针域保存父节点的地址。当访问过程向上回溯时,再恢复所有指针域原有的值。
遍历一棵二叉树的过程中,对于每个被访问的节点,Deutsch-Schorr-Waite算法先将left域改写成指向父节点的反向指针,然后沿着左子树继续向下遍历。在第二次访问的时候父节点的地址被移动right域中,并恢复left域的原值,然后后沿着右子树继续向下遍历。最后一次访问的时候,right域恢复为它的原值,访问过程通过之前保存在right域中的地址返回父节点。对于每个节点,我们需要一个附加的记号位来指明父指针存放在left域中还是right域中。那么这不还是每个节点需要一个位吗?空间还是O(n)的,但是我们可以利用指针域的低位来保存这个标记位。
如二叉树节点定义
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
};
32位系统中,该结构体的大小是12字节,默认情况下编译器都会把该结构体的变量放在起始地址为4的倍数的地方,也就是说left和righ的值低两位都为0,我们可以利用这些位,从而避免了使用O(n)的空间。本文实现代码中使用left域中的最低位做标记。
算法实现参考代码如下:
#pragma pack(4) struct TreeNode { int val; TreeNode *left; TreeNode *right; }; void Visit(TreeNode * node) { printf("%d\n", node->val); } void Traversal(TreeNode * root) { if(root == NULL) return; TreeNode * previous = NULL; TreeNode * current = root; TreeNode * next; while(1) { // 一直向下访问左子树 while(current != NULL) { // 第一次访问,访问节点数据,将父节点地址保存在left域中,然后继续向下访问左子树 Visit(current); next = current->left; current->left = previous; previous = current; current = next; } // 回溯,直到某个节点的右子树还未访问 while(previous != NULL && ((int)previous->left & 0x01)) { // 第三次访问,现在父节点地址保存在right域中,清除标记,恢复right原值,返回到父节点 previous->left = (TreeNode*)((int)previous->left & 0xfffffffe); next = previous->right; previous->right = current; current = previous; previous = next; } if(previous == NULL) // 第三次访问根节点,整棵树遍历结束,退出循环 break; else { // 第二次访问,现在父节点地址保存在left域中,标记, // 恢复left域原值,将父节点地址保存在right域中,然后进入右子树 previous->left = (TreeNode*)((int)previous->left | 0x01); next = (TreeNode*)((int)previous->left & 0xfffffffe); previous->left = (TreeNode*)(((int)previous->left & 0x01) | (int)current); current = previous->right; previous->right = next; } } }
参考资料:
《垃圾收集》,人民邮电出版社。