树的DFS和BFS

原文链接：https://blog.csdn.net/qq_39355828/article/details/119347112 (opens new window)

# 树的DFS和BFS

# DFS：深度优先搜索

递归方式：沿着某一条路径一直深入，直至遇到到达最下的一层，然后再回溯。递归方式

void dfs(TreeNode root)
{
    if(root==null)
        return;
    //对元素进行访问
    System.out.println(root.val);
    dfs(root.left);
    dfs(root.right);
}
//递归方式实现DFS 元素的访问
 public static void dfs(TreeNode root)//递归方式进行元素的访问
    {
        if(root==null)//如果等于null,则直接访问
            return;
        System.out.println(root.val);
        //对元素进行访问
        if(root.left!=null)
        dfs(root.left);
        if(root.right!=null)
        dfs(root.right);
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

非递归方式：借助队列实现二叉树的深度优先遍历

//不使用递归方式，使用栈的方法实现遍历
public static void dfs2(TreeNode root)
    {
        if(root==null)
            return;
        Stack<TreeNode>stack=new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty())
        {
            root=stack.pop();
            System.out.println(root.val);
            if(root.right!=null)
                stack.push(root.right);
            if(root.left!=null)
                stack.push(root.left);
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# BFS：广度优先

//广度优先，借助队列实现
    public static void bfs(TreeNode root)
    {  Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty())
        {
            TreeNode node=queue.poll();//弹出队列头
            System.out.println(node.val);
            if(node.left!=null)//将节点压入栈中，左子树先入队列，则左子树先出去
                queue.add(node.left);
            if(node.right!=null)//右子树压入栈中
                queue.add(node.right);
        }

    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 测试程序：

public class test101 {

    public static void main(String[] args) {
       TreeNode root=new TreeNode(1);
       TreeNode treeNode2=new TreeNode(2);
       TreeNode treeNode3=new TreeNode(3);
       TreeNode treeNode4=new TreeNode(4);
       TreeNode treeNode5=new TreeNode(5);
       TreeNode treeNode6=new TreeNode(6);
       TreeNode treeNode7=new TreeNode(7);
       TreeNode treeNode8=new TreeNode(8);
        TreeNode treeNode9=new TreeNode(9);
        TreeNode treeNode10=new TreeNode(10);
        TreeNode treeNode11=new TreeNode(11);
        TreeNode treeNode12=new TreeNode(12);
        root.left = treeNode2;
        root.right = treeNode3;

        treeNode2.left = treeNode4;
        treeNode2.right = treeNode5;

        treeNode3.left = treeNode6;
        treeNode3.right = treeNode7;

        treeNode4.left = treeNode8;
        treeNode5.left = treeNode9;
        treeNode6.left = treeNode10;

        treeNode7.left = treeNode11;
        treeNode7.right = treeNode12;
        System.out.println("广度优先");
        bfs(root);
        System.out.println("深度优先");
        dfs(root);
        System.out.println("深度优先2");
        dfs2(root);

    }
}