链表，栈和队列等线性数据结构的遍历很简单，但是到了非线性遍历方法多了很多。 主要有两类：深度优先遍历（DFS）和广度优先遍历（BFS）。这里你可能会想到，不应该是前序、中序、后序遍历吗。没错，这些其实就是深度优先遍历的几种方式。而广度优先遍历的访问原则“先上后下-先左后右”，所以不像深度优先优先遍历，根据访问节点方式的不同有不同方式。

##深度优先遍历

1.递归实现

// 前序递归遍历T
void preOrder(TreeNode *root) {
    if(root == NULL)
        return;
    cout << root->val << endl;
    preOrder(root->left);
    preOrder(root->right);
}

2.非递归实现

void preOrder(TreeNode *root) {
    if(root == NULL)
        return;

    stack<TreeNode *> stk;
    stk.push(root);
    while(!stk.empty()) {
        TreeNode *pNode = stk.top();
        stk.pop();
        cout << pNode->val << endl;
        if(pNode->right != NULL)
            stk.push(pNode->right);
        if(pNode->left != NULL)
            stk.push(pNode->left);
    }
}

##广度优先遍历

// 用queue实现的BFS  
void BFS(Node *pRoot) {  
    if (pRoot==NULL)  
        return;  
  
    queue<Node*> Q;
    Q.push(pRoot);  
  
    while(!Q.empty()) {    
        Node *node = Q.front();
        cout<<node->nVal<<"->";  
        if (node->pLeft!=NULL) {  
            Q.push(node->pLeft);  
        }  
  
        if (node->pRight!=NULL) {  
            Q.push(node->pRight);  
        }  
  
        Q.pop();  
    }  
  
    cout<<endl;  
}