slince / tree-samples
树形结构遍历示例
0.0.1
2018-10-08 05:12 UTC
Requires (Dev)
- phpunit/phpunit: ^5.0|^6.0
This package is auto-updated.
Last update: 2024-10-09 03:13:13 UTC
README
包含深度优先算法与广度优先算法; 本示例采用的是非递归算法;借用 SplStack
和 SplQueue
实现两种算法的遍历。在开始讲算法之前,我们先创建一个二叉树节点类 Node
,源码:
class Node { /** * @var int */ protected $value; /** * @var Node */ protected $left; /** * @var Node */ protected $right; //... }
深度优先(DFS)
此算法我们使用的是 Stack
,栈的特性是先入后出,借此我们有了如下思路:
- 创建一个空的堆栈
SplStack
对象 - 将需要遍历的二叉树节点对象压入栈
$stack = new \SplStack(); $stack->push($node);
- 循环堆栈对象;
- 弹出栈内的第一个节点,此节点即完成遍历;
- 将当前访问的节点的右子节点和左子节点先后压入堆栈.
while (!$stack->isEmpty()) { $stack->top(); $node = $stack->pop(); $visitor($node); //此节点完成访问 //压右子树 if ($node->getRight()) { $stack->push($node->getRight()); } if ($node->getLeft()) { $stack->push($node->getLeft()); } }
- 循环下去,直到堆栈内节点完全弹出即可完成二叉树的遍历。
广度优先(BFS)
此算法我们使用的是 Queue
,队列的特性是先入先出,我们的思路如下:
- 创建一个空的堆栈
SplQueue
对象 - 将需要遍历的二叉树节点对象入队
$queue = new \SplQueue(); $queue->enqueue($node);
- 循环队列对象;
- 弹出对首的节点,此节点完成访问;
- 将当前访问的节点的左子节点和由子节点先后入队.
while (!$stack->isEmpty()) { $node = $queue->dequeue(); $visitor($node); //此节点完成访问 //压左子树 if ($node->getLeft()) { $queue->push($node->getLeft()); } if ($node->getRight()) { $queue->push($node->getRight()); } }
- 循环下去,直到队列内元素完全弹出。
Usage
Installation:
$ composer require slince/tree-samples
Basic Usage:
// 创建三个节点的二叉树 $leftChild = new Slince\Tree\Node(2); $rightChild = new Slince\Tree\Node(3); $node = new Slince\Tree\Node(1, $leftChild, $rightChild); // 使用宽度优先算法遍历 $bfs = new Slince\Tree\Traversal\BFS(); $numbers = []; $bfs->travel($node, function(Node $node) use(&$numbers){ $numbers[] = $node->getValue(); }); // 输出遍历顺序 echo implode(',', $numbers); // 1,2,3 // 使用深度优先算法遍历 $dfs = new Slince\Tree\Traversal\DFS(); $numbers = []; $bfs->travel($node, function(Node $node) use(&$numbers){ $numbers[] = $node->getValue(); }); // 对于三个节点的二叉树,dfs和bfs的遍历顺序是一样的,有兴趣的可以自行尝试7个节点的二叉树遍历。
LICENSE
MIT 协议;