How to implement depth calculation of binary tree in PHP (with code)-PHP Tutorial-php.cn

How to implement depth calculation of binary tree in PHP (with code)

不言

Release： 2023-04-04 09:12:02

forward

3267 people have browsed it

The content of this article is about how PHP implements the depth calculation of binary trees (with code). It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

Depth of binary tree:
Enter a binary tree and find the depth of the tree. The nodes (including root and leaf nodes) passing through in sequence from the root node to the leaf nodes form a path of the tree. The length of the longest path is the depth of the tree.

Ideas:

1. Non-recursive layer order traversal
2. Use auxiliary queue, the root node enters the queue first
3. Loop to determine whether the queue is is empty. If it is not empty, continue to cycle through each node in the queue
4. When the queue is cycled, the current node is dequeued and the left and right children of the node are put into the queue

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

Copy after login

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

Copy after login

The above is the detailed content of How to implement depth calculation of binary tree in PHP (with code). For more information, please follow other related articles on the PHP Chinese website!