Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > PHP: Общие вопросы > Помогите составить дерево

Автор: Igor_K 16.4.2008, 21:13

Всем привет!

У меня возникли трудности с составлением дерева. Не могу сообразить, ума не хватает :(((
Есть массив:

Код


$arr = array
(
    array(1, 0, 'Элемент № 1'),
    array(2, 1, 'Элемент № 2'),
    array(3, 2, 'Элемент № 3'),
    array(4, 3, 'Элемент № 4'),
    array(5, 2, 'Элемент № 5'),
    array(6, 3, 'Элемент № 6'),
    array(7, 1, 'Элемент № 7'),
    array(8, 2, 'Элемент № 8'),
    array(9, 1, 'Элемент № 9'),
    array(10, 1, 'Элемент № 10')
);

где внутренние массивы имеют вид array(идентификатор, родитель, значение)

нужно его преобразовать в массив такого вида:

Код


$aarr = array
(
    'Элемент № 1',
    array
    (
        'Элемент № 2',
        array
        (
            'Элемент № 3',
            array
            (
                'Элемент № 4',
                'Элемент № 6'
            ),
            'Элемент № 5',
            'Элемент № 8'
        ),
        'Элемент № 7',
        'Элемент № 9',
        'Элемент № 10'
    )
);

то есть создать такое от дерево. Только ума не хватает, подскажите пожалуйста! smile

Советом, или ссылками.

Автор: GZep 16.4.2008, 21:53

Igor_K, тебе нужна функция, которая бы принимала 1й вариант и возвращала второй?

Автор: Igor_K 16.4.2008, 22:05

GZep, можно и функцию, можно и на словах обьяснить. smile

Я уже и так исяк, но не получается :(

Автор: almagnit 16.4.2008, 22:16

Если с операторами РНР у Вас все в порядке, тогда используте алгоритм:

1. Нужно узнать сколько нужно различных массивов для построения дерева, в Вашем случае нужно

четыре массива на это указывают их номера "0,1,2,3" в значениях массива arr.

2. Создаем массив с требуемым количеством элементов, либо нужное количество отдельных массивов

и присваиваем его n-ой ячейке, либо n-му массиву - элементы массива arr с соответствующими

значениями, т.е. в нулевую ячейку, либо в нулевой массив мы добавляем строку 'Элемент №1' и т.д.

3. Формируем массив aarr из полученного промежуточного массива или массивов

Автор: Fortop 16.4.2008, 22:46

Цитата(almagnit @ 16.4.2008, 22:16

)

ужно узнать сколько нужно различных массивов для построения дерева, в Вашем случае нужно
четыре массива на это указывают их номера "0,1,2,3" в значениях массива arr.

Вообще-то нужен всего 1 массив.

Автор: Igor_K 16.4.2008, 22:47

almagnit, спасибо большое!!! smile

Цитата(almagnit @ 16.4.2008, 22:16

)

3. Формируем массив aarr из полученного промежуточного массива или массивов

Только от с этим не очень понял. Допустим получил 4 массива, как их соединить правильно? То есть поместить в нужную позицию.
Например, от, получил:

Код


$ar = array
(
    array
    (
        'Элемент № 1'
    ),
    array
    (
        'Элемент № 2',
        'Элемент № 7',
        'Элемент № 9',
        'Элемент № 10'
    ),
    array
    (
        'Элемент № 3',
        'Элемент № 5',
        'Элемент № 8'
    ),
    array
    (
        'Элемент № 4',
        'Элемент № 6'
    )
);

Автор: GZep 16.4.2008, 22:54

Igor_K, что-то мне подсказывает, что для решения вопроса нужно увидеть причину для такой сортировки массива. Может на конкретном примере? (вероятно, может получиться более простой способ решения реальной проблемы).

Автор: skyboy 16.4.2008, 23:26

в каждом элементе объяви ещё один элемент массива - типа, children(к примеру).
тогда будет проще собрать дерево:

Код


$arr = array
(
    array(1, 0, 'Элемент № 1', array()),
    array(2, 1, 'Элемент № 2', array()),
    array(3, 2, 'Элемент № 3', array()),
    array(4, 3, 'Элемент № 4', array()),
    array(5, 2, 'Элемент № 5', array()),
    array(6, 3, 'Элемент № 6', array()),
    array(7, 1, 'Элемент № 7', array()),
    array(8, 2, 'Элемент № 8', array()),
    array(9, 1, 'Элемент № 9', array()),
    array(10, 1, 'Элемент № 10', array())
);
$root= null;
foreach($arr AS $key => $element) 
{
  if($element[1] == 0)
    $root= &$arr[$key];
  else
   $arr[$element[1] - 1][3][]= &$arr[$key];
}
print_r($root);

после сей операции у тебя получится не совсем то, что ты описал(из-за дополнительных элементов), но по полученной структуре пройтись вполне можно будет.
ещё я бы сделал ассоциативный массив(id, parent, name, chidren), а то обращение

Код


$root['children'][4]['children'][2]['name']

понятнее, чем

Код


$root[3][4][3][2][2]

вот пример вывода:

Код


Array
(
    [0] => 1
    [1] => 0
    [2] => Элемент № 1
    [3] => Array
        (
            [0] => Array
                (
                    [0] => 2
                    [1] => 1
                    [2] => Элемент № 2
                    [3] => Array
                        (
                            [0] => Array
                                (
                                    [0] => 3
                                    [1] => 2
                                    [2] => Элемент № 3
                                    [3] => Array
                                        (
                                            [0] => Array
                                                (
                                                    [0] => 4
                                                    [1] => 3
                                                    [2] => Элемент № 4
                                                    [3] => Array
                                                        (
                                                        )
                                                )
                                            [1] => Array
                                                (
                                                    [0] => 6
                                                    [1] => 3
                                                    [2] => Элемент № 6
                                                    [3] => Array
                                                        (
                                                        )
                                                )
                                        )
                                )
                            [1] => Array
                                (
                                    [0] => 5
                                    [1] => 2
                                    [2] => Элемент № 5
                                    [3] => Array
                                        (
                                        )
                                )
                            [2] => Array
                                (
                                    [0] => 8
                                    [1] => 2
                                    [2] => Элемент № 8
                                    [3] => Array
                                        (
                                        )

                                )
                        )
                )
            [1] => Array
                (
                    [0] => 7
                    [1] => 1
                    [2] => Элемент № 7
                    [3] => Array
                        (
                        )
                )

            [2] => Array
                (
                    [0] => 9
                    [1] => 1
                    [2] => Элемент № 9
                    [3] => Array
                        (
                        )
                )

            [3] => Array
                (
                    [0] => 10
                    [1] => 1
                    [2] => Элемент № 10
                    [3] => Array
                        (
                        )
                )
        )
)

Автор: SelenIT 17.4.2008, 00:29

Имхо, для исходной задачи так немного нагляднее:

Код


// сортируем исходный массив так,
// чтобы предки гарантированно шли впереди потомков
// (чтобы не потерять ни одной ветки)
function cmp($a,$b) {
    if ($a[1]!=$b[1]) return $a[1] - $b[1];
    else return $a[0] - $b[0];
}
usort($arr, "cmp");

// запоминаем ID-ы непустых ветвей (в ключах массива, для быстроты)
foreach ($arr as $elem) {
    $subtrees[$elem[1]] = 1;
}

// "вешаем" элементы на дерево
// если у элемента есть поддерево -
// создаем соотв. массив и вешаем ссылку на него сразу после самого эл-та
foreach($arr as $elem) {
    $tree[$elem[1]][] = $elem[2];
    if (isset($subtrees[$elem[0]])) {
        $tree[$elem[0]] = &$tree[$elem[1]][];
    }
}

// выводим полное дерево для корневого элемента
print_r($tree[0]);

Цитата(Igor_K @ 16.4.2008, 22:47

)

Допустим получил 4 массива, как их соединить правильно? То есть поместить в нужную позицию.

Лучше всего сделать этот массив ассоциативным:

Код


$ar = array
(
    0 => array
    (
        1 => 'Элемент № 1'
    ),
    1 => array
    (
        2 => 'Элемент № 2',
        7 => 'Элемент № 7',
        9 => 'Элемент № 9',
        10 => 'Элемент № 10'
    ),
    2 => array
    (
        3 => 'Элемент № 3',
        5 => 'Элемент № 5',
        8 => 'Элемент № 8'
    ),
    3 => array
    (
        4 => 'Элемент № 4',
        6 => 'Элемент № 6'
    )
);

Тогда из самого массива сразу станет ясно, что к чему привязывать smile

. Кстати, если эта структура берется из базы, можно сразу получать ее в таком виде.

skyboy, в первом примере круто повезло, что айдишники идут по порядку, начиная с единицы;)

Автор: skyboy 17.4.2008, 00:49

Цитата(SelenIT @ 16.4.2008, 23:29

)

skyboy, в первом примере круто повезло, что айдишники идут по порядку, начиная с единицы;)

полный вариант: "круто повезло, что индекс в массиве совпадает со значением id - 1" ;)
етественно, лучше было бы, если бы индексом элемента в начальном массиве был бы сам id. тогда бы и единицу не прилось бы вычитать.
и если бы элементы юыли бы ассоциативным массивом, было бы удобнее и т.д..

Автор: SelenIT 17.4.2008, 00:54

Цитата(skyboy @ 17.4.2008, 00:49

)

полный вариант: "круто повезло, что индекс в массиве совпадает со значением id - 1" ;)

