0

我正在研究Project Euler 问题 18（我确实解决了问题；我没有作弊。“证明”在这里）并且发现自己需要一种方法来表示看起来像帕斯卡三角形但具有不同值的数据结构. 它看起来与二叉树非常相似，但有一个非常重要的区别：节点的子节点不只是它的子节点。所以前三行如下所示：

    75
   /  \
  95  64
 /  \ / \
17  47  82

请注意，47 有两个父母。

将其表示为链接结构甚至二维数组非常容易，但我希望有一种更优雅的方式。我喜欢二叉树，主要是因为你可以分配一块内存，将其视为一个数组，并通过几个算术运算或整数除法在子级和父级之间导航。有没有办法对这个数据结构做同样的事情？

我最好的解决方案是使用二维数组（很容易找到孩子和父母）。我不喜欢这种实现，因为（至少我这样做的方式）我要求malloc每一行，即使我提前知道结构会有多大。

我的问题与这个问题非常相似，但我对接受的答案不满意。评论暗示了我寻求的解决方案，但没有给出任何解释。

编辑：为了澄清，我正在寻找一种方法来索引一维数组，其方式与按顺序填充到数组中的二叉树（从 1 开始）给出索引i处节点的子节点的属性相同在索引 2 * i和 2 * i + 1 处。我也不太担心能否找到父母，所以不要太担心奇怪的两个父母。

4

2 回答 2

1

是的，可以将三角形数据结构存储在一维数组中（Java 中的示例）：

class Triangle<T> {
  private T[] triangle;

  public Triangle(T[] array, int rows) {
    if (array.length != triangleNumber(rows)) {
      throw new IllegalArgumentException("Array wrong size");
    }
    triangle = array;
  }

  public T get(int row, int col) {
    return triangle[index(row, col)];
  }

  public void set(int row, int col, T val) {
    triangle[index(row, col)] = val; 
  }

  private int triangleNumber(int rows) {
    return rows * (rows + 1) / 2;
  }

  private int index(int row, int col) {
    if (row < 0 || col < 0 || col > row) {
      throw new IndexOutOfBoundsException("Trying to access outside of triangle");
    }
    return triangleNumber(row) + col;
  }
}

传递给构造函数的数组是通过将三角形的行一个接一个地连接到数组中形成的：[t(0,0), t(1,0), t(1,1), t(2, 0), t(2,1), t(2,2), ... , t(rows-1, rows-1)]，其中 t(R, C) 是三角形行 R 和三角形的三角形单元格C 列。

对于任何单元格（行，列）：

  • 左孩子将在 row+1, col
  • 右孩子将在 row+1, col+1
  • 左父母将在第 1 行，第 1 列
  • 右父母将在第 1 行，col

并非所有单元格都存在两个父母和两个孩子，因为他们将位于三角形之外。请参阅 index 方法中的异常检查。

于 2015-09-29T18:43:10.297 回答
0

是的：我们从二维数组的想法开始，但行长不规则。所以每个元素都由二维索引（r，c）索引；(1,1) (2,1)(2,2) (3,1)(3,2)(3,3) (4,1)(4,2)(4,3)(4,4)

因为关系是规则的，你可以表达我们的位置：
对于一个节点 (r,c) 是子节点是 (r+1,min(1,c)),(r+1,max(c+1,r )) 和他的父母是： (r-1,min(1,c-1)),(r-1,max(c,r))

于 2012-11-05T14:40:59.437 回答