什麼應該是最好和有效的方式來查找二進制樹級別是否已完成？

我在業務模型中生成關聯的二叉樹，其中每個成員最多可以有2個子成員。現在我需要知道樹中的某個級別是否已完成。 enter image description here 什麼應該是最好和有效的方式來查找二進制樹級別是否已完成？

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腳本），意味着任何給定級別的所有父母是否都有自己的雙手。什麼應該是最有效的方法來看待這個問題？

期望的輸出：布爾值表示每個級別是否完成。

來源

2014-02-09 Smoking Sheriff

遞歸通過樹，找到終端節點，看看孩子究竟有多少。 0個孩子=完成，2個孩子=完成，1個孩子=不完整。 –

我建議在獨立的結構跟蹤節點數量的各個層面上，很可能會成爲一個簡單的數組。你已經知道了某個節點的水平插入它時，因此在插入時更新的具體數量是廉價

$countAtLevel[$level]++

在此之後，確定的水平是完全簡單，N級總是包含2^n值。

來源

2014-02-09 22:15:44 Warlord

什麼應該是最好和有效的方式來查找二進制樹級別是否已完成？

回答

相關問題