Да, именно это я имел в виду smile

Автор: skyboy 17.4.2008, 01:18

чтоб не париться, можно положить, что исходный массив может быть только таким и модификацию производить собственными силами:

Код


$arr=... // заполнение массива
$result= array();
foreach($arr AS $value) // преобразование массива
{
  $result[$value[0]]= array('id'=> $value[0],'parent'=> $value[1], 'name'=> $value[2], 'children'=> array());
}
$root= null;
foreach($result AS $key => $element) 
{
  if($element['parent'] == 0)
    $root= &$result[$key];
  else
   $result[$element['parent']]['children'][$element['id']]= &$result[$key];
}
print_r($root);

все же, как мне кажется, сортировка в решении будет лишней. у нас и так для ассоциативного массива хеш строится...
P.S. Да, мой код похож на код SelenIT'a, но, чесное слово, не плагиатил, а доработал smile

Автор: SelenIT 17.4.2008, 01:34

Цитата(skyboy @ 17.4.2008, 01:18

)

как мне кажется, сортировка в решении будет лишней. у нас и так для ассоциативного массива хеш строится...

Да, вариант с хешем однозначно лучше smile

. И ссылки на элементы исходного массива красивее, чем мой вариант внутренних ссылок во вспомогательном массиве. А заодно и зависимость от порядка ветвей убирается smile

