数据结构和算法 - PHP 如何实现用户二叉树排序需求

Question

用户二叉树排序需求 用户注册，输入以下注册信息： {代码...} 每注册进一个新用户，该用户就进入到排序中 排序规则 新增用户必须在推荐人下面 按照从左到右,从上到下的方式遍历，找到空位插入数据 下列是图解： ...

天蓬老师 · Answer

不谈为何要实现这样一个奇怪的需求。
就简单实现这个功能来讲，可以根据数据结构中二叉树的顺序存储方式来解决吧。

这里就用PHP中的数组来模拟二叉树的顺序存储，数组中的key相当于存储地址，value相当于存储的数据。当然key为有类似下面这样的结构：

             0
           /   \
           1   2

也就是父节点key值记为n，则左子节点key为2n+1，右子节点key为2(n+1)。下面简单用PHP代码实现下吧（由家里本本没有PHP运行环境，没测试代码的完全正确性@#@）：

phpclass Tree {
    private $data = [];

    public function __construct() {}

    /**
     * @param mixed $val
     * @param int $pid 父节点在$data中的key值
     * @return int 返回插入节点的对应在$data中的key值
     */
    public function add($val, $pid = 0) {

        // 若为空树则插入根节点
        if (!count($this->data)) {
            $this->data[0] = $val;
            return 0;
        }

        // 若左子节点为空则插入左子节点
        if (!isset($this->data[2*$pid+1])) {
            $this->data[2*$pid+1] = $val;
            return 2*$pid+1;
        }

        // 若右子节点为空则插入右子节点
        if (!isset($this->data[2*$pid+2])) {
            $this->data[2*pid+2] = val;
            return 2*pid+2;
        }

        // 获取$data中最后一个节点的key值
        $maxKey = max(array_keys($this->data);

        // 如果是完全二叉树的情况（也就是$data中没有空节点）则在$data最后插入值
        if (count($this->data) === $maxKey + 1) {
            $this->data[$maxKey+1] = $val;
            return $maxKey + 1;
        }

        // 不为完全二叉树则在$data中最小的空key处插入值
        for ($i = 0; $i <= $maxKey; ++$i) {
            if (!isset($this->data[$i])) {
                $this->data[$i] = $val;
                return $i;
            }
        }
    }
}


// 简单测试
$tree = new Tree();
$aid = $tree->add('A', 0);
$bid = $tree->add('B', $aid);
$tree->add('C', $bid);

天蓬老师 · Answer

你好，你这个需求会了吗？现在我也遇到这个需求，无法实现啊···求帮助，QQ369832727

Php8, saya datang juga

Ketahui reka letak tapak web dalam masa 30 minit

Tutorial Video Permulaan Shangguan Oracle kepada Mahir

Baris pertama kod UNI-APP anda

Berkibar dari awal ke pelancaran apl

Tutorial Video Linux Baharu Brother Lian

Tutorial Video AXURE 9 (Sesuai untuk UI Reka Bentuk Produk Interaktif Pengurus Produk)

Tutorial Video PS Kemahiran Asas Sifar

Tutorial video UI 16 hari untuk anda bermula

Tutorial Video Teknik PS dan Teknik Menghiris

Tutorial Video Pembinaan Persekitaran Awan Alibaba dan Pelancaran Projek

Gambaran Keseluruhan Rangkaian Komputer - Pengetahuan Asas yang Perlu Dikuasai Pengaturcara

Tutorial Penting untuk Pengaturcara - Penjelasan Protokol HTTP

Tutorial Video Websocket