| |
I. Introduction
Binary tree traversal methods divided into four types: preorder, inorder, postorder and level traversal.
Wherein, after the traversal methods to achieve before the partial recursive and non-recursive, non-recursive traversal implementation requires the help of the stack.
In fact, is a kind of recursive call stack implementation, therefore, it requires a non-recursive traversal stack by means of artificial structures to achieve.
The level needs to traverse through queue.
II: before after preorder
Recursive traversal:
Ideas and methods recursive traversal is very simple, by adjusting the output statement before achieved in the last three traversal.
Code is as follows:
void show (BiTree T)
{
if (T)
{
printf ( "% c", T-> data); // modify the order of these three statements are achieve three traversal
show (T-> lchild);
show (T-> rchild);
}
}
Non-recursive traversal:
5 summarizes the total different non-recursive traversal algorithm or four ideas, need the help of the stack to complete.
The first traversal algorithm:
Algorithm ideas:
1. Start from the root node, left child if the current node is not empty, then traverse left child in hand stack.
2. The right child node left child node is empty, the stack and traverse the current node
3. In the right child node of the root node, and children continue to traverse along the left, repeating step 1.2
This algorithm preorder traversal
void preorder1 (BiTree T) before 1 // preorder
{
LinkStack s;
InitStack (& s);
BiTree temp;
temp = T;
while (temp ||! EmptyStack (s)) // temp is the first condition for entering the loop
{
if (temp) // traverse the left subtree has been in the end unit
{
Push (& s, temp);
printf ( "% c", temp-> data);
temp = temp-> lchild;
}
else // lchild empty jumps to rchild
{
Pop (& s, & temp);
temp = temp-> rchild;
}
}
}
The second traversal algorithm:
Ideas and first traversal algorithm consensus algorithm, just change the traverse position statement, not into the stack when the output, but in the stack when the output, compared to the former preorder preorder
1. Start from the root node, left child node is not empty, left child into the current stack.
2. The current left child node is empty, the stack and the current output node, and then jump to the right child node
3. Repeat steps 1 and 2 until the stack is empty
void inorder (BiTree T) // preorder
{
LinkStack s;
InitStack (& s);
BiTree temp = T;
while (temp ||! EmptyStack (s))
{
if (temp)
{
Push (& s, temp);
temp = temp-> lchild;
}
else
{
Pop (& s, & temp);
printf ( "% c", temp-> data); // stack when the output is a preorder
temp = temp-> rchild;
}
}
}
The third traversal algorithm:
Such preorder traversal algorithm
Algorithm ideas: 1. First root stack
2. The top of the stack and the stack output, the stack right child node of the current node in the left child node of the current node stack
3. Repeat step 2 until the stack is empty
void preorder2 (BiTree T)
{
LinkStack s;
InitStack (& s);
BiTree temp = T;
Push (& s, temp);
while (! EmptyStack (s))
{
Pop (& s, & temp); // the stack and output
printf ( "% c", temp-> data);
if (temp-> rchild) // stack right child
{
Push (& s, temp-> rchild);
}
if (temp-> lchild) // stack left child
{
Push (& s, temp-> lchild);
}
}
}
The fourth traversal algorithm:
After the non-recursive preorder more complex, to ensure that the left and right output current node has a child node output (or around children is empty)
That is a node for each output to meet one of the following two conditions:
1. This is about child node is empty
2. The nodes around the child has to traverse
Algorithm ideas: 1. First root stack to stack empty of circulatory arrest conditions
2. On the node pointer pre recorded an output node address, cur record the current node address
2.1 current node node around children is empty, or pre recorded for the current node left (right) child, the stack and the current output node and update pre
2.2 otherwise in accordance with the right child, left the child in the order stack
3. Cycle Step 2 until the stack empty
void postorder (BiTree T)
{
BiTree pre, cur;
LinkStack s;
InitStack (& s);
cur = pre = T;
Push (& s, cur);
while (! EmptyStack (s))
{
GetTop (s, & cur); // current node's left and right children are empty, pre for the cur of left child or right child, and the stack output current node
if ((cur-> lchild == NULL && cur-> rchild == NULL) || cur-> lchild == pre || cur-> rchild == pre)
{
Pop (& s, & cur);
printf ( "% c", cur-> data);
pre = cur; // Update the current node
}
else
{
if (cur-> rchild) // Otherwise stack right child, left child
{
Push (& s, cur-> rchild);
}
if (cur-> lchild)
{
Push (& s, cur-> lchild);
}
}
}
}
Fifth traversal algorithm:
Such non-recursive traversal algorithm can be as ideological as recursive traversal sequence by modifying part to do: Before the subsequent three kinds of traversal.
But convenience often bring the complex code structure, such different algorithms means of the stack and above traversal algorithm by means of the stack.
The above algorithm uses data stored in the stack pointer to a binary tree node, and this algorithm is stored in a stack structure
Stack data type definition:
typedef struct {// stack data definition
BiTree ptr;
int task;
} Datatype;
Wherein, task has two values, 0 for visit, 1 traversal. The initial task of all nodes is 1
Algorithm ideas:
1. The root advanced stack, task initialized to 1
2. stack, task if the current node is the current node access 0, 1 task, modify task to zero, according to the order of traversal of the stack you want about child nodes.
For example: If the traversal, the first stack right child node, the current node, left child node. (Other traversal order is changed about the stack order)
3. until the stack is empty, stop the loop
This algorithm is the complete code:
#include < stdio.h>
#include < stdlib.h>
#include < conio.h>
typedef struct binode {// define a binary tree node
char data;
struct binode * lchild, * rchild;
} BiNode, * BiTree;
// To use non-recursive traversal of the stack
#define MAX 50
typedef struct {// stack data definition
BiTree ptr;
int task;
} Datatype;
typedef struct {
Datatype * arr;
int top;
int stacksize;
} SqStack; // sequence of stack
void InitStack (SqStack * S) // initialize the stack character
{
S-> arr = (Datatype *) malloc (sizeof (Datatype) * MAX);
if (S-> arr == NULL)
{
printf ( "Failed to initialize .... \ n");
exit (0);
}
S-> top = -1;
S-> stacksize = MAX;
}
int Push (SqStack * S, Datatype ch) // push (character stack)
{
Datatype * p;
int select;
if (S-> top + 1 == S-> stacksize) // first determine whether the stack is full
{
printf ( "stack full, can not push");
return 0;
}
S-> arr [++ S-> top] = ch;
return 1;
}
int Pop (SqStack * S, Datatype * ch) // stack (Stack characters)
{
if (S-> top < 0)
{
printf ( "stack is empty .... \ n");
return 0;
}
* Ch = S-> arr [S-> top];
S-> top--;
return 1;
}
int GetTopStack (SqStack S, Datatype * ch) // fetch character stack
{
if (S.top < 0)
{
return 0;
}
* Ch = S.arr [S.top];
return 1;
}
int EmptyStack (SqStack S) // determine the stack space
{
if (S.top < 0)
{
return 1;
}
return 0;
}
/ ************************************************************ Stack end ***************** **************** /
void CreateBitree (BiTree * T) to create a binary sequence before //
{
char ch;
scanf ( "% c", & ch);
getchar ();
if (ch == '#')
{
* T = NULL;
}
else
{
* T = (BiTree) malloc (sizeof (BiNode));
(* T) -> data = ch;
CreateBitree (& ((* T) -> lchild));
CreateBitree (& ((* T) -> rchild));
}
}
void View (BiTree T) // non-recursive traversal traversal order to achieve different nodes amend the first sentence of the stack else order
{
Datatype temp;
BiTree p;
temp.task = 1;
temp.ptr = T;
SqStack S;
InitStack (& S);
if (T == NULL) return;
Push (& S, temp);
while (! EmptyStack (S))
{
Pop (& S, & temp); // first root out the stack
p = temp.ptr; // address root record
if (temp.task == 0) // task to access output 0
{
printf ( "% c", temp.ptr-> data);
}
else // task 1 will push children
{
if (p-> rchild) // right child into the stack
{
temp.task = 1;
temp.ptr = p-> rchild;
Push (& S, temp);
}
temp.task = 0; // root of the state traversal to access, and then into the stack
temp.ptr = p;
Push (& S, temp);
if (p-> lchild) // left child into the stack
{
temp.ptr = p-> lchild;
temp.task = 1;
Push (& S, temp);
}
}
}
printf ( "\ n");
}
int main () // create a binary tree: a b d # # e # # c f # # g # #
{
BiTree T;
CreateBitree (& T);
printf ( "traversal is:");
View (T);
return 0;
}
III: Hierarchy traversal
Traverse the level required to use the queue
Algorithm idea when invoices, ie press the left child, right child into the queue to order for each node access level is traversing the queue.
I will not go into here thinking algorithm step, and directly on the code.
void DispLayer (BiTree T) // traverse the level
{
// Install binary tree node address queue; LinkQueue rear
BiTree view = NULL;
InitQueue (& rear);
if (T == NULL)
{
return;
}
EnQueue (& rear, T); // address root loaded into the first total
while (! EmptyQueue (rear)) // traverse the queue is empty then completed
{
DeQueue (& rear, & view); // root out small queue
printf ( "% c", view-> data); // output small roots
if (view-> lchild) // root around small children into the queue exists
{
EnQueue (& rear, view-> lchild);
}
if (view-> rchild)
{
EnQueue (& rear, view-> rchild);
}
}
printf ( "\ n");
} |
|
|
|