二叉树广度遍历
2018-06-10 15:44:56 小德 算法 访问次数 763

     输入一颗二叉树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。 

例如输入

   8
  /   \
 6   10
/  \    /  \
5 7  9  11    

    

输出8 6 10 5 7 9 11

思路: 每一层的值从左往右,依次放置一个数组中,然后foreach遍历输出。

<?php
class Node{
    public $value = '';
    public $left,$right;
    public function __construct($value)
    {
        $this->value = $value;
    }
    public function setChildren($left,$right)
    {
        $this->left = $left;
        $this->right = $right;
    }
    public function getValue()
    {
        return $this->value;
    }

    public function getLeft()
    {
        return $this->left;
    }

     public function getRight()
    {
        return $this->right;
    }

}

$A = new Node(8);
$B = new Node(6);
$C = new Node(10);
$D = new Node(5);
$E = new Node(7);
$F = new Node(9);
$G = new Node(11);
$A->setChildren($B,$C);
$B->setChildren($D,$E);
$C->setChildren($F,$G);
$list = [$A];
while (!empty($list)){ 
    $newNodeS = [];  //初始化为空 避免为空
    foreach ($list as $Node) {
        echo $Node->getValue().' ';
        if(!empty($Node->getLeft())) {
            $newNodeS[] = $Node->getLeft();
        }
        if(!empty($Node->getRight())) {
            $newNodeS[] = $Node->getRight();
        }       
    }
    $list = $newNodeS;

}

exit;