首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

如何编写在二叉树(java)中按级别顺序(从左到右)插入节点的方法?

在Java中,可以使用队列来实现按级别顺序(从左到右)插入节点的方法。具体步骤如下:

  1. 首先,定义一个二叉树节点类,包含节点值和左右子节点的引用。
代码语言:txt
复制
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}
  1. 创建一个队列,用于存储待插入节点的父节点。
代码语言:txt
复制
Queue<TreeNode> queue = new LinkedList<>();
  1. 如果二叉树为空,直接将新节点作为根节点。
代码语言:txt
复制
if (root == null) {
    root = new TreeNode(val);
    return root;
}
  1. 将根节点加入队列。
代码语言:txt
复制
queue.offer(root);
  1. 使用循环遍历队列,直到队列为空。
代码语言:txt
复制
while (!queue.isEmpty()) {
    TreeNode parent = queue.poll();

    // 尝试插入左子节点
    if (parent.left == null) {
        parent.left = new TreeNode(val);
        return root;
    } else {
        queue.offer(parent.left);
    }

    // 尝试插入右子节点
    if (parent.right == null) {
        parent.right = new TreeNode(val);
        return root;
    } else {
        queue.offer(parent.right);
    }
}

完整的代码如下:

代码语言:txt
复制
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class BinaryTreeInsertion {
    public static TreeNode insertLevelOrder(TreeNode root, int val) {
        Queue<TreeNode> queue = new LinkedList<>();

        if (root == null) {
            root = new TreeNode(val);
            return root;
        }

        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode parent = queue.poll();

            // 尝试插入左子节点
            if (parent.left == null) {
                parent.left = new TreeNode(val);
                return root;
            } else {
                queue.offer(parent.left);
            }

            // 尝试插入右子节点
            if (parent.right == null) {
                parent.right = new TreeNode(val);
                return root;
            } else {
                queue.offer(parent.right);
            }
        }

        return root;
    }

    public static void main(String[] args) {
        TreeNode root = null;
        root = insertLevelOrder(root, 1);
        root = insertLevelOrder(root, 2);
        root = insertLevelOrder(root, 3);
        root = insertLevelOrder(root, 4);
        root = insertLevelOrder(root, 5);
    }
}

这个方法可以确保按级别顺序(从左到右)插入节点,即先从根节点开始,逐层遍历二叉树,找到第一个空闲位置插入新节点。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

没有搜到相关的合辑

领券