So implementieren Sie die Tiefenberechnung des Binärbaums in PHP (mit Code)

Der Inhalt dieses Artikels befasst sich mit der Implementierung der Tiefenberechnung von Binärbäumen (mit Code). Ich hoffe, dass er für Sie hilfreich ist.

Tiefe des Binärbaums:
Geben Sie einen Binärbaum ein und ermitteln Sie die Tiefe des Baums. Die Knoten (einschließlich Wurzel- und Blattknoten), die nacheinander vom Wurzelknoten zu den Blattknoten verlaufen, bilden einen Pfad des Baums. Die Länge des längsten Pfads ist die Tiefe des Baums.

Ideen:

1. Nicht rekursive Ebenenreihenfolge-Durchquerung
2. Verwenden Sie eine Hilfswarteschlange, der Wurzelknoten wird zuerst in die Warteschlange gestellt
3 . Schleife, um festzustellen, ob die Warteschlange leer ist. Durchlaufen Sie jeden Knoten in der Warteschlange.
4. Beim Durchlaufen der Warteschlange wird der aktuelle Knoten aus der Warteschlange entfernt und die linken und rechten Kinder des Knotens werden in die Warteschlange gestellt

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

Das obige ist der detaillierte Inhalt vonSo implementieren Sie die Tiefenberechnung des Binärbaums in PHP (mit Code). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!