java - 如何创建包含从 1 到 n 的所有数字的二叉搜索树

Question

我正在尝试创建一个包含从 1 到 n 的所有数字的二叉搜索树。一个例子是从 1 到 5 是这样的

根:3

根.左:2

根.左.左 = 1

root.right = 4

root.right.right = 5

这棵树恰好不是很平衡，但我更喜欢一种生成尽可能平衡的树的方法。

我正在尝试为此创建自己的数据结构，所以我基本上只是编写了一个 Node 类:

    private class BinaryNode{
        int data;
        BinaryNode left;
        BinaryNode right;
        BinaryNode parent;
    }

我计划将它放在另一个代表树本身的类中。我一直在寻找一种正确确定左/右值以构建树的好方法，感谢任何帮助!

Answer 1

根节点上的数据将是(n+1)/2；如果你有一个子树表示 [i..j] 范围，则该子树的根是 (i+j)/2(使用整数运算)。

您可以使用该事实递归地构建树:

static BinaryNode build(int i, int j) {
    if (i > j) return null;

    int mid = (i + j) / 2;  // Assumes i >= 0.

    BinaryNode node = new BinaryNode();
    node.data = mid;

    node.left = build(i, mid - 1);
    if (node.left != null) node.left.parent = node;

    node.right = build(mid + 1, j);
    if (node.right != null) node.right.parent = node;

    return node;
}

然后开始递归调用:

BinaryNode node = build(1, n);

但是必须指出，这样的二叉搜索树(存储从 1 到 n 的连续整数)是无用的:您还不如简单地使用数组，并使用数组索引“搜索”它。