Построение дерева

Question

Я немного озадачен этой проблемой, и некоторое время думал об этом. У меня есть таблица в моей БД, которая содержит задачи. Каждая задача может иметь родительскую задачу, удерживая ее первичный ключ в поле parent_id. У меня нет предела тому, насколько глубоко эти задачи могут быть связаны.

+-----------+-------+-----+
| Field     | Type  | Key |
+-----------+-------+-----+
| id        | int   | PRI |
| parent_id | int   | MUL |
+-------------------+-----+

Задача без parent_id является «проектом», и все задачи могут быть сгруппированы в группы задач путем совместного использования родительской задачи. Теперь я хотел бы заполнить поле выбора HTML всеми потомками проекта.

Task 1
  -Task 1.1
  -Task 1.2
    -Task 1.2.1
    -Task 1.2.2
  -Task 1.3
Task 2

Как я могу это сделать? Я полагаю, что какая-то рекурсивная функция в порядке, но я не могу понять, как это сделать.

Любая помощь будет принята с благодарностью. :)

Answer 1

Я настоятельно рекомендую вам прочитать эту статью о хранении иерархических данных в базе данных . Здесь обсуждаются два алгоритма, и в зависимости от ваших потребностей может подойти любой из них.

Модель списка смежности

Это то, что у вас сейчас есть. Каждый узел дерева хранит ссылку на своего родителя, и вы можете рекурсивно определить путь к узлу, выбрав каждый уровень дерева и выполнив итерации по узлам. Это просто реализовать, но недостатком является то, что для определения конкретного пути к узлу требуются рекурсивные запросы. Если ваше дерево подвергается множеству изменений (например, записи), это хороший способ, так как динамический поиск каждого узла хорошо работает с постоянно меняющимся деревом. Если он тяжел для чтения, у вас есть некоторые накладные расходы в рекурсии.

Модифицированный обход дерева предзаказа

Мой любимый, это очень аккуратный алгоритм. Вместо сохранения ссылки на родителя (что вы можете сделать в любом случае для удобства), вы сохраняете ссылку на «левый» и «правый» узлы для каждого данного узла. Весь путь к узлу может быть определен в одном запросе выбора или, наоборот, для всех дочерних узлов. Алгоритм сложнее реализовать, но он имеет преимущества в производительности для деревьев с интенсивным чтением. Недостаток заключается в том, что каждый раз, когда узел перемещается или добавляется, необходимо пересчитывать целые ветви дерева, поэтому он может не подходить для наборов данных с интенсивной записью.

В любом случае, надеюсь, что эта статья даст вам некоторые идеи. Это хорошо.

Answer 2

Это пример того, как вы можете рекурсивно перемещаться по вашей базе данных для настройки формы HTML. Это реализация того, что зомбат называет «моделью списка смежности».

Используются две функции: одна просто для получения элементов «верхнего уровня» (проектов); и один рекурсивный, чтобы получить все дочерние элементы данного элемента. Затем я использую это для заполнения формы HTML.

<code><?php
/**
 * Fetches all the projects and returns them as an array.
 * "Projects" meaning: tasks without a parent.
 * @return array
 */
function getProjects() {
    $sql = "SELECT id FROM tree WHERE parentID IS NULL";
    $result = mysql_query($sql) or die(mysql_error());
    $results = array();
    while($row = mysql_fetch_assoc($result)) {
        $results[] = $row['id'];
    }
    return $results;
}

/**
 * Fetches all tasks belonging to a specific parent.
 * Adds HTML space entities to represent the depth of each item in the tree.
 * @param int $parent_id The ID of the parent.
 * @param array $data An array containing the dat, filled in by the function.
 * @param int $current_depth Indicates the current depth of the recursion.
 * @return void
 */
function getTasks($parent_id, &$data, $current_depth=1) {
    $sql = "SELECT id FROM tree WHERE parentID = {$parent_id}";
    $result = mysql_query($sql) or die(mysql_error());
    while($row = mysql_fetch_assoc($result)) {
        $data[] = str_repeat('&nbsp;', $current_depth) . '- ' . $row['id'];
        getTasks($row['id'], $data, $current_depth + 1);
    }
}


/*
 * Fetch all the data and set it up so it can be used in the HTML
 */
mysql_connect('localhost', 'usr', 'pwd');
mysql_select_db('test');

// Get all the projects, adding a "-" as the initial value of the box.
$projects = array_merge(array('-'), getProjects());

// Fetch the tasks.
// If no project has been selected, just show a "please select"
$tasks = array();
if(isset($_GET['project']) && $_GET['project'] != '-') {
    getTasks($_GET['project'], $tasks);
}
else {
    $tasks = array('Select a project');
}

mysql_close();
?>
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
    <title>Tree Select Example</title>
    <meta http-equiv="content-type" content="text/html; charset=UTF-8">
</head>
<body>
    <form action="<?php echo $_SERVER['PHP_SELF']; ?>" method="get">
        <select name="project" onchange="this.parentNode.submit();">
            <?php
            foreach($projects as $_project) {
                $selected = ($_project == @$_GET['project']) ? ' selected' : '';
                echo "<option value=\"{$_project}\"{$selected}>{$_project}</option>";
            }
            ?>
        </select><br>
        <select name="tasks[]" multiple size="10">
            <?php
            foreach($tasks as $_task) {
                echo "<option value=\"{$_task}\">{$_task}</option>";
            }
            ?>
        </select><br>
        <input type="submit">
    </form>
    <pre><?php print_r($_GET); ?>

Answer 3

, пожалуйста, включите эту функцию, чтобы иметь древовидное отображение с вашим пунктирным индикатором. я сделал для выбора опции окна.

function display_children($parent, $level) { 

    // retrieve all children of $parent 
    $output = "";
    $result = mysql_query('SELECT * FROM treeview_items  WHERE parent_id="'.$parent.'";'); 
    while ($row = mysql_fetch_array($result)) { 
        echo "<option value='".$row['id']."'>".str_repeat('--',$level).$row['name']."</option>" ."<br>"; 
        display_children($row['id'], $level+1); 
    } 
}