二叉树遍历——深度优先(DFS)与广度优先(BFS)

我不是女神ヾ 2022-05-16 12:12 250阅读 0赞

# **二叉树的深度优先遍历（DFS）与广度优先遍历（BFS）** #

**深度优先遍历：**从根节点出发，沿着左子树方向进行纵向遍历，直到找到叶子节点为止。然后回溯到前一个节点，进行右子树节点的遍历，直到遍历完所有可达节点为止。

**广度优先遍历：**从根节点出发，在横向遍历二叉树层段节点的基础上纵向遍历二叉树的层次。

**DFS实现：**

数据结构：栈

父节点入栈，父节点出栈，先右子节点入栈，后左子节点入栈。递归遍历全部节点即可

**BFS实现：**

数据结构：队列

父节点入队，父节点出队列，先左子节点入队，后右子节点入队。递归遍历全部节点即可

#include <iostream>
    #include <stdlib.h>
    #include <malloc.h>
    #include <Stack>
    #include <Queue>
    using namespace std;
     
    typedef struct Node {
        char data;
        struct Node *lchild;
        struct Node *rchild;
    } *Tree;
    //Tree 是一个node指针的类型定义
     
    int index = 0;  //全局索引变量
    //二叉树构造器,按先序遍历顺序构造二叉树
    //无左子树或右子树用'#'表示
    void treeNodeConstructor(Tree &root, char data[]){
        char e = data[index++];
        if(e == '#'){
            root = NULL;
        }else{
            root = (Node *)malloc(sizeof(Node));
            root->data = e;
            treeNodeConstructor(root->lchild, data);  //递归构建左子树
            treeNodeConstructor(root->rchild, data);  //递归构建右子树
        }
    }
    //深度优先遍历
    void depthFirstSearch(Tree root){
        stack<Node *> nodeStack;  //使用C++的STL标准模板库
        nodeStack.push(root);
        Node *node;
        while(!nodeStack.empty()){
    	    node = nodeStack.top();
    		cout<<node->data;//遍历根结点
            nodeStack.pop();
            if(node->rchild){
                nodeStack.push(node->rchild);  //先将右子树压栈
            }
            if(node->lchild){
                nodeStack.push(node->lchild);  //再将左子树压栈
            }
        }
    }
     
    //广度优先遍历
    void breadthFirstSearch(Tree root){
        queue<Node *> nodeQueue;  //使用C++的STL标准模板库
        nodeQueue.push(root);
        Node *node;
        while(!nodeQueue.empty()){
            node = nodeQueue.front();
            nodeQueue.pop();
            cout<<node->data;//遍历根结点
            if(node->lchild){
                nodeQueue.push(node->lchild);  //先将左子树入队
            }
            if(node->rchild){
                nodeQueue.push(node->rchild);  //再将右子树入队
            }
        }
    }
     
    int main() {
        //上图所示的二叉树先序遍历序列,其中用'#'表示结点无左子树或无右子树
        char data[15] = {'A', 'B', 'D', '#', '#', 'E', '#', '#', 'C', 'F','#', '#', 'G', '#', '#'};
        Tree tree;
        treeNodeConstructor(tree, data);
        printf("深度优先遍历二叉树结果: ");
        depthFirstSearch(tree);
        printf("\n\n广度优先遍历二叉树结果: ");
        breadthFirstSearch(tree);
        return 0;
    }

# 深度优先搜索习题 #

Given a binary tree, find its minimum depth.The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.（求给定二叉树的最小深度）

思路：深度优先搜索

递归，若为空树返回0；

若左子树为空，则返回右子树的最小深度+1；（加1是因为要加上根这一层，下同）

若右子树为空，则返回左子树的最小深度+1；

若左右子树均不为空，则取左、右子树最小深度的较小值，+1；

虽然没有用到栈的数据结构，但本质上思想就是深度优先搜索。

参考代码：

class Solution {
    public:
        int run(TreeNode *root)
        {
            if(root == nullptr) return 0;
            if(root->left == nullptr) // 若左子树为空，则返回右子树的最小深度+1
            {
                return run(root->right)+1;
            }
            if(root->right == nullptr) // 若右子树为空，则返回左子树的最小深度+1
            {
                return run(root->left)+1;
            }
            // 左右子树都不为空时，取较小值
            int leftDepth = run(root->left);
            int rightDepth = run(root->right);
            return min(leftDepth+1,rightDepth+1);
        }
    };

#  #

# 广度优先搜索习题 #

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

/*
    struct TreeNode {
    	int val;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	TreeNode(int x) :
    			val(x), left(NULL), right(NULL) {
    	}
    };*/
    class Solution {
    public:
        vector<int> PrintFromTopToBottom(TreeNode* root) {
            vector<int> res;
            if(root==NULL)
                return res;
            queue<TreeNode*> q;
            q.push(root);
            while(!q.empty()){
                res.push_back(q.front()->val);
                if(q.front()->left!=NULL)
                    q.push(q.front()->left);
                if(q.front()->right!=NULL)
                    q.push(q.front()->right);
                q.pop();
            }
            return res;
        }
    };