php多叉树实现及其遍历方法

网上php关于树的算法的文章貌似不多。看过一些文章之后，自己实现了一下，这里分享出来，共同学习。

一、构建节点类

class Node{

    private string $name;

    private int $id;

    /**
     * @var Node[]
     */
    private array $children=[];


    public function __construct(int $id,string $name)
    {
        $this->id=$id;
        $this->name=$name;
    }

    /**
     * @return string
     */
    public function getName(): string
    {
        return $this->name;
    }

    /**
     * @return int
     */
    public function getId(): int
    {
        return $this->id;
    }

    public function addChild(Node $node){
        $this->children[]=$node;
    }

    /**
     * @return Node[]
     */
    public function getChildren(): array
    {
        return $this->children;
    }
}

二、实现递归遍历

    /**
     * 递归遍历其下所有子节点
     */
    public function recursionTraverse():void {
        echo $this->getName();
        foreach ($this->getChildren() as $child){
            $child->recursionTraverse();
        }
    }

三、广度优先遍历

    /**
     * 非递归广度优先遍历其下所有子节点
     */
    public function breadthTraverse():void{
        $queue=new SplQueue;

        $queue->enqueue($this);

        while ($queue->count()){
            /**
             * @var Node $node
             */
            $node=$queue->dequeue();
            echo $node->getName();
            foreach ($node->getChildren() as $child){
                $queue->enqueue($child);
            }
        }
    }

四、深度优先遍历

    /**
     * 非递归深度优先遍历其下所有子节点
     */
    public function depthTraverse():void{
        $stack=new SplStack;
        $stack->unshift($this);

        while ($stack->count()){
            /**
             * @var Node $node
             */
            $node=$stack->shift();

            echo $node->getName();
            foreach (array_reverse($node->getChildren()) as $child){
                $stack->unshift($child);
            }
        }
    }

五、添加一些测试数据，构建树

// 测试数据
$example=[
    ['id'=>1,'parent_id'=>0,'name'=>'1'],
    ['id'=>2,'parent_id'=>1,'name'=>'2'],
    ['id'=>3,'parent_id'=>1,'name'=>'3'],
    ['id'=>4,'parent_id'=>2,'name'=>'4'],
    ['id'=>5,'parent_id'=>2,'name'=>'5'],
    ['id'=>6,'parent_id'=>2,'name'=>'6'],
    ['id'=>7,'parent_id'=>3,'name'=>'7'],
    ['id'=>8,'parent_id'=>3,'name'=>'8'],
];

// 构建树
function make_tree(array $treeData,Node $parentNode){
    foreach ($treeData as $treeDatum){
        if($treeDatum['parent_id']===$parentNode->getId()){
            $node=new Node($treeDatum['id'],$treeDatum['name']);
            make_tree($treeData,$node);
            $parentNode->addChild($node);
        }
    }
}

$root=new Node(0,'0');
make_tree($example,$root);

// 递归遍历
$root->recursionTraverse();
echo PHP_EOL;

// 广度优先遍历
$root->breadthTraverse();
echo PHP_EOL;

// 深度优先遍历
$root->depthTraverse();
echo PHP_EOL;