php - General tree traversal(infinite) in breadth-first search manner -
i have tree structure each node has 5 child nodes , more not allowed. wish traverse tree in breadth-first search manner.
now wish calculate empty node selected parent using breadth-first search manner.
e.g.
- if given parent 1, function must return node 4 because has positions available.
- if given parent 2, must return node 7
i using php(codeigniter) + mysql this.
my controler
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; } and model
//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() $empty_pos) return $empty_pos->empty_position; } //get 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() $member_id) { $member_array[$i] = $member_id['member_id']; $i++; } return $member_array; } } database
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 0 move next node `name` varchar(20) collate utf8_unicode_ci default null, primary key (`member_id`) ) engine=innodb default charset=utf8 collate=utf8_unicode_ci; where stuck up!
i able traverse till node 6 above code. in next iteration have need check @ node 7 since nodes in order 5 rase n , not finite tree structure.
next tree traversal order 7 8 9 10 11 12 13 14 16 ......
i still thinking, faster traversing tree position_id every possible position. if @ complete tree of level see mean - example looks that.
the connections between position , position_id simple int arithmetic (div , modulo).
all nodes in subtrees share of properties - example direct subnodes of node 4 (third node in second row) numbers
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 so still have traverse levels in loop, not nodes if manage position number in every node.
step 2:
row r has 5^r elements (starting row 0).
store in every node row , column, in every row column starts 0. second row not 2,3,4,5,6 1|0, 1|1, 1|2, 1|3, 1|4.
if search root 1|1 (row 1, second element, in nice tree named "3"), children in row 2 have
col / 5 = 1 all children in row 3 have
col / 25 = 1 and on.
one level below node 2|10 nodes 3|(5*10) til 3|(5*11-1) = 50 .. 55-1
two levels below nodes 4|(50*5) til 4|(55*5-1)
and on.
step 3
pseudocode:
getfreenode($node){ $rowmax = 100; $row = $node->row + 1; $from = 5 * $node->col; $to = $from + 5; while($row <= $rowmax){ if ($id = query("select id member " ."where row = $row , col >= $from , col < $bis" ." , 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 } please ask if more details needed.
Comments
Post a Comment