3

我编写了以下代码来逐行打印二叉树。这个想法是使用 2 个队列并在它们之间交替。我正在使用 $tmp 变量交换 2 个队列。我认为这不是有效的，因为我正在复制数组。有没有更好的方法在不涉及复制的 php 中执行此操作？谢谢。

Btree：http ://www.phpkode.com/source/s/binary-tree/binary-tree/btree.class.php

// use 2 queues to get nodes level by level

$currentQueue = array();
$otherQueue = array();

if (!empty($Root)) {
    array_push($currentQueue, array($Root->getData(), $Root->getLeft(), $Root->getRight()));
}

$level = 0;
while (!empty($currentQueue)) {

echo "Level " . $level . ": ";
// print and pop all values from current queue while pushing children onto the other queue
$row = array();
while ($node = array_shift($currentQueue)) {
    $row[] = $node[0];
    $left = $node[1];
    $right = $node[2];
    if (!empty($left)) {
        $data = $left->getData();
        $l = $left->getLeft();
        $r = $left->getRight();
        array_push($otherQueue, array($data, $l, $r));
    }
    if (!empty($right)) {
        $data = $right->getData();
        $l = $right->getLeft();
        $r = $right->getRight();
        array_push($otherQueue, array($data, $l, $r));
    }
}

echo implode(' ,', $row);

echo "<br>";
// swap stacks
$tmp = $currentQueue;
$currentQueue = $otherQueue;
$otherQueue = $tmp;
$level++;
}
4

1 回答 1

1

如果您只想避免数组复制，您可以：

$tmp = & $currentQueue;
$currentQueue = & $otherQueue;
$otherQueue = & $tmp;

但是，如果您真的想优化此代码，我建议您从Knuth或Cormen 等人那里找到一个广度优先搜索算法并在 PHP 中实现它（或找到一个现有的实现）。

还要确保您确实需要优化此代码。

于 2013-04-01T05:42:16.990 回答