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

Question

我试图使用二元搜索树的功能，而不是实际创建节点对象并给它们左/右子对象，而是在三个平行数组中使用二元搜索树的基本思想：左、数据和右。在这些数组中的特定索引处，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或其他值，这也不一定能帮助我在递归中取得任何进展

Answer 1

关于代码的一些评论：

• 不应该为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在使用类实例时提供的现成的强大堆内存管理。因此，我建议用面向对象的方式实现一个树