常规二叉树插入异常排查：仅插入6的问题分析

问题描述 #

执行插入操作tree.insert(1); tree.insert(15); tree.insert(7); tree.insert(13); tree.insert(58); tree.insert(6);时，仅有6被插入到树中。

核心问题分析 #

你的insert方法存在两处致命逻辑错误，导致前面的插入全部被覆盖：

1. 每次插入都会强制重置根节点
   递归方法中，只要遇到x == null的情况，就直接把root赋值为新创建的节点。第一次插入1时，root为空，正常设置为1的节点；第二次插入15时，递归到root的左孩子（此时为null），又把root重置为15的节点；后续每次插入都会重复这个操作，最后一次插入6时，root被替换为6的节点，前面所有插入的节点全部丢失。

2. 从未给节点的左右孩子赋值
   递归过程中只是不断调用insert(x.left_child, k)或insert(x.right_child, k)，但从来没有将新节点赋值给当前节点的left_child或right_child。也就是说，除了root被反复替换，其他节点的左右孩子始终是null，递归一直在空节点中循环，每次都触发root重置。

修复方案 #

方案一：实现普通二叉树的层次插入（按顺序填充左右节点） #

用层次遍历的方式找到第一个空的位置插入：

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree {
    private Node root;

    public BinaryTree() {
        root = null;
    }

    public boolean is_empty() {
        return (root == null);
    }

    public void insert(int k) {
        Node newNode = new Node(k);
        if (root == null) {
            root = newNode;
            return;
        }
        // 队列实现层次遍历，找到第一个空的左右节点
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node current = queue.poll();
            if (current.left_child == null) {
                current.left_child = newNode;
                return;
            } else {
                queue.add(current.left_child);
            }
            if (current.right_child == null) {
                current.right_child = newNode;
                return;
            } else {
                queue.add(current.right_child);
            }
        }
    }

    // 修正后的打印方法（移除多余双引号）
    public void print_inorder() {
        print_inorder(root);
    }

    public void print_inorder(Node node) {
        if (node == null) {
            return;
        }
        print_inorder(node.left_child);
        System.out.print(node.key + " ");
        print_inorder(node.right_child);
    }

    // 其余打印方法同理修正双引号问题
    public void print_preorder() {
        print_preorder(root);
    }

    public void print_preorder(Node node) {
        if (node == null) {
            return;
        }
        System.out.print(node.key + " ");
        print_preorder(node.left_child);
        print_preorder(node.right_child);
    }

    public void print_postorder() {
        print_postorder(root);
    }

    public void print_postorder(Node node) {
        if (node == null) {
            return;
        }
        print_postorder(node.left_child);
        print_postorder(node.right_child);
        System.out.print(node.key + " ");
    }
}

方案二：实现二叉搜索树的插入（左小右大规则） #

如果是要实现二叉搜索树，按数值大小规则插入：

public class BinaryTree {
    private Node root;

    public BinaryTree() {
        root = null;
    }

    public boolean is_empty() {
        return (root == null);
    }

    public void insert(int k) {
        root = insert(root, k);
    }

    private Node insert(Node x, int k) {
        if (x == null) {
            return new Node(k);
        }
        // 左子树存比当前节点小的值
        if (k < x.key) {
            x.left_child = insert(x.left_child, k);
        } 
        // 右子树存比当前节点大的值
        else if (k > x.key) {
            x.right_child = insert(x.right_child, k);
        }
        // 相等值可选择不插入或自行处理
        return x;
    }

    // 同样修正打印方法的双引号问题
    public void print_inorder() {
        print_inorder(root);
    }

    public void print_inorder(Node node) {
        if (node == null) {
            return;
        }
        print_inorder(node.left_child);
        System.out.print(node.key + " ");
        print_inorder(node.right_child);
    }

    // 其余打印方法同理修正
}

额外提示 #

你的打印方法中存在语法错误：System.out.print(node.key + "\ "");多了一个双引号，需改成System.out.print(node.key + " ");才能正常编译运行。

内容的提问来源于stack exchange，提问作者Tareq El-Sayyed