Using Morris Traversal, we can traverse the tree without using stack and recursion. The algorithm for Preorder is almost similar to Morris traversal for Inorder.
1...If left child is null, print the current node data. Move to right child.….Else, Make the right child of the inorder predecessor point to the current node. Two cases arise:
………a) The right child of the inorder predecessor already points to the current node. Set right child to NULL. Move to right child of current node.
………b) The right child is NULL. Set it to current node. Print current node’s data and move to left child of current node.
2...Iterate until current node is not NULL.
From http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html
1. 如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。
2. 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。
a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。输出当前节点（在这里输出，这是与中序遍历唯一一点不同）。当前节点更新为当前节点的左孩子。
b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空。当前节点更新为当前节点的右孩子。
3. 重复以上1、2直到当前节点为空。
void morrisTraversalPreorder(struct node* root){ while (root) { // If left child is null, print the current node data. Move to // right child. if (root->left == NULL) { printf( "%d ", root->data ); root = root->right; } else { // Find inorder predecessor struct node* current = root->left; while (current->right && current->right != root) current = current->right; // If the right child of inorder predecessor already points to // this node if (current->right == root) { current->right = NULL; root = root->right; } // If right child doesn't point to this node, then print this // node and make right child point to this node else { printf("%d ", root->data); current->right = root; root = root->left; } } }}