将堆输出为树 PHP

Question

我有一个数组$heap = array(9, 9, 9, 8, 9, 9, 8, 9, 9, 9, 9, 9, 8, 8, 9, 7, 9, 8, 8, 9, 9,);，我想像二叉树一样输出它，当我们可以通过这个公式知道两个子节点时，$heap[$key*2+1]和第二个$heap[$key*2+2]。我尝试运行使用 foreach 但收到有关未定义偏移量 21 的错误。这是 foreach：

foreach ($heap as $key => $value) {
    echo $value;
    if ($key != count($heap)) {
        echo $heap[$key*2+1];
        echo $heap[$key*2+2];
    }
}

我哪里做错了，我该如何解决？

Answer 1

我认为你的检查有误：

if ($key != count($heap)) {
    echo $heap[$key*2+1];
    echo $heap[$key*2+2];
}

这里可能是$key*2+2数组越界的情况。也为它添加支票。尝试使用 bool array_key_exists ( mixed $key , array $array )，像这样：

if ($key != count($heap)) {
    if (array_key_exists($key*2 + 1, $heap)) echo $heap[$key*2 + 1];
    if (array_key_exists($key*2 + 2, $heap) ) echo $heap[$key*2 + 2];
}

正如您在评论中指出的那样，您正在将代码中的值加倍。这可以通过递归函数来避免，像这样（伪代码）：

printArray(i, aHeap) {
    if (i < count($heap)) {
        echo $heap[i];
        printArray(2*i + 1, aHeap);
        printArray(2*i + 2, aHeap);
    }
}

Answer 2

它只是一个停止它的通知，只是通过检查数组键是否存在来定义偏移量。使用下面的代码

foreach ($heap as $key => $value) {
    echo $value;
    if ($key != count($heap)) {
         if (array_key_exists($key*2 + 1, $heap)){ echo $heap[$key*2 + 1];}
    if (array_key_exists($key*2 + 2, $heap) ){ echo $heap[$key*2 + 2]; }
    }
}

希望对您有所帮助

Answer 3

实际上，您可以在不使用 for:

检查密钥是否存在的情况下执行此操作

for($i = 0, $m = count($heap) - 1; $i < $m - 2; $i++) {
    echo $heap[$i+1];
    echo $heap[$i+2];
}

这将确保密钥只进入所有索引 - 2，因此在最后一次迭代中 $i + 2 将是最后一个密钥。

将堆输出为树 PHP

Output heap as tree PHP

php

binary-tree

binary-heap

data-structures