欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树的广度优先遍历和深度优先遍历(Java版)

程序员文章站 2022-05-21 19:28:29
...
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int x){val=x;}
}

public class Main {
    static List<Integer> BFSList=new ArrayList<>();
    static List<Integer> DFSList=new ArrayList<>();
    public static void main(String[] args) {
        TreeNode root=new TreeNode(1);
        TreeNode second=new TreeNode(2);
        TreeNode three=new TreeNode(3);
        TreeNode four=new TreeNode(4);
        TreeNode five=new TreeNode(5);
        TreeNode six=new TreeNode(6);
        TreeNode seven=new TreeNode(7);
        root.right=three;
        root.left=second;
        second.right=five;
        second.left=four;
        three.right=seven;
        three.left=six;
        BFS(root);
        DFS(root);
        System.out.print("广度优先遍历结果:");
        printList(1);
        System.out.println();
        System.out.print("深度优先遍历结果:");
        printList(2);
    }

    public static void BFS(TreeNode root)
    {
        if(root==null)
            return;
        //广度优先遍历使用队列实现
        Queue<TreeNode> queue=new LinkedList<>();//使用LinkedList来实现队列
        queue.add(root);//将根结点入队
        while (!queue.isEmpty())
        {
            //如果队列元素不为空,则进行出队操作
            TreeNode node=queue.poll();
            /*poll返回当前删除的节点,若为空则返回null。也可以用remove,若为空,则抛出异常"NoSuchElementException"
            */
            BFSList.add(node.val);//保存当前遍历结点的值
            if(node.left!=null)
                queue.add(node.left);
            if(node.right!=null)
                queue.add(node.right);
        }
    }

    public static void DFS(TreeNode root)
    {
        if(root==null)
            return;
        //深度优先遍历使用栈实现
        Stack<TreeNode> stack=new Stack<TreeNode>();
        stack.add(root);//将根结点入栈
        //如果栈元素不为空,则进行出出栈操作
        while (!stack.isEmpty())
        {
            TreeNode node=stack.pop();
            DFSList.add(node.val);
            if(node.right!=null)
                stack.push(node.right);
            if(node.left!=null)
                stack.push(node.left);
        }


    }
    
    public static void printList(int flag)
    {
        //打印广度优先遍历结果
        if(flag==1)
        {
            for(int i=0;i<BFSList.size();i++)
            {
                System.out.print(BFSList.get(i)+" ");
            }
        }
        //打印广度优先遍历结果
        else if(flag==2)
        {
            for(int i=0;i<DFSList.size();i++)
            {
                System.out.print(DFSList.get(i)+" ");
            }
        }
        else
            return;
    }
}