0

这是我的数据结构类的作业，它是用 Java 编写的。

我必须制作这个小游戏之类的东西；这个世界是由一个图组成的，一些节点持有的项目，当找到时，将被添加到用户的库存中，这是一个二叉搜索树。（它必须是一个二叉搜索树，否则这会容易得多。）我已经弄清楚了大部分，但我需要用户能够查看和访问库存树的内容。我提供的二叉树节点类有一个inorderPrint()使用递归打印所有内容的方法，但这仅有助于向它们显示内容，而不是为它们提供访问它们的简单方法。我想要一个返回二进制搜索树节点数组的方法，这样我就可以在主...

int i = 0;
int choice;
System.out.println("# - Item\tPoints"); //Will appear as # - Item     Points
for (BTNode node : inventory.treeAsArray()) {
    System.out.printf("%d - %s\t%d\n", i, node.getData().getName(),
                      node.getData().getPoints()); //example: 1 - Poo    100
    i++;
}

System.out.println("Select the number of the item you want to remove: ");
choice = keyboard.nextInt();

然后我会再次遍历数组并删除与用户输入的数字相对应的项目。不过，我不知道如何编写一个以数组形式返回二叉搜索树内容的方法。这是我的主要问题。在我的教科书中我真的找不到它的算法。

4

2 回答 2

1

如果我要这样做，我可能只是按顺序将一个数组传递给所有节点。

public ArrayList<BTNode> treeAsArray() {
    ArrayList<BTNode> list = new ArrayList<BTNode>();
    root.buildListInorder(list);
    return list;
}

然后有

private void buildListInorder(ArrayList<BTNode> list) {
    buildListInorder(this.left);
    list.add(this);
    buildListInorder(this.right);
}

您需要添加适当的检查，但这是所需代码的基本大纲。

于 2012-05-06T06:38:20.410 回答
0 
public List<BTNode> treeAsArray() {
     return treeAsArray(this.root, new ArrayList<BTNode>());
}

private List<BTNode> treeAsArray(BTNode root, List<BTNode> array) {
     if (root == null)
         return array;

     treeAsArray(root->getLeftNode(), array);
     array.add(root);
     treeAsArray(root->getRightNode(), array);

     return array;
}
于 2012-05-06T06:39:55.650 回答