Не удается показать все дерево в предварительном порядке обхода в php

В моей базе данных есть таблица, в которой размещено множество генеалогических деревьев.

-----------------------------
- id  name              parent_id
-----------------------------
- 1   grandfather       NULL
- 2   father            1
- 3   uncle             1
- 4   son               2
- 5   brother           2
- 6   cousin's dauther  7
- 7   cousin            8
- 8   auntie            1

Проблема в том, что я не могу показать все имена из-за пограничного случая:

-Когда у меня есть человек с parent_id, который больше, чем parent_id его родителя (см. дочь двоюродного брата)

Я использую эти запросы для получения таблицы:

    $sql = "SELECT p1.id, p1.name, p1.parent_id FROM pariente p1 
    ORDER BY p1.parent_id";
    $result = $conn->query($sql);

Проблема в том, что если я использую «ORDER BY parent_id», «дочь двоюродного брата» не будет отображаться, а если я использую «ORDER BY id», «двоюродный брат» не будет отображаться.

Я использую эти функции, чтобы превратить дерево в массив и нарисовать его:

        function make_tree($data, $root) {
            $tree = [];
            foreach ($data as $node) {
                insert($tree, $node);
            }

            return $tree;
        }

        function insert(&$root, &$node) {
            if (!$root) {
                $root = $node;
            }
            else if ($root["id"] === $node["parent_id"]) {
                $root["children"][] = $node;
            }
            else if (array_key_exists("children", $root)) {
                foreach ($root["children"] as &$c) {
                    if (insert($c, $node)) {
                        break;
                    }
                }
            }
        }

        function preorder2(&$root) {
            if ($root) {
                echo "<li>";
                echo $root["name"];

                if (array_key_exists("children", $root)) {
                    echo "<ul>";
                    foreach ($root["children"] as $c) {
                        preorder2($c);
                    }
                    echo "</ul>";
                }
                echo "</li>";
            }
        }
    ?>

И после того, как я использую это для вызова функций:

<div>

<?php
while( $row = mysqli_fetch_assoc( $result)){
    $resguard[] = $row;
}
    $tree = make_tree($resguard);
    preorder2($tree);
?>
</div>

php database tree genealogy
person MatAle Albiach    schedule 20.08.2018    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Однажды у меня была похожая проблема, и вот как я ее исправил.

  1. Перебирайте набор данных, помещая каждый узел в свой массив, и следите за тем, что вы хотите сделать своим корневым узлом.

  2. Перебрать массив. Для каждого узла, где parent_id не равен нулю, найдите родительский узел по идентификатору и добавьте текущий узел в качестве дочернего. Нет необходимости использовать рекурсию при построении дерева.

person toastifer    schedule 20.08.2018
comment
В актуальной версии у меня в таблице более 1400 человек. Если я понимаю ваше решение, я должен сначала заполнить массив всеми корнями (parent_id = null), а после пройти через таблицу, добавив дочерние элементы к каждому узлу, уже находящемуся в таблице. Это хороший способ, но я не могу представить, как добавить все узлы, сколько раз я должен проходить через таблицу, проверяя дочерние элементы, по одному разу для каждого человека в таблице? Или какое условие я должен использовать? в первой итерации он уже добавит большую часть людей. - person MatAle Albiach; 21.08.2018
comment
Вы проходите по списку дважды. Первый помещает узел в массив с идентификатором в качестве ключа, чтобы вы могли мгновенно найти его. Во второй раз вы подключаете каждого ребенка к родителю. Не добавляйте дочерние элементы, пока каждый узел не будет найден по идентификатору. Таким образом, вы получите их все. В качестве преимущества теперь у вас также есть доступ к каждому узлу по идентификатору без необходимости поиска результатов или дерева. - person toastifer; 21.08.2018
comment
Звучит очень хорошо, но возможен ли для этой структуры предварительный обход? - person ggorlen; 21.08.2018
comment
@ggorlen Конечно! Просто сохраните ссылку/указатель на корневой узел, а затем посетите текущий узел, а затем дочерние элементы по порядку. - person toastifer; 21.08.2018

arrow_upward
0
arrow_downward

В конце концов, я считаю, что не получил ответа на тостификатор, но это заставило меня задуматься, и в итоге я решил проблему (все еще используя способ, которым ggorlen показывает дерево).

Сначала это запросы:

$sql = "SELECT p1.id, p2.name, p2.id as minor, p2.name FROM pariente p1 INNER JOIN pariente p2 ON p1.id = p2.parent_id ORDER BY p1.id";
$result = $conn->query($sql);

$sql2 = "SELECT p1.id, p1.nombre, p1.padre_id FROM pariente p1 WHERE p1.padre_id IS NULL ORDER BY p1.id";
$raices = $conn->query($sql2);

Функции:

        function make_tree($resguardo, $root){
            $tree = [];
            $tree = $root;
            foreach ($resguardo[$root["id"]] as $node) {
                add($tree, $node, $resguardo);
            }
            return $tree;
        }

        function add(&$root, &$children, $resguardo){
            $root["children"][$children["minor"]] = $children;

            $flag= false;
            if (isset($resguardo[$children["minor"]])) {
                $flag = true;
            }

            if ($flag == false){
                return;
            } else {
                foreach ($resguardo[$children["minor"]] as $child) {
                    agregar($root["children"][$children["minor"]], $child, $resguardo);
                }
            }
        }

        function preorder2(&$root) {
            if ($root) {
                echo "<li>";
                echo '<a href="">';
                echo $root["name"];
                echo "</a>";

                if (array_key_exists("children", $root)) {
                    echo "<ul>";
                    foreach ($root["children"] as $c) {
                        preorder2($c);
                    }
                    echo "</ul>";
                }
                echo "</li>";
            }
        }

И я называю их здесь:

while( $row = mysqli_fetch_assoc($result)){
    $resguardo[$row["id"]][] = $row;
}
    while( $root = mysqli_fetch_assoc( $roots)){
    echo '<ul>';
    $tree = make_tree($resguardo, $root);
    preorder2($tree);
    echo "</ul>";
}

Большое спасибо вам обоим, я бы никогда не решил это без вашей помощи.

person MatAle Albiach    schedule 25.08.2018