Comment implémenter le calcul de profondeur des arbres binaires en PHP (avec code)

Le contenu de cet article explique comment implémenter le calcul de profondeur des arbres binaires en PHP (avec du code). Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

Profondeur de l'arbre binaire :
Entrez un arbre binaire et trouvez la profondeur de l'arbre. Les nœuds (y compris les nœuds racine et feuille) passant en séquence du nœud racine aux nœuds feuille forment un chemin de l'arbre. La longueur du chemin le plus long est la profondeur de l'arbre.

Idées :

1. Parcours d'ordre de niveau non récursif
2. Utilisez la file d'attente auxiliaire, le nœud racine est mis en premier dans la file d'attente
3. . Boucle pour déterminer si la file d'attente est vide. Si elle n'est pas vide, continuez à parcourir chaque nœud de la file d'attente
4 Lors de la boucle de la file d'attente, le nœud actuel est retiré de la file d'attente et les enfants gauche et droit du nœud. sont mis dans la file d'attente

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);

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!