<?php
/*
构造如下一棵树:
a
/ | \
b c d
/ \ |
e f g
|
h
深度优先遍历(DFT):
a
b
e f
h
c d
g
广度优先遍历(BFT):
a
b c d
e f
g
h
*/
$h = new TreeNode('h');
$g = new TreeNode('g');
$f = new TreeNode('f', [$h]);
$e = new TreeNode('e');
$d = new TreeNode('d', [$g]);
$c = new TreeNode('c');
$b = new TreeNode('b', [$e, $f]);
$a = new TreeNode('a', [$b, $c, $d]);
$tree = &$a;
dft($tree);
echo "\n----\n";
bft($tree);
exit();
class TreeNode {
public $data;
public $children = [];
public function __construct($data, $children = []) {
$this->data = $data;
$this->children = array_merge($this->children, $children);
}
}
/**
* depth first traversal
*
* 借助栈实现
*/
function dft($tree) {
$stack = array($tree, "\n");
while (!empty($stack)) {
$node = array_pop($stack);
if (is_string($node)) {
echo $node;
} else {
echo $node->data;
if ($node->children) {
array_push($stack, "\n");
$children = array_reverse($node->children);
foreach ($children as $c) {
array_push($stack, "\t");
array_push($stack, $c);
}
array_push($stack, "\n");
}
}
}
}
/**
* breadth first traversal
*
* 借助队列实现
*/
function bft($tree) {
$queue = array($tree, "\n");
while(!empty($queue)) {
$node = array_shift($queue);
if (is_string($node)) {
echo $node;
} else {
echo $node->data;
if ($node->children) {
foreach ($node->children as $c) {
array_push($queue, $c);
array_push($queue, "\t");
}
array_push($queue, "\n");
}
}
}
}