在树下查找 ID - 查询逻辑 - PHP

使用您当前的数据库模式，我只看到多个选择语句的选项。你必须向上或向下检查树，直到你击中根或最后一个孩子(就像尼顿菲尔斯的答案一样(。

我自己会在表格中添加第四列，包含完整路径：

id   name   childOf   pathToFolder
----------------------------------
1      A        0      ,1,
2      B        1      ,1,2,
3      C        0      ,1,3,
4      D        3      ,1,3,4,
5      E        2      ,1,2,5,
6      F        5      ,1,2,5,6,

有几种方法可以使用这些新数据。一种方法是，如果有人想移动B，请获取有效目的地的列表：SELECT id FROM folders WHERE pathToFolder NOT LIKE ',1,2,%'

这种操作不是最快的，但非常方便。

会有一种方法可以同时获取目标和目标(或整个数据对象等(的 id，并检查目标是否在目标路径中。如果是，则该方法将返回 false 或引发异常，否则将返回 true。可以将该方法作为控制结构引入目录复制代码流。

就个人而言，对于分层数据结构，我会将其实现为嵌套集。设置和修复嵌套集可能会很麻烦，但我觉得它对于检查节点之间的关系和获取整个子树非常方便。

这是一个 PHPUnit 测试，部分且有点幼稚地实现了我的想法：

<?php
ini_set('display_errors', 1);
ini_set('display_startup_errors', 1);
error_reporting(-1);
require 'vendor/autoload.php';
class ParentingSucks
{
    public $data = array();
    public function isAllowed($targetId, $destId)
    {
        $target = $this->getById($targetId);
        $dest = $this->getById($destId);
        $parent = $this->getById($dest['childOf']);
        $isAllowed = true;
        while ($parent) {
            if ($parent['id'] == $targetId) {
                $isAllowed = false;
                break;
            }
            $parent = $this->getById($parent['childOf']);
        }
        return $isAllowed;
    }
    public function getById($id)
    {
        if (isset($this->data[$id])) {
            return $this->data[$id];
        }
        return array();
     }
}
class HowIMetYourParentDir extends PHPUnit_Framework_TestCase
{
    /**
     * @test
     * @dataProvider generate
     */
    public function droppingOnParentNotAllowed($data, $target, $dest, $outcome)
    {
        $stub = $this->getMock('ParentingSucks', null);
        $stub->data = $data;
        $result = $stub->isAllowed($target, $dest);
        $this->assertEquals($result, $outcome, 'Oh no!');
    }
    public function generate()
    {
        $fakeData = array(
            1 => array('id' => 1, 'name' => 'A', 'childOf' => 0),
            2 => array('id' => 2, 'name' => 'B', 'childOf' => 1),
            3 => array('id' => 3, 'name' => 'C', 'childOf' => 0),
            4 => array('id' => 4, 'name' => 'D', 'childOf' => 3),
            5 => array('id' => 5, 'name' => 'E', 'childOf' => 2),
            6 => array('id' => 6, 'name' => 'F', 'childOf' => 5),
        );
        return array(
            array(
                $fakeData,
                2, // target
                6, // dest
                false, // outcome
            ),
            array(
                $fakeData,
                4,
                2,
                true,
            ),
            array(
                $fakeData,
                4,
                2,
                true,
            ),
            array(
                $fakeData,
                3,
                4,
                false,
            ),
        );
    }
}              false, // outcome
            ),
            array(
                $fakeData,
                4,
                2,
                true,
            ),
            array(
                $fakeData,
                4,
                2,
                true,
            ),
            array(
                $fakeData,
                3,
                4,
                false,
            ),
        );
    }
}

变量/函数/类名可能不适合您的域模型，所以不要介意它们。

您有几个选择：

