数据结构和算法 - 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