Общий обход дерева (бесконечный) в режиме поиска в ширину

У меня есть структура дерева, где каждый узел имеет 5 дочерних узлов и больше, чем это недопустимо. Я хочу пересечь это дерево с помощью метода поиска по ширине.

Теперь я хочу рассчитать пустой узел из выбранного родителя, используя метод поиска по ширине.

• создать массив из списка массивов
• Лучшая древовидная структура php / Mysql
• Преобразование плоского массива в дерево с однократным циклом
• Меню дерева PHP / MySQL
• Строка PHP для вложенного / многомерного массива
• Маршрутизация регулярных выражений для Zend Framework 2

например

1. если заданный родительский 1, то функция должна возвращать узел 4, потому что у него есть доступные позиции.
2. Если заданный родительский элемент равен 2, он должен вернуть узел 7

Для этого я использую PHP (codeigniter) + Mysql.

Мой контролер

public function addmember() { $current_node = $this->input->post('member'); $empty_location = $this->tree_model->GetEmptyPositions($current_node); if($empty_location != 0) { echo "Position available"; } else { $next_nodes = $this->tree_model->GetAllChilds($current_node); $i=0; for($i=0;$i<5;$i++){ $result = $this->tree_model->GetEmptyPositions($next_nodes[$i]); if($result != 0 ) { $current_node = $next_nodes[$i]; goto exe; } } } exe: echo $current_node; } 

и моя модель

 //get number of empty nodes of current member public function GetEmptyPositions($id) { $this->db->select('empty_position'); $this->db->from('member'); $this->db->where('member_id',$id); $result = $this->db->get(); if ($result->num_rows() > 0) foreach($result->result() as $empty_pos) return $empty_pos->empty_position; } //get all childs of current node public function GetAllChilds($id) { $this->db->select('member_id'); $this->db->from('member'); $this->db->where('tree_parent_id',$id); $result = $this->db->get(); if ($result->num_rows() > 0) { $i = 0; foreach($result->result_array() as $member_id) { $member_array[$i] = $member_id['member_id']; $i++; } return $member_array; } } 

База данных

 CREATE TABLE IF NOT EXISTS `member` ( `member_id` int(11) NOT NULL AUTO_INCREMENT, `datetime` datetime DEFAULT NULL, `parent_id` int(11) DEFAULT NULL, `tree_parent_id` int(11) DEFAULT NULL, `empty_position` tinyint(4) DEFAULT '5', // stores how many empty positions remain if zero move to next node `name` varchar(20) COLLATE utf8_unicode_ci DEFAULT NULL, PRIMARY KEY (`member_id`) ) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci; 

Где я застрял!

Я могу пройти до узла 6 выше кода. но в следующей итерации мне нужно проверить @ узел 7, так как узлы будут иметь порядок 5 до n и это не конечная древовидная структура.

следующий порядок обхода дерева 7 8 9 10 11 12 13 14 16 ……

Solutions Collecting From Web of "Общий обход дерева (бесконечный) в режиме поиска в ширину"

 1 + 5 + (3-1)*5 + 1 1 + 5 + (3-1)*5 + 2 1 + 5 + (3-1)*5 + 3 1 + 5 + (3-1)*5 + 4 1 + 5 + (3-1)*5 + 5 

  col / 5 = 1 

  col / 25 = 1 

 getFreeNode($node){ $rowMax = 100; $row = $node->row + 1; $from = 5 * $node->col; $to = $from + 5; while($row <= $rowMax){ if ($id = query("select id from member " ."where row = $row and col >= $from and col < $bis" ." and empty_position > 0")) { return $id; } $row++; $from *= 5; $to *= 5; } } insertNode($parent, $node){ $node->row = $parent->row + 1; $node->col = 5*$parent->col + (5 - $parent->freeNodeCount); $node->parent_id = $parent->member_id }