数据结构和算法 - PHP 如何实现用户二叉树排序需求 -php教程-PHP中文网

首页

后端开发

php教程

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

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Jun 06, 2016 pm 08:36 PM

php

用户二叉树排序需求

用户注册，输入以下注册信息：

<code>- 电子邮箱
- 密码
- 确认密码
- 推荐人ID(此ID可以在数据库中手动增加一个)
</code>

每注册进一个新用户，该用户就进入到排序中
排序规则
1. 新增用户必须在推荐人下面
2. 按照从左到右,从上到下的方式遍历，找到空位插入数据

下列是图解：

假设A是根节点(A就是手动添加的第一位用户)
有一个新用户注册进来(假设新用户为B)，推荐人ID填写的是A的ID，则排序如下：

<code>    A
    /
   B 
</code>

又有一位C用户注册，推荐人ID填写的是B的ID，则：

<code>     A
    /
   B
  /
 C
</code>

有一位D用户注册，推荐人ID填写的是A的ID，则：

<code>   A
  /  \
 B   D  
/
</code>

有一位E用户注册，推荐人ID填写的是B的ID，则

<code>       A
      /  \
     B   D  
    /  \
   C   E
</code>

有一位F用户注册，推荐人ID填写的是A的ID，则

<code>       A
     /   \
    B     D 
   /  \   /
  C   E F
</code>

有一位G用户注册，推荐人ID填写的是E的ID，则

<code>        A
     /     \
    B      D    
   /  \    /
  C   E  F
      /
     G
</code>

有一位H用户注册，推荐人ID填写的是B的ID，则

H的推荐人是B，所以，H必定是在B的下面，然后按照从左到右的方式查找，C和E占了上面的两个位置，所以到下一排查找，找到空位，则插入H，以下都是这种规律

<code>        A
     /     \
    B      D    
   /  \    /
  C   E  F
 /    /
H   G
</code>

有一位I用户，和J用户又陆续注册进来，填写的都是C的ID，则

<code>           A
        /       \
       B       D    
     /     \   /
    C     E  F
   /   \   /
  H    I G
 /
J
</code>

有一位K用户，和L用户又陆续注册进来，填写的都是A的ID，则

<code>          A
     /         \
    B          D    
  /     \      /   \
 C       E   F   K
/   \    /   \
   H    I  G   L
  /
J
</code>

有一位M用户，N用户和O用户又注册进来，填写的分别是B用户，C用户，和L用户的ID，则：

<code><br> A              
         /         \
        B          D    
      /    \      /    \
     C     E    F     K
    /   \  /   \
   H   I G    L
  /  \  
 J   M      
</code>

<code>               A                
          /          \
         B           D  
      /      \      /     \
      C       E   F      K
    /    \    /   \
   H     I  G   L
  /   \   / 
 J   M  N    
</code>

<code>                A               
           /           \
          B            D    
       /      \     /       \
     C        E   F       K
   /    \    /    \
  H     I  G     L
 /  \    /        /
J   M  N        O
</code>

有一位P用户、Q用户、R用户、S用户又注册进来，填写的分别是A用户，B用户，E用户，A用户的ID。则：

<code>                  A             
            /           \
           B            D   
         /     \       /     \
       C       E     F     K
    /     \    /   \   /
   H     I  G   L  P
  /   \   /      /
 J   M  N     O
</code>

<code>                   A                
            /             \
           B              D 
        /      \        /      \
       C       E      F      K
    /     \    /   \    /
   H      I  G    L  P
  /  \    /  \      /
 J   M  N   Q   O
</code>

<code>                         A              
                /                \
               B                  D 
           /         \          /       \
          C           E       F       K
       /     \        /   \    /
      H      I      G    L  P
     /  \    /  \    /     /
    J   M  N  Q  R    O
</code>

<code>                     A              
            /                 \
           B                   D    
       /         \           /       \
     C           E        F         K
   /    \       /    \    /    \
 H      I     G     L  P    S 
/  \    /  \    /     /
   J   M  N  Q  R    O
</code>

回复内容：

用户二叉树排序需求

用户注册，输入以下注册信息：

<code>- 电子邮箱
- 密码
- 确认密码
- 推荐人ID(此ID可以在数据库中手动增加一个)
</code>

每注册进一个新用户，该用户就进入到排序中
排序规则
1. 新增用户必须在推荐人下面
2. 按照从左到右,从上到下的方式遍历，找到空位插入数据

下列是图解：

假设A是根节点(A就是手动添加的第一位用户)
有一个新用户注册进来(假设新用户为B)，推荐人ID填写的是A的ID，则排序如下：

<code>    A
    /
   B 
</code>

又有一位C用户注册，推荐人ID填写的是B的ID，则：

<code>     A
    /
   B
  /
 C
</code>

有一位D用户注册，推荐人ID填写的是A的ID，则：

<code>   A
  /  \
 B   D  
/
</code>

有一位E用户注册，推荐人ID填写的是B的ID，则

<code>       A
      /  \
     B   D  
    /  \
   C   E
</code>

有一位F用户注册，推荐人ID填写的是A的ID，则

<code>       A
     /   \
    B     D 
   /  \   /
  C   E F
</code>

有一位G用户注册，推荐人ID填写的是E的ID，则

<code>        A
     /     \
    B      D    
   /  \    /
  C   E  F
      /
     G
</code>

有一位H用户注册，推荐人ID填写的是B的ID，则

<code>        A
     /     \
    B      D    
   /  \    /
  C   E  F
 /    /
H   G
</code>

有一位I用户，和J用户又陆续注册进来，填写的都是C的ID，则

