php - 使用改进的前序树遍历算法溢出二叉树中的新节点

Question

我想使用 php 在 MlM 应用程序中实现二叉树放置，

使用的术语：

推荐人，上线，下线

推荐人只会是前 2 个被推荐人的上线，额外的推荐人将溢出到二叉树以填充任何可用空间，从左到右

例子：

1. “A”指“B”和“C”和“D”，
2. “B”和“C”并作为“A”的下线放置，
3. “C”然后溢出到下一个可用空间。

4. 在这种情况下，在 "B" 的左侧，因为还没有任何下线

     A
     /\
    /  \
   B    C
   

   / D

假设每个推荐人只带来 2 人，我可以使用修改后的前序树遍历算法将其自动添加到表中，

但我的挑战是确定桌子上的下一个可用空间（按顺序）以添加来自已经有 2 条下线的推荐人的溢出。

Answer 1

我终于自己解决了这个问题。

//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;
    }