实现二叉树的层序插入：基于树大小的路径导航

      1
    /   \
   2     3
  /
 4

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

    public TreeNode(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }

    // 假设此处有其他辅助方法，如打印树结构
}

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

    public TreeNode(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }

    /**
     * 在二叉树中插入新节点，以维持层序、从左到右的结构。
     * 该方法通过树的大小计算插入路径，并以迭代方式实现。
     *
     * @param data 要插入的节点数据。
     * @param size 树中当前已有的节点数量。
     * @return 树的根节点（通常是当前调用的 TreeNode 实例）。
     */
    public TreeNode insert(int data, int size) {
        // 如果当前节点是根节点，则直接从this开始
        TreeNode current = this;

        // 计算新节点在逻辑上的索引（从1开始）
        // 假设树当前有size个节点，新节点将是第 size+1 个节点。
        // 我们需要找到第 size+1 个节点的父节点。
        // Integer.toBinaryString((size + 1) >> 1) 得到的是 (size+1) 除以2 的二进制表示。
        // 举例：size=4, size+1=5 (101)。 (size+1)>>1 = 2 (10)。
        // 这表示我们要找的路径是到第 (size+1) 个节点的前一位的路径。
        // .substring(1) 是为了去除最高位的 '1'。
        // 实际上，(size + 1) 的二进制表示，去掉最高位后，就是从根到目标节点父节点的路径。
        // 例如：size=4, size+1=5 (101)。路径 '01'。
        // 0 -> left, 1 -> right
        String pathBits = Integer.toBinaryString(size + 1).substring(1);

        // 遍历路径位，找到新节点的父节点
        for (char bit : pathBits.toCharArray()) {
            if (bit == '0') { // '0' 表示向左
                if (current.left == null) { // 理论上不会发生，因为路径是到父节点
                    // 这是为了防止空指针，但根据算法，到这里时current.left或right应该已经存在
                    // 除非树非常小，路径直接指向根的子节点
                    break;
                }
                current = current.left;
            } else { // '1' 表示向右
                if (current.right == null) { // 同上
                    break;
                }
                current = current.right;
            }
        }

        // 找到父节点后，根据路径的最后一个位（或者说根据当前父节点哪个子节点为空）插入新节点
        // 根据这种层序插入的规则，一个节点要么先填充左子节点，然后填充右子节点。
        // 所以，如果左子节点为空，就插入左侧；否则，插入右侧。
        if (current.left == null) {
            current.left = new TreeNode(data);
        } else {
            current.right = new TreeNode(data);
        }

        return this; // 返回根节点
    }
}

public class Main {
    public static void main(String[] args) {
        // 创建根节点，树的初始大小为1
        TreeNode root = new TreeNode(1);
        int size = 1; // 记录当前树的节点数量

        // 循环插入更多节点
        for (int i = 2; i <= 10; i++) { // 插入数据2到10
            root.insert(i, size); // 调用insert方法，并传入当前树的大小
            size++; // 每次插入后，树的大小增加
        }

        // 此时，树的结构将是近似完全二叉树，节点按层序从左到右填充
        // 示例打印（需要TreeNode类中实现一个打印方法）
        // printTree(root); // 假设有一个printTree方法
    }

    // 辅助方法：打印树结构（仅为示例，需要具体实现）
    // private static void printTree(TreeNode node) { /* ... */ }
}

│       ┌── 7
│   ┌── 3
│   │   └── 6
│   │        
└── 1
    │       
    │   ┌── 5
    │   │   └── 10
    └── 2   ┌── 9
        └── 4
            └── 8