php - 查找二叉树级别是否已完成的最佳且有效的方法应该是什么？

Question

我正在业务模型中生成一个关联二叉树，其中每个成员最多可以有 2 个子成员。现在我需要知道树中的某个级别是否已完成。

function binarytree($id = 1, $link , $supermember = false, $float = "left", $level =1)
    {
        $level++;
        if($level>3)
        {
            return false;
        }
        $width = 100;
        $res_count = 1;
        if($supermember)
        {    
            $res_count = 2;     
        }
        $query = "Select * from binary_tbl where id = $id";
        $res = mysql_query($query, $link) or die(mysql_error());
        $div_witdh =  $width/$res_count;
        while($r = mysql_fetch_object($res))
        {
                echo "<div style='width:$div_witdh%;text-align:center;float:$float'>$r->name<br>";
                $query_member = "Select * from binary_tbl where supermember = $id";
                $res_member = mysql_query($query_member, $link) or die(mysql_error());
                while($rm = mysql_fetch_object($res_member))
                {
                            $this->binarytree($rm->id, $link, true, $float, $level);
                            $float = ($float=='left')?'right': 'left';
                }       
                echo "</div>";
        }
    }

我正在使用以下数据库关系来使用 php 代码生成二叉树..

CREATE TABLE `binary_tbl` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(10) DEFAULT NULL,
  `supermember` int(11) NOT NULL,
  `membercount` int(1) DEFAULT NULL,
   PRIMARY KEY (`id`)
 ) 

我需要通过运行一段代码(可以是 cron php 脚本)来知道每个级别是否已完成，这意味着任何给定级别的所有 parent 是否都忙得不可开交。看待这个问题最有效的方法是什么？

所需输出: bool 值表示每个级别是否完成。

Answer 1

我建议在一个单独的结构中跟踪每个级别上的节点数量，也可以是一个简单的数组。您在插入节点时已经知道节点的级别，因此在插入时更新特定计数的成本较低

$countAtLevel[$level]++

在此之后，确定一个级别是否完成就很简单，第 n 个级别始终包含 2^n 个值。