在数组列表中存储二叉搜索树

Question

我正在尝试使用包含 n 个元素的二叉搜索树并将它们存储在数组列表中。当前，它们存储在数组列表中的位置基于，树的根是元素 1，（p = 它们 parent 在数组中的索引）左边的 child 将位于索引 p *2，右边的 child 将在索引 p*2+1.

目前我尝试使用以下代码来做到这一点：

public static void arraywriter(TreeNode<String> node) throws FileNotFoundException
{
    int pos = 1;
    outputform.set(pos, node.getElement());
    pos = pos*2;
    if(node.getLeft() != null) {
        arraywriter(node.getLeft());
    }
    pos = pos+1;
    if(node.getRight() != null) {
        arraywriter(node.getRight());
    }
}

我的逻辑有什么问题？我将如何进行这项工作？目前，如果我使用它，然后尝试打印出 outputform 的内容（这是 arraylist 的名称，它的基本大小为 10,000），我得到：索引 1 返回为 null，其余为 "n"这也是我初始化每个元素的方式。

谢谢！

Answer 1

你的pos一直都是固定值1，也就是说你一遍又一遍地覆盖它。

考虑使用与此类似的东西：

public static void arraywriter(TreeNode<String> node, int pos) throws FileNotFoundException
{
    outputform.set(pos, node.getElement());
    pos = pos*2;
    if(node.getLeft() != null) {
        arraywriter(node.getLeft(), pos);
    }
    pos = pos+1;
    if(node.getRight() != null) {
        arraywriter(node.getRight(), pos);
    }
}

在数组列表中存储二叉搜索树

Storing a binary search tree in an arraylist

java

arraylist

binary-search-tree