数据结构和算法 - PHP 如何实现用户二叉树排序需求
用户二叉树排序需求
-
用户注册，输入以下注册信息：
<code>- 电子邮箱 - 密码 - 确认密码 - 推荐人ID(此ID可以在数据库中手动增加一个) </code>
ログイン後にコピーログイン後にコピー 每注册进一个新用户，该用户就进入到排序中
-
排序规则
- 新增用户必须在推荐人下面
- 按照从左到右,从上到下的方式遍历，找到空位插入数据
下列是图解：
假设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>回复内容：
用户二叉树排序需求
-
用户注册，输入以下注册信息：
<code>- 电子邮箱 - 密码 - 确认密码 - 推荐人ID(此ID可以在数据库中手动增加一个) </code>
ログイン後にコピーログイン後にコピー 每注册进一个新用户，该用户就进入到排序中
-
排序规则
- 新增用户必须在推荐人下面
- 按照从左到右,从上到下的方式遍历，找到空位插入数据
下列是图解：
假设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
ホットAIツール
Undresser.AI Undress
リアルなヌード写真を作成する AI 搭載アプリ
AI Clothes Remover
写真から衣服を削除するオンライン AI ツール。
Undress AI Tool
脱衣画像を無料で
Clothoff.io
AI衣類リムーバー
AI Hentai Generator
AIヘンタイを無料で生成します。
人気の記事
ホットツール
メモ帳++7.3.1
使いやすく無料のコードエディター
SublimeText3 中国語版
中国語版、とても使いやすい
ゼンドスタジオ 13.0.1
強力な PHP 統合開発環境
ドリームウィーバー CS6
ビジュアル Web 開発ツール
SublimeText3 Mac版
神レベルのコード編集ソフト（SublimeText3）
ホットトピック
7469
15
1376
52
77
11
19
29
Ubuntu および Debian 用の PHP 8.4 インストールおよびアップグレード ガイド
Dec 24, 2024 pm 04:42 PM
PHP 8.4 では、いくつかの新機能、セキュリティの改善、パフォーマンスの改善が行われ、かなりの量の機能の非推奨と削除が行われています。 このガイドでは、Ubuntu、Debian、またはその派生版に PHP 8.4 をインストールする方法、または PHP 8.4 にアップグレードする方法について説明します。
CakePHP について話し合う
Sep 10, 2024 pm 05:28 PM
CakePHP は、PHP 用のオープンソース フレームワークです。これは、アプリケーションの開発、展開、保守をより簡単にすることを目的としています。 CakePHP は、強力かつ理解しやすい MVC のようなアーキテクチャに基づいています。モデル、ビュー、コントローラー
CakePHP ファイルのアップロード
Sep 10, 2024 pm 05:27 PM
ファイルのアップロードを行うには、フォーム ヘルパーを使用します。ここではファイルアップロードの例を示します。
CakePHP のロギング
Sep 10, 2024 pm 05:26 PM
CakePHP へのログインは非常に簡単な作業です。使用する関数は 1 つだけです。 cronjob などのバックグラウンド プロセスのエラー、例外、ユーザー アクティビティ、ユーザーが実行したアクションをログに記録できます。 CakePHP でのデータのログ記録は簡単です。 log()関数が提供されています
PHP 開発用に Visual Studio Code (VS Code) をセットアップする方法
Dec 20, 2024 am 11:31 AM
Visual Studio Code (VS Code とも呼ばれる) は、すべての主要なオペレーティング システムで利用できる無料のソース コード エディター (統合開発環境 (IDE)) です。 多くのプログラミング言語の拡張機能の大規模なコレクションを備えた VS Code は、
CakePHP クイックガイド
Sep 10, 2024 pm 05:27 PM
CakePHP はオープンソースの MVC フレームワークです。これにより、アプリケーションの開発、展開、保守がはるかに簡単になります。 CakePHP には、最も一般的なタスクの過負荷を軽減するためのライブラリが多数あります。
