三角形存储为数组。每个级别的高度和长度？

Question

假设我们有一个三角形，每个节点都有K个子节点。

K=2的一个例子是：

  1
 2 3
4 5 6

K=3的一个例子是：

    1
  2 3 4
5 6 7 8 9

K=4的一个例子是：

        1
     2 3 4 5
  5 6 7 8 9 1 2

等。

1. 我想把这些三角形存储在一个数组中。我希望检索三角形的总高度(假设它们是完整的三角形)，给定元素T的总数和每个节点K的子节点数。
2. 我还希望找到数组中的每个元素对每个子元素的偏移量。我知道，在上面的例子中，数组K= 2，数组为1，2，3，4，5，6，其中每级L的偏移量为L* (L + 1) /2(因为级别1有1元素，2级有2，3级有3…)

编辑:这个例子是正确的。每个节点都可以访问K个子节点。对于K=3，1可以访问2，3和4.2，可以访问5，6，7.3可以访问6，7和8。

这些都是三角形，而不是图形或树。

Answer 1

既然你已经澄清了你的要求..。

对于K=2，有

1
1+1
1+1+1
...

元素，这是系列1,2,3,....，如果n是级别号，那么每个级别上都有n元素。注意，这也可以写成1+1(n-1)

对于K=3，有

1
1+2
1+2+2
...

元素在每个级别，这是系列1,3,5,...；在每个级别上都有1+2(n-1)元素。

对于K=4，有

1
1+3
1+3+3
...

元素在每个级别上，这是系列1,4,7,...。每个级别都有1+3(n-1)元素。

在每个三角形的每个层次上都有1+(K-1)(n-1)元素。我希望你能继续下去。

Answer 2

高度为T的三角形h的元素总数为：

T=∑1.h (1 + (K-1)(n-1))

T=h+ (K-1) *∑1.h (n-1)

T=h+ (K-1) *∑0.h-1 (n)

T=h+ (K-1) *(( h-1) 2+h-1)/2

T=h+ (K-1) *(h 2+1-2h+ h-1) /2

T=h+ (K-1) *(h 2-h)/2

计算高度

因此，要得到高度h，插入K的值并求解方程。下面是一个简单的例子，其中K等于3。

T=h+ (K-1) *(h 2-h)/2

T=h+ (3-1) *(h 2- h) /2

T=h+(h 2- h)

T=h

H=√T

计算偏移量

对于偏移量，您使用相同的公式来计算元素的总数，但是将h设置为高度-1。下面是一个获得K为4的三角形中第3行的偏移量的示例。

偏移量(H)= h-1 + (K-1) *((h-1)2- (h-1)) /2

偏移量(3)= 3-1 + (4-1) *((3-1)

偏移量(3)=2+3*(4-2)/2

偏移(3)=5