Автор: Igor_K 17.4.2008, 16:17

Спасибо большое!!!!! smile

Щяс буду пробовать ваши варианты. smile

Автор: Igor_K 17.4.2008, 17:23

Цитата(SelenIT @ 17.4.2008, 00:29

)

Кстати, если эта структура берется из базы, можно сразу получать ее в таком виде.

Да, из базы данных. а как ее получить в таком виде?

Автор: DeamonShan 17.4.2008, 17:51

Код


function doTree($id){
global $arr;
 $res=query("select * from table where parent_id=$id");

 while ($str=fetchrow($res)){
  array_push($arrTmp,$str['element']);
  doTree($str['id']);
 }
  array_push($arr,$arrTmp);
}

doTree(0);
print_r ($arr);

в случае если из БД берется...

Автор: DeamonShan 17.4.2008, 18:08

не тестировал...

Автор: SelenIT 17.4.2008, 19:06

Цитата(Igor_K @ 17.4.2008, 17:23

)

а как ее получить в таком виде?

Общий принцип примерно http://forum.vingrad.ru/index.php?showtopic=147526&view=findpost&p=1188785 (вся соль в строке 22;).

В том примере дерево строится рекурсивной ф-цией, но можно применить подход skyboyя со ссылками...

Автор: Igor_K 18.4.2008, 13:07

