| |
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). Tail-recursive recursive call stack information needed to store the call, when a large-scale data easily when stack space beyond. Although most of the compiler can automatically remove the tail-recursive, but even so, we might as well own removal. Non-recursive 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);
}
}
Non-recursive 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 post-order 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);
}
}
Non-recursive 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 first-order 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 pop-up 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 two-dimensional 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 non-recursive 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
}
} |
|
|
|