<code>           A
        /       \
       B       D    
     /     \   /
    C     E  F
   /   \   /
  H    I G
 /
J
</code>

有一位K用户，和L用户又陆续注册进来，填写的都是A的ID，则

<code>          A
     /         \
    B          D    
  /     \      /   \
 C       E   F   K
/   \    /   \
   H    I  G   L
  /
J
</code>

有一位M用户，N用户和O用户又注册进来，填写的分别是B用户，C用户，和L用户的ID，则：

<code><br> A              
         /         \
        B          D    
      /    \      /    \
     C     E    F     K
    /   \  /   \
   H   I G    L
  /  \  
 J   M      
</code>

<code>               A                
          /          \
         B           D  
      /      \      /     \
      C       E   F      K
    /    \    /   \
   H     I  G   L
  /   \   / 
 J   M  N    
</code>

<code>                A               
           /           \
          B            D    
       /      \     /       \
     C        E   F       K
   /    \    /    \
  H     I  G     L
 /  \    /        /
J   M  N        O
</code>

有一位P用户、Q用户、R用户、S用户又注册进来，填写的分别是A用户，B用户，E用户，A用户的ID。则：

<code>                  A             
            /           \
           B            D   
         /     \       /     \
       C       E     F     K
    /     \    /   \   /
   H     I  G   L  P
  /   \   /      /
 J   M  N     O
</code>

<code>                   A                
            /             \
           B              D 
        /      \        /      \
       C       E      F      K
    /     \    /   \    /
   H      I  G    L  P
  /  \    /  \      /
 J   M  N   Q   O
</code>

<code>                         A              
                /                \
               B                  D 
           /         \          /       \
          C           E       F       K
       /     \        /   \    /
      H      I      G    L  P
     /  \    /  \    /     /
    J   M  N  Q  R    O
</code>

<code>                     A              
            /                 \
           B                   D    
       /         \           /       \
     C           E        F         K
   /    \       /    \    /    \
 H      I     G     L  P    S 
/  \    /  \    /     /
   J   M  N  Q  R    O
</code>

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

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

<code>             0
           /   \
           1   2
</code>

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

<code>php</code><code>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);
</code>

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

声明

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

PHP：服务器端脚本语言的简介Apr 16, 2025 am 12:18 AM

PHP是一种服务器端脚本语言，用于动态网页开发和服务器端应用程序。1.PHP是一种解释型语言，无需编译，适合快速开发。2.PHP代码嵌入HTML中，易于网页开发。3.PHP处理服务器端逻辑，生成HTML输出，支持用户交互和数据处理。4.PHP可与数据库交互，处理表单提交，执行服务器端任务。

PHP和网络：探索其长期影响Apr 16, 2025 am 12:17 AM

PHP在过去几十年中塑造了网络，并将继续在Web开发中扮演重要角色。1)PHP起源于1994年，因其易用性和与MySQL的无缝集成成为开发者首选。2)其核心功能包括生成动态内容和与数据库的集成，使得网站能够实时更新和个性化展示。3)PHP的广泛应用和生态系统推动了其长期影响，但也面临版本更新和安全性挑战。4)近年来的性能改进，如PHP7的发布，使其能与现代语言竞争。5)未来，PHP需应对容器化、微服务等新挑战，但其灵活性和活跃社区使其具备适应能力。

为什么要使用PHP？解释的优点和好处Apr 16, 2025 am 12:16 AM

PHP的核心优势包括易于学习、强大的web开发支持、丰富的库和框架、高性能和可扩展性、跨平台兼容性以及成本效益高。1)易于学习和使用，适合初学者；2)与web服务器集成好，支持多种数据库；3)拥有如Laravel等强大框架；4)通过优化可实现高性能；5)支持多种操作系统；6)开源，降低开发成本。

揭穿神话：PHP真的是一种死语吗？Apr 16, 2025 am 12:15 AM

PHP没有死。1)PHP社区积极解决性能和安全问题，PHP7.x提升了性能。2)PHP适合现代Web开发，广泛用于大型网站。3)PHP易学且服务器表现出色，但类型系统不如静态语言严格。4)PHP在内容管理和电商领域仍重要，生态系统不断进化。5)通过OPcache和APC等优化性能，使用OOP和设计模式提升代码质量。

PHP与Python辩论：哪个更好？Apr 16, 2025 am 12:03 AM

PHP和Python各有优劣，选择取决于项目需求。1)PHP适合Web开发，易学，社区资源丰富，但语法不够现代，性能和安全性需注意。2)Python适用于数据科学和机器学习，语法简洁，易学，但执行速度和内存管理有瓶颈。

PHP的目的：构建动态网站Apr 15, 2025 am 12:18 AM

PHP用于构建动态网站，其核心功能包括：1.生成动态内容，通过与数据库对接实时生成网页；2.处理用户交互和表单提交，验证输入并响应操作；3.管理会话和用户认证，提供个性化体验；4.优化性能和遵循最佳实践，提升网站效率和安全性。

PHP：处理数据库和服务器端逻辑Apr 15, 2025 am 12:15 AM

PHP在数据库操作和服务器端逻辑处理中使用MySQLi和PDO扩展进行数据库交互，并通过会话管理等功能处理服务器端逻辑。1）使用MySQLi或PDO连接数据库，执行SQL查询。2）通过会话管理等功能处理HTTP请求和用户状态。3）使用事务确保数据库操作的原子性。4）防止SQL注入，使用异常处理和关闭连接来调试。5）通过索引和缓存优化性能，编写可读性高的代码并进行错误处理。