数据结构和算法 - 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, I'm coming too

Learn website layout in 30 minutes

Shangguan Oracle Beginner to Proficient Video Tutorial

Your first line of UNI-APP code

Flutter from scratch to app launch

Brother Lian New Linux Video Tutorial

AXURE 9 Video Tutorial (Suitable for Product Manager Interactive Product Design UI)

Zero Basic Proficiency PS Video Tutorial

16 day UI video tutorial to get you started

PS Techniques and Slicing Techniques Video Tutorial

Alibaba Cloud Environment Construction and Project Launch Video Tutorial

Overview of Computer Networks - Basic Knowledge that Programmers Must Master

Essential Tutorial for Programmers - HTTP Protocol Explanation

Websocket Video Tutorial