Online PHP editor | rfc for fg7g9

<?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"); } } } }

3v4l.org

Active branches

Archived branches