数据结构和算法 - PHP 如何实现用户二叉树排序需求
-
用户注册,输入以下注册信息:
- 电子邮箱 - 密码 - 确认密码 - 推荐人ID(此ID可以在数据库中手动增加一个)
每注册进一个新用户,该用户就进入到排序中
-
排序规则
- 新增用户必须在推荐人下面
- 按照从左到右,从上到下的方式遍历,找到空位插入数据
下列是图解:
假设A是根节点(A就是手动添加的第一位用户)
有一个新用户注册进来(假设新用户为B),推荐人ID填写的是A的ID,则排序如下:
A
/
B
又有一位C用户注册,推荐人ID填写的是B的ID,则:
A
/
B
/
C
有一位D用户注册,推荐人ID填写的是A的ID,则:
A
/ \
B D
/
C
有一位E用户注册,推荐人ID填写的是B的ID,则
A
/ \
B D
/ \
C E
有一位F用户注册,推荐人ID填写的是A的ID,则
A
/ \
B D
/ \ /
C E F
有一位G用户注册,推荐人ID填写的是E的ID,则
A
/ \
B D
/ \ /
C E F
/
G
有一位H用户注册,推荐人ID填写的是B的ID,则
H的推荐人是B,所以,H必定是在B的下面,然后按照从左到右的方式查找,C和E占了上面的两个位置,所以到下一排查找,找到空位,则插入H,以下都是这种规律
A
/ \
B D
/ \ /
C E F
/ /
H G
有一位I用户,和J用户又陆续注册进来,填写的都是C的ID,则
A
/ \
B D
/ \ /
C E F
/ \ /
H I G
/
J
有一位K用户,和L用户又陆续注册进来,填写的都是A的ID,则
A
/ \
B D
/ \ / \
C E F K
/ \ / \
H I G L
/
J
有一位M用户,N用户和O用户 又注册进来,填写的分别是B用户,C用户,和L用户的ID,则:
A
/ \
B D
/ \ / \
C E F K
/ \ / \
H I G L
/ \
J M
A
/ \
B D
/ \ / \
C E F K
/ \ / \
H I G L
/ \ /
J M N
A
/ \
B D
/ \ / \
C E F K
/ \ / \
H I G L
/ \ / /
J M N O
有一位P用户、Q用户、R用户、S用户又注册进来,填写的分别是A用户,B用户,E用户,A用户的ID。则:
A
/ \
B D
/ \ / \
C E F K
/ \ / \ /
H I G L P
/ \ / /
J M N O
A
/ \
B D
/ \ / \
C E F K
/ \ / \ /
H I G L P
/ \ / \ /
J M N Q O
A
/ \
B D
/ \ / \
C E F K
/ \ / \ /
H I G L P
/ \ / \ / /
J M N Q R O
A
/ \
B D
/ \ / \
C E F K
/ \ / \ / \
H I G L P S
/ \ / \ / /
J M N Q R O
回复内容:
用户二叉树排序需求
-
用户注册,输入以下注册信息:
- 电子邮箱 - 密码 - 确认密码 - 推荐人ID(此ID可以在数据库中手动增加一个)
每注册进一个新用户,该用户就进入到排序中
-
排序规则
- 新增用户必须在推荐人下面
- 按照从左到右,从上到下的方式遍历,找到空位插入数据
下列是图解:
假设A是根节点(A就是手动添加的第一位用户)
有一个新用户注册进来(假设新用户为B),推荐人ID填写的是A的ID,则排序如下:
A
/
B
又有一位C用户注册,推荐人ID填写的是B的ID,则:
A
/
B
/
C
有一位D用户注册,推荐人ID填写的是A的ID,则:
A
/ \
B D
/
C
有一位E用户注册,推荐人ID填写的是B的ID,则
A
/ \
B D
/ \
C E
有一位F用户注册,推荐人ID填写的是A的ID,则
A
/ \
B D
/ \ /
C E F
有一位G用户注册,推荐人ID填写的是E的ID,则
A
/ \
B D
/ \ /
C E F
/
G
有一位H用户注册,推荐人ID填写的是B的ID,则
H的推荐人是B,所以,H必定是在B的下面,然后按照从左到右的方式查找,C和E占了上面的两个位置,所以到下一排查找,找到空位,则插入H,以下都是这种规律
A
/ \
B D
/ \ /
C E F
/ /
H G
有一位I用户,和J用户又陆续注册进来,填写的都是C的ID,则
A
/ \
B D
/ \ /
C E F
/ \ /
H I G
/
J
有一位K用户,和L用户又陆续注册进来,填写的都是A的ID,则
A
/ \
B D
/ \ / \
C E F K
/ \ / \
H I G L
/
J
有一位M用户,N用户和O用户 又注册进来,填写的分别是B用户,C用户,和L用户的ID,则:
A
/ \
B D
/ \ / \
C E F K
/ \ / \
H I G L
/ \
J M
A
/ \
B D
/ \ / \
C E F K
/ \ / \
H I G L
/ \ /
J M N
A
/ \
B D
/ \ / \
C E F K
/ \ / \
H I G L
/ \ / /
J M N O
有一位P用户、Q用户、R用户、S用户又注册进来,填写的分别是A用户,B用户,E用户,A用户的ID。则:
A
/ \
B D
/ \ / \
C E F K
/ \ / \ /
H I G L P
/ \ / /
J M N O
A
/ \
B D
/ \ / \
C E F K
/ \ / \ /
H I G L P
/ \ / \ /
J M N Q O
A
/ \
B D
/ \ / \
C E F K
/ \ / \ /
H I G L P
/ \ / \ / /
J M N Q R O
A
/ \
B D
/ \ / \
C E F K
/ \ / \ / \
H I G L P S
/ \ / \ / /
J M N Q R O
不谈为何要实现这样一个奇怪的需求。
就简单实现这个功能来讲,可以根据数据结构中二叉树的顺序存储方式来解决吧。
这里就用PHP中的数组来模拟二叉树的顺序存储,数组中的key相当于存储地址,value相当于存储的数据。当然key为有类似下面这样的结构:
0
/ \
1 2
也就是父节点key值记为n,则左子节点key为2n+1,右子节点key为2(n+1)。下面简单用PHP代码实现下吧(由家里本本没有PHP运行环境,没测试代码的完全正确性@#@):
php
class 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 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);
你好,你这个需求会了吗?现在我也遇到这个需求,无法实现啊···求帮助,QQ369832727