数据结构-二叉树的深度优先和广度优先遍历

╰半夏微凉° 2022-06-15 05:40 187阅读 0赞

# 1.基本概念 #

DFS深度优先遍历：沿着树的深度遍历树的节点，先访问根结点，然后是左子树，右子树  
BFS广度优先遍历：横向遍历，沿着树的宽度，先访问根结点，然后左右子节点。然后是上述左右子节点的子节点，一层一层往下。  
以下图为例：  
![这里写图片描述][binarytree1.png_3313947]  
DFS的结果为【ABDECFG】  
BFS的结果为【ABCDEFG】

# 2.递归实现 #

void DFS(TreeNode* root, vector<int>& ans) {
        if (root == NULL)
            return;
        ans.push_back(root->val);
        DFS(root->left, ans);
        DFS(root->right, ans);
    }

# 3.非递归实现 #

DFS使用stack，先进后出，先入栈的节点后访问

void DFS(TreeNode* root, vector<int>& values) {
        if (root == NULL)
            return;
        stack<TreeNode*> nodes;
        nodes.push(root);
        while (!nodes.empty()) {
            root = nodes.top();
            nodes.pop();
            values.push_back(root->val);
            if(root->right)
                nodes.push(root->right);
            if(root->left)
                nodes.push(root->left);
        }
    }

BFS使用queue，先进先出，先入队列的节点先访问

void BFS(TreeNode* root, vector<int> values) {
        if (root == NULL)
            return;
        queue<TreeNode*> nodes;
        nodes.push(root);
        while (!nodes.empty()) {
            root = nodes.front();
            nodes.pop();
            values.push_back(root->val);
            if(root->left)
                nodes.push(root->left);
            if(root->right)
                nodes.push(root->right);
        }
    }

前序、中序、后序遍历的递归与非递归实现–**[博文链接][Link 1]**

[binarytree1.png_3313947]: /images/20220615/ceadaf81a58b4514b2f0d52caaa29c65.png
[Link 1]: http://blog.csdn.net/my_lovely_lemon_tree/article/details/72721020