【数据结构】多叉树的深度优先遍历DFS和广度优先遍历BFS（含C++递归和非递归方式实现）

• 前言
• 1. 深度优先遍历
• • 1.2 先序遍历
  • • 1.2.1 C++递归实现
    • 1.2.2 C++非递归实现
  • 1.2 后序遍历
  • • 1.2.1 C++递归实现
    • 1.2.2 C++非递归实现
• 2. 广度优先遍历
• • 2.1 C++递归实现
  • 2.2 C++非递归实现

树的遍历，是指依照一定的规律不重复地访问树中的每个节点。在本篇文章中我们主要介绍多叉树的深度优先遍历（DFS）和广度优先遍历（BFS）。

深度优先遍历指的是是从根节点开始沿着树的每一个枝遍历到叶子节点，再遍历其他的枝。深度优先遍历又分为先序遍历和后序遍历，具体如下图所示：

在进行实现之前，我们先实现多叉树的数据结构，其结构如下：

struct Node{
    char data;
    vector children;
    Node(char data):data(data){}
};

我们给出一个多叉树如下图：

实现该多叉树如下图所示：

int main(){
    Node root('A');
    Node B('B');
    Node C('C');
    Node D('D');
    Node E('E');
    Node F('F');
    Node G('G');
    Node H('H');
    Node I('I');
    Node J('J');

    root.children.push_back(&B);
    root.children.push_back(&C);

    B.children.push_back(&D);
    D.children.push_back(&G);
    D.children.push_back(&H);
    D.children.push_back(&I);
    C.children.push_back(&E);
    C.children.push_back(&F);
    E.children.push_back(&J);
}

先序遍历即是指父节点先于子节点访问，访问顺序为A → B → D → G → H → I → C → E → J → F。访问顺序如下图所示：

我们实现代码如下：

void Preorder(Node* root){
    // 先序遍历
    if(nullptr == root) return;
    // 访问当前节点
    cout << root->data << endl;
    // 访问子节点
    for(auto node:root->children){
        Preorder(node);
    }
}

非递归写法其实就是将递归写法写成迭代方法访问，这时候往往需要一个栈来辅助访问，具体代码如下：

void preorder_stack(node* root){
    if(nullptr == root) return;
    stack s;
    s.push(root);
    while(!s.empty()){
        node* node = s.top();
        s.pop();
        cout << node->data << " ";
        for(int i=node->children.size()-1; i>=0; i--){
            s.push(node->children[i]);
        }       
    }
}

访问过程中优先处理子节点，上图中的后续遍历结果为G → H → I → D → B → J → E → F → C → A。访问顺序如下图所示：

void Postorder(Node* root){
    // 先序遍历
    if(nullptr == root) return;
    // 访问子节点
    for(auto node:root->children){
        Postorder(node);
    }
    // 访问当前节点
    cout << root->data << endl;
}

同先序遍历中的思路相同，后序遍历的非递归写法也是写成迭代方法访问，需要一个栈来辅助访问，具体代码如下：

void Postorder_stack(Node* root){
    if(nullptr == root) return;
    stack s;
    s.push(root);
    Node* pre = root;
    while(!s.empty()){
        Node* node = s.top();
        if(node->children.empty() // 叶子结点
                || pre == node->children.back() // 分支节点的叶子节点完>成访问
        ){
            s.pop();
            cout << node->data << " ";
        }else{
            for(int i=node->children.size()-1; i>=0; i--){
                s.push(node->children[i]);
            }
        }
        pre = node;
    }
}

广度优先遍历从根节点开始从上到下按照层依次遍历。上图中的多叉树的遍历结果为A → B → C → D → E → F → G → H → I → J。遍历顺序如下图所示：

我们首先需要求得该多叉树的深度，在进行遍历的时候利用traverLayer找到对应的那一行输出遍历，具体代码如下：

int depth(Node* root) {
    if(nullptr == root) return 0;
    int maxdepth = 0;
    for(auto child : root->children){
        maxdepth = max(maxdepth, depth(child));
    }
    return maxdepth+1;
}
void traverLayer(Node* root, int level){
    if(nullptr == root) return;
    if(level == 0){
        cout << root->data << " ";
    }else{
        for(auto child:root->children){
            traverLayer(child,level-1);
        }
    }
}
void BFS2(Node* root){
    if(nullptr == root) return;
    int n=depth(root);
    for(int i=0; i
        traverLayer(root, i);
    }
}

具体实现代码如下：

void BFS(Node* root){
    if(nullptr == root) return;
    queue q;
    q.push(root);
    while(!q.empty()){
        Node* node = q.front();
        q.pop();
        cout << node->data << endl;
        for(auto child:node->children){
            q.push(child);
        }
    }
}