slince/tree-samples

树形结构遍历示例

0.0.1 2018-10-08 05:12 UTC

This package is auto-updated.

Last update: 2020-10-08 17:53:48 UTC


README

Build Status Coverage Status Latest Stable Version Scrutinizer

包含深度优先算法与广度优先算法; 本示例采用的是非递归算法;借用 SplStackSplQueue 实现两种算法的遍历。在开始讲算法之前,我们先创建一个二叉树节点类 Node,源码

class Node
{
    /**
     * @var int
     */
    protected $value;

    /**
     * @var Node
     */
    protected $left;

    /**
     * @var Node
     */
    protected $right;
    
    //...
}

深度优先(DFS)

此算法我们使用的是 Stack,栈的特性是先入后出,借此我们有了如下思路:

  1. 创建一个空的堆栈 SplStack 对象
  2. 将需要遍历的二叉树节点对象压入栈
$stack = new \SplStack();
$stack->push($node);
  1. 循环堆栈对象;
  2. 弹出栈内的第一个节点,此节点即完成遍历;
  3. 将当前访问的节点的右子节点和左子节点先后压入堆栈.
while (!$stack->isEmpty()) {
    $stack->top();
    $node = $stack->pop();
    $visitor($node); //此节点完成访问

    //压右子树
    if ($node->getRight()) {
        $stack->push($node->getRight());
    }
    if ($node->getLeft()) {
        $stack->push($node->getLeft());
    }
}
  1. 循环下去,直到堆栈内节点完全弹出即可完成二叉树的遍历。

完整代码

广度优先(BFS)

此算法我们使用的是 Queue,队列的特性是先入先出,我们的思路如下:

  1. 创建一个空的堆栈 SplQueue 对象
  2. 将需要遍历的二叉树节点对象入队
$queue = new \SplQueue();
$queue->enqueue($node);
  1. 循环队列对象;
  2. 弹出对首的节点,此节点完成访问;
  3. 将当前访问的节点的左子节点和由子节点先后入队.
while (!$stack->isEmpty()) {
    $node = $queue->dequeue();
    $visitor($node); //此节点完成访问
    //压左子树
    if ($node->getLeft()) {
       $queue->push($node->getLeft());
    }
    if ($node->getRight()) {
       $queue->push($node->getRight());
    }
}
  1. 循环下去,直到队列内元素完全弹出。

完整代码

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 协议;