1. 使用当前的树结构，您可以递归(或使用堆栈(迭代要附加到的元素的父元素;如果父元素之一等于追加的元素，则只需返回错误。您还可以在javascript中执行该检查以提供更好的用户体验(为什么甚至允许将元素拖动到它自己的子:)(;然而，这种方法对于真正的大树来说可能有点慢，但写入真的很便宜。

2. 您可以通过将树结构重新加工为嵌套集来简化处理树;我不会深入讨论嵌套集的细节，因为您可以在此页面上阅读以下内容：关于嵌套集。相反，我将让您快速了解嵌套集的可能性。首先，您的表格如下所示：

   ID 名称 LFT RGT    ---------------------------    1 A 1 8    2 B 2 7    5 E 3 6    6 楼 4 5    3 C 9 12    4 天 10 11

乍一看可能看起来很奇怪，但现在不要担心。

这样，您可以轻松检查一个节点是否是另一个节点的父节点：$static->lft > $appended->lft && $static->rgt < $appended->rgt，如果这是真的，那么$appended是$static的父节点，您可能会抛出错误;

您是否需要：

• 检索给定节点的所有父节点？选择 WHERE lft < $node->lft and rgt > $node->rgt ;
• 检索所有后代？选择WHERE lft > $node->lft and rgt < $node->rgt
• 找回所有兄弟姐妹？在列中添加额外的level，这很容易

但是等等等等，我如何在该结构中插入一个新节点？你可能会问。幸运的是，没有必要重新发明轮子，因为嵌套集非常受欢迎。你可以使用这样的实现：https://github.com/riquito/Baobab/，只专注于你的应用;

查看存储库中的一些示例：https://github.com/riquito/Baobab/blob/master/src/examples/animals.php

$root_id=$tree->appendChild(NULL,array("name"=>'Animals'));
$vertebrates_id   = $tree->appendChild($root_id,array("name"=>"Vertebrates"));
$invertebrates_id = $tree->appendChild($root_id,array("name"=>"Invertebrates"));

如您所见，您不必触及lft或rgt值，因为有人已经为您编写了该部分。如果你使用Propel或Doctrine，事情会更容易，因为它们都支持嵌套集。

逻辑相当简单：

可以将文件夹f拖动到目标文件夹t当且仅当f<>t和f不是t的祖先.

由于该问题被标记为 php 并且没有指定 RDBMS，因此我将假设您的文件夹位于如下所示的 php 数组中：

$namespace=array(
  1=>array('name'=>'A','parent'=>0),
  2=>array('name'=>'B','parent'=>1),
  3=>array('name'=>'C','parent'=>0),
  4=>array('name'=>'D','parent'=>3),
  5=>array('name'=>'E','parent'=>2),
  6=>array('name'=>'F','parent'=>5),
  );

要确定$f是否是$t的祖先，我们应该从$t开始，然后向上走树，直到(1(我们找到$f或(2(我们找到一个根(不是根，因为您的命名空间中有多个根(。因此，请考虑以下函数：

function is_ancestor($f,$t)
  {
  global $namespace;
  $are_equal=($f==$t);
  $t_parent=$namespace[$t]['parent'];
  $is_root=!isset($namespace[$t_parent]);
  return $are_equal || (!$is_root && is_ancestor($f,$t_parent));
  }

我认为这很简单。但有两件事：(1(显然，参数是文件夹ID，(2(尽管名称如此，该函数不仅检查$f是否是$t的祖先，而且还检查它们是否相等。

你可以在这个php小提琴中看到整个概念的实际应用。

次优方法是简单地计算给定文件夹的所有子文件夹，然后检查目标文件夹是否是其中的一部分。可能看起来像这样：

getSubfolders(folder):
    oneLevelDeepSubfolders = subfolders with child-of field == folder.id
    allSubfolders = []
    for subfolder in oneLevelDeepFolders:
        allSubfolders += getSubfolders(subfolder);
    return allSubfolders;

然后只需检查您的目标文件夹是否在getSubfolder(文件夹(中。

您可能希望通过创建另一个表来加快此过程，该表预先计算任意深度的子文件夹关系，这样您就不必在每次需要时都递归计算它。

想起了语言课上的事情。所以我想出了一个这样的解决方案：让我用一种想象的方式建造你的树。我会说 R 表示根 (id：0(，-1 表示结尾。

R:AC
A:B
B:E
E:F
F:-1
C:D
D:-1

但是，如果我们想快速做事，这还不够。让我们也添加这些：

R:BC
R:EC
R:FC
R:BD
R:ED
R:FD

让我为您整理一下：

R:AC
R:AD *I added this one
R:BC
R:EC
R:FC
R:BD
R:ED
R:FD
R:A * this one too
R:C * this one too
A:B
B:E
E:F
C:D
F:-1
D:-1

这应该足够了。所以，你说

例如，D 到 B 是可以的，D 到 E 是可以的，B 到 F 是不可以的，因为它拖到

自己的树中，但 F 到 B 可以，因为它拖到树上。

让我们看看，D到B可以吗？我们应该从右到左检查它。D在哪里？哦，是的，你在那里..R：BD！所以，如果他们在一起可以吗？是的，没关系。D 到 E？R：ED！是的，也没关系。B 到 F？让我们一起来看看BF...没有哈？所以，右侧的B...有A：B，那么我们来检查一下A R：A！繁荣！B

这只是一个以不同方式看待事物的建议。它可以通过不同的观点来完成。但我真的认为使用这样的语言语法会有所帮助。它可以在空中创建，也可以根据情况作为地图文件完成。但是在很多情况下，复杂性确实很低。祝你好运，找到最佳解决方案！

我不明白你的问题。算法非常简单。

每次调用PHP时，您首先要检查该文件夹是否不是目标文件夹的子文件夹。现在在您的情况下，这是行不通的。您不应使用数字 id 来保存文件夹和文件，因为所有操作系统都使用文件路径。

就像这样：

url                    type     description
-------------------------------------------------
ROOT/folder            2        Image folder...
ROOT/hallo             1        Hallo directory..
ROOT/hallo/subfolder   1        I am a sub dir..

现在您只需要一列，但它将是一个全文索引。当您要检查文件夹是否不是其自己的子文件夹的父文件夹时，您只需检查 url。

就像我画ROOT/hallo To ROOT/hallo/subfolder 你只需这样做：

根/哈洛 = 10 个字符

根/哈洛/子文件夹 = 20 个字符

<?php
    $selected_folder = 'ROOT/hallo';
    $subject_folder = 'ROOT/hallo/subfolder';
    $length = strlen($selected_folder);
    if($selected_folder != substr($subject_folder,0,$length)){
         echo 'go';
    }
    else{
        echo 'Can not relocate folder to its own subfolder';
    }
?>

由于问题被标记为PHP，并且您正在谈论拖放，因此您需要类来表示PHP和JavaScript中的树行为

对于PHP，我建议你通过cake-php框架的TreeBehavior类的实现，它为任何模型添加了树行为，并期望你按照Adam的建议拥有你的表结构。

对于Javascript实现，我观察到YUI树模块

实现 JavaScript 的树

还有一个库可能支持拖放，在这里找到它

我希望这对你有帮助。

只是检查父母，直到你点击你的根文件夹？在伪代码中

// targetFolder is the target folder where the folder is going to be moved
// while sourceFolder is the folder that's moved.
parents = targetFolder.getParents();
if (parents.contains(sourceFolder)) {
    // don't allow the operation
}

您可以检查目标路径。如果父节点之一是源节点，则链将断开并显示错误。例如：

<?php
define("ROOT_NODE_ID",0);
function getChildOf($nodeId){
   // some code to get id value of parent node and assign it to $parentId
   return $parentId;
}
$sourceId = 2; // Node B
$destinationId = 6; // Node F
$error = false;
$tmpParentId = getChildOf( $destinationId );
while($tmpParentId != ROOT_NODE_ID){
    if($tmpParentId == $sourceId ){
        $error=true;
        break;
    }
    $tmpParentId = getChildOf( $tmpParentId );
}

此方法允许使用具有整数值的索引和 NOT USE 字符串函数。字符串函数在处理 int 类型字段时可能会慢得多。您也可以保留此表结构而无需进行任何修改。

创建两个函数并获取每个 id 的所有顶级父级，即从 B 到 A，类似地从 F 到它的顶桅父 F 到 c，并将 id 存储在两个不同的数组中。现在检查两个数组中是否有共同的东西。如果常见的cn拖动，则无法拖动