목차
回复内容:
백엔드 개발 PHP 튜토리얼 数据结构和算法 - PHP 如何实现用户二叉树排序需求

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

Jun 06, 2016 pm 08:36 PM
php

用户二叉树排序需求

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

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

  3. 排序规则

    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>
로그인 후 복사
로그인 후 복사

C

有一位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>
로그인 후 복사
로그인 후 복사

回复内容:

用户二叉树排序需求

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

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

  3. 排序规则

    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>
로그인 후 복사
로그인 후 복사

C

有一位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>
로그인 후 복사
로그인 후 복사

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

这里就用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으로 문의하세요.

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai Generator

AI Hentai를 무료로 생성하십시오.

뜨거운 도구

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

CakePHP 프로젝트 구성 CakePHP 프로젝트 구성 Sep 10, 2024 pm 05:25 PM

이번 장에서는 CakePHP의 환경 변수, 일반 구성, 데이터베이스 구성, 이메일 구성에 대해 알아봅니다.

Ubuntu 및 Debian용 PHP 8.4 설치 및 업그레이드 가이드 Ubuntu 및 Debian용 PHP 8.4 설치 및 업그레이드 가이드 Dec 24, 2024 pm 04:42 PM

PHP 8.4는 상당한 양의 기능 중단 및 제거를 통해 몇 가지 새로운 기능, 보안 개선 및 성능 개선을 제공합니다. 이 가이드에서는 Ubuntu, Debian 또는 해당 파생 제품에서 PHP 8.4를 설치하거나 PHP 8.4로 업그레이드하는 방법을 설명합니다.

CakePHP 날짜 및 시간 CakePHP 날짜 및 시간 Sep 10, 2024 pm 05:27 PM

cakephp4에서 날짜와 시간을 다루기 위해 사용 가능한 FrozenTime 클래스를 활용하겠습니다.

CakePHP 파일 업로드 CakePHP 파일 업로드 Sep 10, 2024 pm 05:27 PM

파일 업로드 작업을 위해 양식 도우미를 사용할 것입니다. 다음은 파일 업로드의 예입니다.

CakePHP 라우팅 CakePHP 라우팅 Sep 10, 2024 pm 05:25 PM

이번 장에서는 라우팅과 관련된 다음과 같은 주제를 학습하겠습니다.

CakePHP 토론 CakePHP 토론 Sep 10, 2024 pm 05:28 PM

CakePHP는 PHP용 오픈 소스 프레임워크입니다. 이는 애플리케이션을 훨씬 쉽게 개발, 배포 및 유지 관리할 수 있도록 하기 위한 것입니다. CakePHP는 강력하고 이해하기 쉬운 MVC와 유사한 아키텍처를 기반으로 합니다. 모델, 뷰 및 컨트롤러 gu

PHP 개발을 위해 Visual Studio Code(VS Code)를 설정하는 방법 PHP 개발을 위해 Visual Studio Code(VS Code)를 설정하는 방법 Dec 20, 2024 am 11:31 AM

VS Code라고도 알려진 Visual Studio Code는 모든 주요 운영 체제에서 사용할 수 있는 무료 소스 코드 편집기 또는 통합 개발 환경(IDE)입니다. 다양한 프로그래밍 언어에 대한 대규모 확장 모음을 통해 VS Code는

CakePHP 유효성 검사기 만들기 CakePHP 유효성 검사기 만들기 Sep 10, 2024 pm 05:26 PM

컨트롤러에 다음 두 줄을 추가하면 유효성 검사기를 만들 수 있습니다.

See all articles