我們知道遍歷一棵二叉樹，無論是先序遍歷、中序遍歷、後序遍歷都需要一個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;
}
}
}
