常量空间遍历二叉树

我们知道遍历一棵二叉树，无论是先序遍历、中序遍历、后序遍历都需要一个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域中的最低位做标记。
算法实现参考代码如下：

[cpp]
#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;
        }
    }
}

#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;
  }
}
}

补充：软件开发 , C++ ,