SelenIT, Спасибо за помощь!!! Разобрался. smile

DeamonShan, тоже спасибо, но имхо в каждой итерации делать запрос в базу данныых не хочется ;)

Автор: Igor_K 18.4.2008, 13:27

Добавьте кто-то всем отписавшимся тут плюсики, у меня постов не хватает smile

спасибо!

Автор: fics 30.3.2009, 23:13

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

кусочек из одного моего класса. $node["level"] - дополнительное поля уровня вложенности
сразу в сессию пишу чтобы не ганять такой тяжелый скрипт

Код



public function build_tree($par) {
       $result = mysql_query("select * from categories where parentid = ".$par);
            
        while($node = mysql_fetch_array($result)) {
                  
           $record = array($node["categoryid"], $node["parentid"], $node["categoryname"],
                            $node["level"]);
                     
           $_SESSION["tree"][] = $record;                
           $this->build_tree($node["categoryid"]);
                }
            
      return true;      
  }

Автор: Igor_K 3.5.2009, 15:52

fics, такой подход не очень. 100 вложений - 100 запросов.

Опять я вернулся к этому вопросу. Тему создал по этому поводу получения данных из таблицы http://forum.vingrad.ru/forum/topic-257734.html

Вернулся к этому вопросу спустя год, не довел тогда роботу до конца.

Автор: MoLeX 4.5.2009, 05:34

Цитата(Igor_K @ 3.5.2009, 15:52

)

00 вложений - 100 запросов.

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

Автор: LittleFuntik 16.6.2009, 00:39

Вот держи мое решение, http://forum.vingrad.ru/forum/topic-263175/kw-php-list-treeview.html!!!
И всего-лишь ОДИН ЗАПРОС к БД

Автор: capitan 11.9.2009, 12:51

Недавно как раз работал с деревом каталога. Из всех вариантов выбрал, как считаю, самый оптимальный.
"Дерево каталогов NESTED SETS (вложенные множества) и управление им "
http://www.getinfo.ru/article610.html

Все остальные варианты хороши на маленьких объёмах. При польших объёмах, скрипты еле ворочаются.

Автор: deperoff 12.2.2012, 12:01

Код


$result=mysql_query("SELECT id, parent_id, title FROM tree");
$cats = array();
while($cat =  mysql_fetch_assoc($result))
        $cats[$cat['parent_id']][] =  $cat;
 
function  build_tree($cats,$parent_id){
if(is_array($cats) and count($cats[$parent_id])>0){
$tree = '<ul>';
 foreach($cats[$parent_id] as $cat){
  $tree .= '<li>'.$cat['title'];
 $tree .=  build_tree($cats,$cat['id']);
  $tree .= '</li>';         
 }
 $tree .= '</ul>';
  } 
  else return null;          
  return $tree; 
}
echo build_tree($cats,0); // :)))

Вот http://php-include.ru/stati/ierarkhicheskoe-derevo-na-php))

Автор: xPchelkiNx 9.8.2012, 16:01

Цитата(Igor_K @ 17.4.2008, 17:23)

Цитата(SelenIT @ 17.4.2008, 00:29

)

Кстати, если эта структура берется из базы, можно сразу получать ее в таком виде.

Да, из базы данных. а как ее получить в таком виде?
и мне это интересно!!!

Автор: Genn 26.8.2012, 22:45

эта структура таблицы легко реализуется

id
id_parent
name

потом foreach и всех делов