用java写个二叉树宽度优先遍历

谁践踏了优雅 2024-03-27 18:02 36阅读 0赞

好的，这里是用 Java 写的二叉树的宽度优先遍历的代码示例：

import java.util.LinkedList;
    import java.util.Queue;
    
    public class BinaryTreeBFS {
        public static class TreeNode {
            int val;
            TreeNode left;
            TreeNode right;
    
            TreeNode(int x) {
                val = x;
            }
        }
    
        public static void bfs(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
    
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                System.out.print(node.val + " ");
    
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }
    
        public static void main(String[] args) {
            TreeNode root = new TreeNode(1);
            root.left = new TreeNode(2);
            root.right = new TreeNode(3);
            root.left.left = new TreeNode(4);
            root.left.right = new TreeNode(5);
            root.right.left = new TreeNode(6);
            root.right.right = new TreeNode(7);
    
            bfs(root);  // 输出: 1 2 3 4 5 6 7
        }
    }

在这段代码中，我们定义了一个 `TreeNode` 类表示二叉树的节点，其中包含了节点的值(`val`)、左子节点(`left`)和右子节点(`right`)。然后我们定义了一个 `bfs` 函数，用于实现二叉树的宽度优先遍历。

我们使用一个队列来保存当前遍历到的节点，每次取出队列的头部元素，访问它，然后将它的左右子节点加入队列中。这样我们就可以保证每个节点都只被访问一次，遍历的顺序也是按照宽度优先的顺序。