在二进制搜索树的数组实现上实现插入函数

Question

我试图在不实际创建节点 objects 并为它们提供 left/right children 的情况下使用二叉搜索树的功能，而是使用二叉搜索树的基本思想在三个并行数组中：左、数据和右。在这些数组中的特定索引处，left 保存当前数据左侧 child 所在数据的索引，而 right 保存当前数据右侧 child 所在数据的索引。这个 table 给出了一个更好的例子来说明我在说什么：

-1 值表示节点没有左或右 child。在插入任何节点之前，所有数组的值都是0，每次插入一个节点时，其左右children索引值都设置为-1（表示我们刚刚插入的是叶子).我正在努力弄清楚的是如何递归地执行此操作而不会意外访问 -1 的索引。我目前在下面看到的尝试是运行进入这个问题：

public void insert(int d) {
//PRE: the tree is not full
//if d is not in the tree insert d otherwise the tree does not change
    if(root == -1) {
        root = d;
    }
    insert(d, 0);
}

private void insert(int d, int index) {
    if(data[index] == d) {
        return;
    }
    if(data[index] == 0) {
        data[index] = d;
        right[index] = -1;
        left[index] = -1;
    }
    if(data[index] > d) {
        if(left[index] == 0) {
            data[index] = d;
            right[index] = -1;
            left[index] = -1;
        } else {
            insert(d, left[index]);
        }
    }
    if(data[index] < d) {
        if(right[index] == 0) {
            data[index] = d;
            right[index] = -1;
            left[index] = -1;
        } else {
            insert(d, right[index]);
        }
    }
    return;
}

我很好奇如何防止访问索引值为 -1 的数组，同时仍然能够指示节点在特定一侧没有 child。

我理解的概念是每次插入一个节点时，我都是在插入一个叶子，所以当一个节点被放置在一个特定的索引处时，它的左右可以自动设置为-1，但是我当前的递归调用最终在某一时刻传入 -1。即使我将此值更改为 0 或其他值，也不一定能帮助我在递归中取得任何进展。

Answer 1

对您的代码的一些评论：

root变量不应该赋值d，而是index会存储d的地方，只有这样，用等于 -1 的 root 编码空树才有意义（意识到 d 可能是 -1）。
您的代码没有逻辑来确定在哪个索引处存储新节点。这真的是你的问题。一个简单的解决方案是维护一个 size 变量。这就是存储下一个节点的索引，之后 size 成员应该递增。
没有理由将 0 视为某种特殊指示符，您的代码应该只检查 -1 引用，而不是 0。
你有一些代码重复，你可以通过创建一个将“创建”节点的方法来避免：它将使用 size 作为它的索引，并将一个值作为参数.

这是建议的代码：

class BinaryTree {
    public static final int MAXSIZE = 100;
    int left[] = new int[BinaryTree.MAXSIZE]; 
    int right[] = new int[BinaryTree.MAXSIZE]; 
    int data[] = new int[BinaryTree.MAXSIZE]; 
    int root = -1;
    int size = 0;

    private int createNode(int value) {
        data[size] = value;
        left[size] = -1;
        right[size] = -1;
        return size++;
    }

    public void insert(int value) {
        if (root == -1) {
            root = createNode(value);
        } else {
            insert(value, 0);
        }
    }

    private void insert(int value, int index) {
        if (data[index] == value) {
            return;
        }
        if (data[index] > value) {
            if (left[index] == -1) {
                left[index] = createNode(value);
            } else {
                insert(value, left[index]);
            }
        } else {
            if (right[index] == -1) {
                right[index] = createNode(value);
            } else {
                insert(value, right[index]);
            }
        }
        return;
    }
}

此代码可以进一步扩展：

验证树已达到最大大小，
节点删除
重用已删除节点索引的“内存管理”（通过维护“空闲列表”）
自平衡（如 AVL 或红黑树）

自己进行“内存管理”（数组槽管理）真的会模仿 Java 在使用 class 实例时开箱即用的强大堆内存管理。出于这个原因，我建议以 OOP 方式实现树。

在二进制搜索树的数组实现上实现插入函数

Implementing an insert function onto array implementation of Binary Search Tree

java

binary-search-tree

parallel-arrays