欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

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

程序员文章站 2023-12-29 14:04:46
...
用户二叉树排序需求
  1. 用户注册,输入以下注册信息:

    - 电子邮箱
    - 密码
    - 确认密码
    - 推荐人ID(此ID可以在数据库中手动增加一个)
    
  2. 每注册进一个新用户,该用户就进入到排序中

  3. 排序规则

    1. 新增用户必须在推荐人下面
    2. 按照从左到右,从上到下的方式遍历,找到空位插入数据

下列是图解:

假设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

回复内容:

用户二叉树排序需求

  1. 用户注册,输入以下注册信息:

    - 电子邮箱
    - 密码
    - 确认密码
    - 推荐人ID(此ID可以在数据库中手动增加一个)
    
  2. 每注册进一个新用户,该用户就进入到排序中

  3. 排序规则

    1. 新增用户必须在推荐人下面
    2. 按照从左到右,从上到下的方式遍历,找到空位插入数据

下列是图解:

假设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运行环境,没测试代码的完全正确性@#@):

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 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

上一篇:

下一篇: