1

phpを使ってMlMアプリに二分木配置を実装したいのですが、

使用される用語:

リファラー、アップライン、ダウンライン

リファラーは、最初に参照された 2 つのアップラインのみになり、追加のリフェラルはバイナリ ツリーにスピルオーバーされ、利用可能なスペースを左から右に埋めます。

例：

  1. 「A」は「B」と「C」と「D」を指し、
  2. 「B」と「C」を「A」のダウンラインとして配置し、
  3. 「C」は、次に使用可能なスペースにスピルオーバーします。

  4. この場合は "B" の左側にあり、ダウンラインがまだないためです。

      A
  /\
 /  \
B    C

    / D

すべてのリファラーが 2 人だけを連れてくると仮定すると、修正されたプレオーダー ツリー トラバーサル アルゴリズムを使用して、テーブルに自動的に追加できます。

しかし、私の課題は、テーブルで次に利用可能なスペースを (順番に) 識別して、既に 2 つのダウンラインを持っているリファラーからのスピルオーバーを追加することです。

4

1 に答える 1

0

私は最終的に自分で問題を解決しました。

//traverse the network binary tree to fetch the next available upline to place the user under
    function get_next_free_upline($pref, $sponsor_id)
    {

        $ref_id = $sponsor_id;
        $get_next = TRUE;

        $level = 1;
        $lft = $this->get_pointers($ref_id, 'lft');
        $rgt = $this->get_pointers($ref_id, 'rgt');
        $offset = $this->get_offset($lft, $rgt);

        while ($get_next !== FALSE) 
        {               
            $query = $this->db->query
            ('  SELECT node.*, (COUNT(parent.upline_id) - ' . $offset . ') AS level
                FROM tree AS node
                CROSS JOIN tree AS parent
                WHERE (node.lft BETWEEN parent.lft AND parent.rgt AND 
                 node.lft > ' . $lft .' AND node.rgt < ' . $rgt . ')
                GROUP BY node.id    
                having level = ' . $level . '
                ORDER BY node.lft           
            ');


            $result = $query->result();

            //check if this upline has less than 2 downlines
            //if yes, assign the user_id to upline and return
            if ($query->num_rows() < 2)
            {
                $upline_id = $sponsor_id;
                $get_next = FALSE;
            }
            else
            {   //loop through all members under the current sponsor id 
                //to know where to spill over the referred member
                foreach ($result as $row):  



                    $sponsor_id = $row->id;

                    //check all occurences of this level member as an upline            
                    $this->db->select('*');
                    $this->db->from('tree');
                    $this->db->where('upline_id', $sponsor_id);

                    $inner_query = $this->db->get();

                    if ($inner_query->num_rows() < 2)
                    {
                        $upline_id = $sponsor_id;
                        $get_next = FALSE;
                        break;
                    }           
                endforeach; 

                //increase the level number and loop back               
                $level  = $level + 1;
                $get_next = TRUE;   
            }               
        }           
            return $upline_id;
    }
于 2012-11-18T23:54:13.580 に答える