The secondary traversal is traversed, that is, traversing the left subtree, then accessing the root node, and finally traversing the right tree, this order is the same for each sub-tree, which is the commonality of the subtree, so it can set the cycle in turn, one by one Access each node. This action is done for the subtree of each tree. Therefore, when starting traversing, you should first find the leftmost node, and the traversal should start from now on. If you visit this node, you should access the root node and the right child of this node one by one. A little difficult first is to find the leftmost node. The method is to NULL from the root nodes of the tree. The second is to access the right sequence in the order of the order after accessing the root node. For the right tree, be sure to understand it as a subtree, so the traversal of it is also the leftmost node of the subtree, and then start traversing. The algorithm of the secondary traversal binary tree non-recursive algorithm is: 1, set a stack S and a pointer P pointing to the tree root, with P point to point to the Lchild Lchild and let it down until the P == Null jumps out the loop. In this process, each node is in the stack, then P pointing at the top of the tree. 2, the top of the stack is set to access the leftmost node. (This step is very important, in order to realize the order of the first-stop node to access the root node in the order of the elements in the stack. The elements within the stack are quenched by the elements sequence traversed in the order.) 3, Access the root node of the leftmost point. 4. Since the right sub-tree is understood as a subtree, the traversal of it is also a method of traversing the right sequence, so the root node of the right sub-tree is understood to start the root nodes of the tree, so the statement P = P-> rchild, starting over the traversal of a tree, the P pointer will walk every node of the right tree. Including the bifurcation algorithm in the attachment, you can directly copy the paste to VC to compile. Considering that only a demonstration role, the space release program is not written, please hesight. The younger brother is shallow, and it is now ugly. This program is successful in VC 6.0: / *
* CopyRight (C) 2004
* All Rights Reserved.
*
* File Name: Traverse.c
* File ID: One of the various operations of the binary tree
* Summary: binary tree operation, including the recurrent algorithm of sequence, order and sequence traversal traversal,
* Non-creation algorithm traversed in the middle.
* Current version: 1.0
* Author: yu
* Completion date: July 31, 2004
*
* Replacement version: 1.0
* Original author: yu
* Completion date: July 31, 2004
* /
#include
#include
#define stack_init_size 100 / / The number of spatial numbers initially assigned
#define stackincream 10 / / The number of spaces in the stack space increase
Typedef char Eletype; // binary tree node information type
Typedef struct bitnode // binary nodes type
{
Struct Bitnode * LCHILD, * RCHILD;
Eletype Data;
} Bitnode;
Typedef BitNode * ELMTYPE; // ELEMTYPE Declaration is a pointer type
Typedef struct stack // stack storage type, dynamic assignment
{
ELMTYPE * BASE;
ELMTYPE * TOP;
Int stacksize;
} SQSTACK;
SQSTACK * INITSTACK () // Creating a stack
{
Sqstack * S;
IF (! (s = (SQSTACK *) Malloc (Sizeof (Sqstack)))) EXIT (-1);
S-> Base = (ELEMTYPE *) Malloc (stack_init_size * sizeof (elemType)); // Initialization To the stack assignment STACK_INIT_SIZE ELEMTYPE Type Space IF (! S-> Base) // Assignment Space Failed
{
EXIT (-2);
Printf ("Stack Space Allocation Failed! / N");
}
IF (S-> Base) // Assignment Space
Printf ("Successful Stack Space Allocation! / N");
S-> TOP = S-> Base; // Initialization stack head pointer
S-> stacksize = stack_init_size;
Return S;
}
Void Push (Sqstack * S, ELMTYPE E) // Stack, e If an address
{
IF (S-> TOP-S-> Base> = S-> stacksize) // Stack full
{
S-> Base = (ELEMTYPE *) Realloc (S-> Base, (S-> stacksize stackincream * sizeof (elemType)); // Infoot to increase space
IF (! S-> Base) // increase allocation space failure
EXIT (-2);
S-> stacksize = stackincream;
}
* (S-> TOP) = E;
S-> TOP ;
}
ELMTYPE POP1 (SQSTACK * S) // Out of the stack 1, the returnful E is a stack top element is an address
{
ELMTYPE E;
IF (S-> TOP == S-> Base) return 0; / / Stack Empty return
S-> TOP -;
e = * (S-> TOP);
Return E;
}
INT stackempty (sqstack * s) // Judging the stack empty, the stack returns 1, otherwise returns 0
{
IF (S-> Base == S-> TOP) Return 1;
Else Return 0;
}
BitNode * createbitree () // Preface to recreate the tree
{
Char x;
BitNode * T;
Scanf ("% C", & x);
IF (x == ') t = NULL;
Else
{
IF (! (t = (bitnode *) malloc (sizeof (bitnode)))))))
T-> Data = X; // Establish a node
T-> LCHILD = Createbitree (); // built a left subtree
T-> rchild = cretebitree (); // Building a right child
}
Return T;
}
INT inorder (bitnode * t) // eschent traversal binary tree non-recursive algorithm
{
Sqstack * S;
BitNode * P;
s = initstack (); // Initialization
P = T;
Printf ("" Traverse Tree, Character Sequence is: / N ");
While (p ||! stackempty (s))
{
While (p) // find the leftmost node
{
Push (S, P);
P = p-> lchild; // p pointer smooth LCHILD
}
P = POP1 (s); // Stack top element outlet to access the leftmost node
Printf ("% c", p-> data); // Access the leftmost node
P = P-> rChild;
}
Printf ("/ n");
Return 1;
}
void main ()
{
BitNode * T;
Printf ("Please enter a tree character sequence, indicate null: / n" in space);
T = CreateBitree ();
Inorder (t);
}
