The recursive and non recursive implementation of sequential traversal binary tree is analyzed in depth

1, first order traversal binary tree   The recursive implementation
Thought: if the binary tree is empty, return. Otherwise,
1) traverse the root node;
2) first order traverses the left subtree;
3) first order traverses the right subtree;

Code:

template<typename elemType> 
void PreOrder(nodeType<elemType> *root)  
{  
    if(root==NULL)  
        return ;  
    visit(root->data); // visit the data
    PreOrder(root->lchild); //Recursive call, the first order traverses the left subtree & NBSP;
    PreOrder(root->rchild); //Recursively, the order traverses the right subtree & NBSP;
}  

2, first order traversal binary tree non-recursive implementation
Thought: binary tree non-recursive first order traversal, first order traversal thought: first let the root into the stack, as long as the stack is not empty, you can do pop-up operation, every time a node, remember to put its left and right nodes are pushed into the stack, remember the right subtree first stack, so that can ensure that the right subtree in the stack is always at the bottom of the left subtree.

The idea of nonrecursive algorithm of preorder traversal binary tree
Set up Stack;
T points to the root;
When t is not empty or the Stack is not empty, repeat:
          If t is not empty, access t, t push; T refers to left children;
          Otherwise: push top element to t;
          T points to the right child;
The end of the

void PreOrder_Nonrecursive(BinaryTree T)     //Non - recursive & NBSP of first order traversal; & have spent & have spent
{  
    if(!T) return ;    
    stack<BinaryTree> s;  
    s.push(T);  
    while(!s.empty())  
    {  
        BinaryTree temp = s.top();  
        visit(temp->data);  
        s.pop();  
        if(temp->rchild)  
            s.push(temp->rchild);  
        if(temp->lchild)  
            s.push(temp->lchild);  
    }  
}