标签：Node queue top DFS BFS value child new PHP
广度有优先可以实现二叉树的层级遍历
- 优先将 根节点 加入队列
- 取出来一个节点进行处理
- 依次词节点的 子节点入队 没有就不放入
- 队列非空则 继续 重复取出一个节点加入子节点 知道结束
点击查看代码
class Node
{
public $value;
public $child_left;
public $child_right;
}
$a = new Node();
$b = new Node();
$c = new Node();
$d = new Node();
$e = new Node();
$f = new Node();
$g = new Node();
$h = new Node();
$i = new Node();
$a->value = '1';
$b->value = '2';
$c->value = '3';
$d->value = '4';
$e->value = '5';
$f->value = '6';
$g->value = '7';
$a->child_left = $b;
$a->child_right = $c;
// 2
// 4 5
$b->child_left = $d;
$b->child_right = $e;
// 3
// 6 7
$c->child_left = $f;
$c->child_right = $g;
function bfs($root)
{
$queue = [ $root];
while (count($queue)) {
for ($i = 0; $i < count($queue); $i++) {
$top = array_shift($queue);
echo $top->value, PHP_EOL;
if ($top->child_left) {
array_push($queue, $top->child_left);
}
if ($top->child_right) {
array_push($queue, $top->child_right);
}
}
}
}
深度优先使用栈 和广度优先一样
- 放入跟节点
- 拿出节点
- 放入子节点
- 栈非空 弹出节点 加入子节点
点击查看代码
function dfs($root)
{
$queue = [$root];
while (count($queue)) {
for ($i = 0; $i < count($queue); $i++) {
$top = array_pop($queue);
echo $top->value, PHP_EOL;
if ($top->child_left) {
array_push($queue, $top->child_left);
}
if ($top->child_right) {
array_push($queue, $top->child_right);
}
}
}
}
标签：Node,
queue,
top,
DFS,
BFS,
value,
child,
new,
PHP
From： https://www.cnblogs.com/guanchaoguo/p/16845135.html