PHP二叉树自动排位算法

要点

自动公排

1. 一人下面只排两个人，即二叉树
2. 如果排满，往下查找，从左往右查找没有排满的

数据库结构

user_tree:id, userid, pid, share_id

算法

public static function get_node_pid($share_id){
        $layer = 1;

        $not_found = true;

        $uids = [];

        $pid = 0;

        while($not_found){
            if($layer == 1){
                $pids = [$share_id];
            }else{
                $pids = $uids[$layer - 1];
            }
            $pids_str = implode(",", $pids);

            $users = db('user_tree', [], false)->where("pid in ({$pids_str})")->field("user_id")->select();

            $uids[$layer] = array_column($users, 'user_id');

            $count_layer = count($uids[$layer]);

            $count_full = pow(2, $layer);

            if($count_layer == $count_full){
                $layer += 1;
            }else{
                foreach ($pids as $pid_a){
                    $count = db('user_tree', [], false)->where(['pid' => $pid_a])->count();
                    if($count < 2){
                        $pid = $pid_a;
                        break;
                    }
                }
                $not_found = false;
            }
        }

        return $pid;
    }