java - 在二叉搜索树的数组实现上实现插入函数

问题描述

我正在尝试使用二叉搜索树的功能，而无需实际创建 Node 对象并赋予它们左/右子对象，而是在三个并行数组中使用二叉搜索树的基本思想：左、数据和右。在这些数组中的特定索引处，left 保存当前数据的左孩子所在的数据的索引，而 right 保存当前数据的右孩子所在的数据的索引。这张表提供了一个更好的例子来说明我在说什么：

-1 值表示节点没有左或右子节点的位置。在插入任何节点之前，所有数组的值都为0，每次插入一个节点时，它的左右子索引值都设置为-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 的数组，同时仍然能够指示节点在特定一侧没有子节点。

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

标签： javabinary-search-treeparallel-arrays

解决方案

关于您的代码的一些注释：

root变量不应该被赋值d，而是将被存储的索引，只有d这样，空树被编码root为 -1 才有意义（意识到这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 在使用类实例时提供的强大的堆内存管理。出于这个原因，我建议以 OOP 方式实现树。

java - 在二叉搜索树的数组实现上实现插入函数

问题描述

解决方案

推荐阅读