如何实现二叉树的左到右平衡插入

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

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

      1
    /   \
   2     3
  /
 4

          1
(left)  /   \
       2     3
      / \ (right)
     4   5

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

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

    // toString for visualization (optional, but helpful for debugging)
    @Override
    public String toString() {
        return String.valueOf(data);
    }
}

public class BinaryTree {

    // 假设 TreeNode 类已定义如上

    /**
     * 实现二叉树的左到右平衡插入。
     * 该方法基于树的当前大小，利用二进制路径导航到正确的插入位置。
     *
     * @param data 要插入的节点数据。
     * @param size 树中当前节点的总数。
     * @return 树的根节点（通常是调用此方法的对象本身）。
     */
    public TreeNode insert(int data, int size) {
        // 'this' 指向当前树的根节点
        TreeNode currentRoot = this; 

        // 计算 (size + 1) 的二进制表示，并跳过最高位
        // (size + 1) >> 1 等同于 (size + 1) / 2，用于去除最低位，但这里是为了逻辑上匹配
        // 实际上，Integer.toBinaryString((size + 1)) 得到的是完整的二进制串
        // 然后 substring(1) 才是跳过最高位
        String bits = Integer.toBinaryString(size + 1).substring(1); 

        // 遍历二进制路径，导航到插入点前的父节点
        for (char bit : bits.toCharArray()) {
            if (bit == '1') {
                // '1' 表示向右子节点移动
                if (currentRoot.right == null) { // 如果路径中途遇到空，说明是错误或树不完整
                    // 实际情况下，此逻辑应确保不会在路径中途创建节点，
                    // 而是到达叶子节点处进行插入。
                    // 对于完全二叉树的构建，只有在最后一个bit才真正插入。
                    // 这里的检查是预防性的，确保路径有效。
                }
                currentRoot = currentRoot.right;
            } else {
                // '0' 表示向左子节点移动
                if (currentRoot.left == null) {
                    // 同上
                }
                currentRoot = currentRoot.left;
            }
        }

        // 到达目标父节点后，根据最后一个路径位（即 (size+1) 的最低位）决定插入左子或右子
        // 实际上，(size + 1) % 2 == 0 表示它是偶数，对应左子节点 (2, 4, 6...)
        // (size + 1) % 2 == 1 表示它是奇数，对应右子节点 (3, 5, 7...)
        // 更准确地说，如果 (size + 1) 是偶数，则新节点是其父节点的左子；如果是奇数，则是右子。
        // 这与二进制路径的最后一位有关。
        if ((size + 1) % 2 == 0) { // 如果下一个节点编号是偶数，它将是其父节点的左子
            currentRoot.left = new TreeNode(data);
        } else { // 如果下一个节点编号是奇数，它将是其父节点的右子
            currentRoot.right = new TreeNode(data);
        }

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

public class Main {
    public static void main(String[] args) {
        // 创建根节点
        TreeNode root = new TreeNode(1);
        int size = 1; // 树中当前节点数量

        // 插入更多节点
        for (int i = 2; i <= 10; i++) {
            root.insert(i, size++); // 每次插入后，size递增
        }

        // 打印树结构（需要一个树的打印函数，这里仅示意）
        // 例如：printTree(root);
        // 理想的输出结构将是：
        //         1
        //       /   \
        //      2     3
        //     / \   / \
        //    4   5 6   7
        //   / \
        //  8   9
        // /
        // 10
    }
}

        1
      /   \
     2     3
    / \   / \
   4   5 6   7
  / \
 8   9
/
10