
For a data structure, the traversal is a common operation. Binary Tree is a basic data structure, is the son of an effect that every node number is not more than two trees. Binary tree node declaration as follows:
typedef struct TreeNode * PtrToNode;
typedef struct TreeNode * BinTree;
struct TreeNode
{
int Data; // For simplicity, let's assume that the elements of the tree node to an int
BinTree Left;
BinTree Right;
};
Binary tree traversal main preorder, preorder, after preorder, preorder layer four ways, introduced one by one below.
1. preorder
Prior preorder traversal of the nodes access the work before it is carried out about his son being accessed. In other words, the order preorder access node is the root node  the son left  and right son. Since the tree can be defined recursively, so common operations with recursive tree is often convenient clear. Recursive code is as follows:
void PreOrderTraversal (BinTree BT)
{
if (BT)
{
printf ( "% d \ n", BT> Data); // do some access nodes such as print
PreOrderTraversal (BT> Left); // access left son
PreOrderTraversal (BT> Right); // Right access sons
}
}
As it can be seen from the recursive code, which is a recursive tail recursion (tail recursion recursive form that is at the end of the function or the function is about to return to the previous). Tailrecursive recursive call stack information needed to store the call, when a largescale data easily when stack space beyond. Although most of the compiler can automatically remove the tailrecursive, but even so, we might as well own removal. Nonrecursive preorder algorithm basic idea: use the stack
. A encountered a node to access it, then put it onto the stack, and to traverse its left subtree;
. B When the left subtree traverse end, the node from the stack pop and son pointing to the right, to continue a step;
c. When all nodes to access the complete and final access node of the tree is empty and the stack is empty, stop.
Codes are as follows:
void PreOrderTraversal (BinTree BT)
{
BinTree T = BT;
Stack S = CreatStack (MAX_SIZE); // create and initialize the stack S
while (T ! IsEmpty (S))
{
while (T) // node along the way to the left and to access (print) was pushed onto the stack
{
printf ( "% d \ n", T> Data);
Push (S, T);
T = T> Left;
}
if (! IsEmpty (S))
{
T = Pop (S); // node popped from the stack
T = T> Right; // turn right subtree
}
}
}
2. preorder
Traversal path traversal and preorder traversal exactly the same. The realization of ideas are very similar with the preorder traversal. The main difference is the order of the different access nodes: traversal is complete access to all the root access and then left his son, and finally the right to access his son, the son is left  the root  the right son.
Recursive code is as follows:
void InOrderTraversal (BinTree BT)
{
if (BT)
{
InOrderTraversal (BT> Left);
printf ( "% d \ n", BT> Data);
InOrderTraversal (BT> Right);
}
}
Nonrecursive codes are as follows:
void InOrderTraversal (BinTree BT)
{
BinTree T = BT;
Stack S = CreatStack (MaxSize); // create and initialize the stack S
while (T ! IsEmpty (S))
{
while (T) // node along the way to the left and pushed onto the stack
{
Push (S, T);
T = T> Left;
}
if (! IsEmpty (S))
{
T = Pop (S); // node popped from the stack
printf ( "% d \ n", T> Data); // (access) print node
T = T> Right; // turn right subtree
}
}
}
3. After preorder
Postorder and preorder, preorder path is exactly the same. The main difference is that postorder traversal visits the nodes in the order is the first visit left son and right son, last access node, left his son  the son of the right  the root node.
Thinking and recursive traversal and preorder is similar to the following code:
void PostOrderTraversal (BinTree BT)
{
if (BT)
{
PostOrderTraversal (BT> Left);
PostOrderTraversal (BT> Right);
printf ( "% d \ n", BT> Data);
}
}
Nonrecursive implementation after preorder
Thought one:
For a node in order to achieve access to the left of the son  the son of the right  the root node, you can use LIFO stack, under the premise of the node is not empty, then click the root node, the right son, left his son push. Therefore, we need to follow the root  the son of the right  left son sequential traversal of the tree, and we already know preorder traversal order is the root  son left  and right son, just so around preorder traversal of exchange and the access method Print to another stack can be pushed. Finally, print stack elements together. Code is as follows:
void PostOrderTraversal (BinTree BT)
{
BinTree T = BT;
Stack S1 = CreatStack (MAX_SIZE); // create and initialize the stack S1
Stack S2 = CreatStack (MAX_SIZE); // create and initialize the stack S2
while (T ! IsEmpty (S1))
{
while (T) // node has access to the right and along the way (pressed into S2) after pushed onto the stack S1
{
Push (S2, T);
Push (S1, T);
T = T> Right;
}
if (! IsEmpty (S1))
{
T = Pop (S1); // node popped from the stack
T = T> Left; // turn left subtree
}
}
while (! IsEmpty (S2)) // access (print) S2 elements
{
T = Pop (S2);
printf ( "% d \ n", T> Data);
}
}
Thinking is due to the advantages of a firstorder traversal utilizes the idea of the code neater, clearer thinking. The disadvantage is that all nodes need to use a stack to store the tree, take up more space.
Thought two:
To access a node on a node of the conditions of access is a right son. Prev we can add a variable to determine the current node Curr a relationship with it to perform the corresponding operation.
• If Prev empty (Curr is the root node) or Prev Curr is the parent node, Curr node left child and right child respectively pushed onto the stack;
• If Prev Curr is left son and right son will Curr onto the stack;
• Otherwise Prev Curr's son is a right, access Curr;
Code is as follows:
void PostOrderTraversal (BinTree BT)
{
if (BT == NULL)
return;
Stack S = CreatStack (MAX_SIZE);
BinTree Prev = NULL, Curr = NULL; // initialize
s.push (BT);
while (! IsEmpty (S))
{
Curr = Top (S); // the top element is assigned Curr
if (Prev == NULL  Prev> Left == Curr  Prev> Right == Curr) // If Prev Curr is NULL or the parent node
{
if (Curr> Left! = NULL)
Push (S, Curr> Left);
else if (Curr> Right! = NULL)
Push (S, Curr> Right);
}
else if (Curr> Left == Prev) // If Prev Curr is left son
{
if (Curr> Right! = NULL)
Push (S, Curr> Right);
}
else
{
printf ( "% d \ n", Curr> Data); // access the current node
Pop (S); // after the popup visit
}
Prev = Curr; // End Curr after processing the current node becomes node Prev
}
}
4. Layer preorder
The core issue of the binary tree traversal is a linear twodimensional structure. When we visited their son around by node, there is a problem after a visit left son and right son how to access. Therefore, we need a storage node structure stored temporarily not accessible. The first three nonrecursive traversal implementation, we are here to save through the stack. In fact, it can be preserved by the queue.
The basic idea queue implementation: traversal starting from the root, the root node into the first team, then the loop: the team node access (access) the root node, left his son into the team, the right son into the team until the queue is empty stop.
The result of this approach is to traverse the binary tree from top to bottom, layer by layer traversal from left to right, the sequence traversal, code as follows:
void LevelOrderTraversal (BinTree BT)
{
BinTree T;
Queue Q; // declare a queue
if (BT == NULL)
return; // If the tree is empty, return directly
Q = CreatQueue (MAX_SIZE); // create and initialize the queue
AddQ (Q, BT); // root node into the team
while (! IsEmpty (Q))
{
T = DeleteQ (Q); // node from the team
printf ( "% d \ n", T> Data); // access to a team of node
if (T> Left) AddQ (Q, T> Left); // If the son is not left empty, its enqueue
if (T> Right) AddQ (Q, T> Right) // if the right son is not empty, it will enqueue
}
} 


