欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[PHP]算法- 二叉树的深度的PHP实现

程序员文章站 2022-05-12 17:04:41
二叉树的深度: 输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。 思路: 1.非递归层序遍历 2.使用辅助队列,根结点先入队列 3. 循环判断队列是否为空,如果不为空就继续循环队列里面的每个结点 4. 循环队列时,当前当前结点出... ......
二叉树的深度:
输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

思路:
1.非递归层序遍历
2.使用辅助队列,根结点先入队列
3. 循环判断队列是否为空,如果不为空就继续循环队列里面的每个结点
4. 循环队列时,当前当前结点出队列,把该结点的左右孩子入队列

treedepth(tree)
    if !tree return 0
    array_push(queue,tree);
    depth=0
    while(!empty(queue)){
        ++depth
        for i=0;i<queue.size;i++
            node=array_pop(queue)
            array_push(queue,node->left);
            array_push(queue,node->right);
    return depth
<?php
class treenode{
    var $val;
    var $left = null;
    var $right = null;
    function __construct($val){
        $this->val = $val;
    }   
}
function treedepth($tree)
{
        if(!$tree) return 0;
        $queue=array();
        array_push($queue,$tree);//在数组最后添加元素
        $depth=0;
        while(!empty($queue)){
                $depth++;
                $size=count($queue);
    
                for($i=0;$i<$size;$i++){
                        $node=array_shift($queue);//非常重要 删除第一个元素
                        if($node->left){
                                array_push($queue,$node->left);
                        }   
                        if($node->right){
                                array_push($queue,$node->right);
                        }   
                }   
        }    
        return $depth;
}

$node1=new treenode(1);
$node2=new treenode(2);
$node3=new treenode(3);
$node4=new treenode(4);
$node5=new treenode(5);
$node6=new treenode(6);
$node7=new treenode(7);


$tree=$node1;
$node1->left=$node2;
$node1->right=$node3;
$node2->left=$node4;
$node2->right=$node5;
$node4->right=$node6;
$node3->left=$node7;

var_dump($tree);
$dep=treedepth($tree);
var_dump($dep);