如何创建一个二进制搜索树，其中包括从1到n的所有数字 [英] How to create a binary search tree that includes all numbers from 1 to n

问题描述

我正在尝试创建一个二进制搜索树，其中包括从1到n的所有数字。一个例子是从1到5，例如

Im trying to create a Binary search tree that includes all numbers from 1 to n. an example would be from 1 to 5 would be something like

root：3

root.left：2

root.left: 2

root.left.left = 1

root.left.left = 1

root.right = 4

root.right = 4

root.right.right = 5

root.right.right = 5

这棵树不是很平衡，但是我更喜欢一种能够产生平衡的方法。

This tree happens to be not very balanced, but I would prefer a method that produces as balanced of a tree as possible.

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

I am trying to create my own data structure for this, so I basically just wrote a Node class:

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

我计划将其放在另一个类中，该类代表树本身。我一直在寻找一种适当的方法来确定树的左/右值，希望对您有所帮助！

And I planned on having that inside another class, which represents the tree itself. I am stuck finding a good way determine the left/right values appropriately to build the tree, any help is appreciated!

推荐答案

根节点上的数据将为（n + 1）/ 2 ；如果您有一个表示范围 [i..j] 的子树，则该子树的根为（i + j）/ 2 （使用整数算法）。

The data on the root node would be (n+1)/2; if you've got a subtree representing the range [i..j], the root of that subtree is (i+j)/2 (using integer arithmetic).

您可以使用以下事实递归构建树：

You can build the tree recursively using that fact:

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）是没有用的：您也可以简单地使用数组，然后使用数组索引搜索它。

It must be pointed out, however, that such a binary search tree (storing contiguous integers from 1 to n) is useless: you may as well simply use an array, and "search" it using an array index.

这篇关于如何创建一个二进制搜索树，其中包括从1到n的所有数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！