php - 幅優先探索方式での一般的なツリー トラバーサル (無限)

Question

各ノードに 5 つの子ノードがあり、それ以上は許可されないツリー構造があります。このツリーを幅優先検索でトラバースしたいと思います。

ここで、幅優先探索法を使用して、選択した親から空のノードを計算したいと考えています。

例えば

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 までトラバースできます。しかし、次の反復では、ノードが n に 5 の順序で並べられ、有限ツリー構造ではないため、@ ノード 7 をチェックする必要があります。

次のツリー走査順序 7 8 9 10 11 12 13 14 16 ......