Как построить древовидный массив неограниченной вложенности?

Question

[pomozov]

Есть 2 массива. Первый массив это родители первого уровня, а второй потомки (родитель указан в ключе 'referer' ). Как их иерархически объединить в третий, при условии, что вложенность может быть условно неограниченной?

Массив 1 (родители первого уровня):

$array1 = [
    ['page'=>'1.ru', 'title'=>'—', 'childs'=>[]],
    ['page'=>'3.ru', 'title'=>'—', 'childs'=>[]],
    ['page'=>'6.ru', 'title'=>'—', 'childs'=>[]]
];

Массив 2 (потомки):

$array2 = [
    ['page'=>'666.ru', 'title'=>'+', 'referer'=>'66.ru'],
    ['page'=>'33.ru' , 'title'=>'+', 'referer'=>'3.ru'],
    ['page'=>'66.ru' , 'title'=>'+', 'referer'=>'6.ru']
];

Массив 3 (желаемый результат):

$array3 = [
    ['page'=>'1.ru', 'title'=>'—', 'childs'=>[]],
    ['page'=>'3.ru', 'title'=>'—', 'childs'=>[
        ['page'=>'33.ru' , 'title'=>'+', 'childs'=>[]],
    ]],
    ['page'=>'6.ru', 'title'=>'—', 'childs'=>[
        ['page'=>'66.ru' , 'title'=>'+', 'childs'=>[
            ['page'=>'666.ru', 'title'=>'+', 'childs'=>[]]
        ]]
    ]]
];

Answer 1

[Alexandroppolus]

вложенность мотет быть неограниченной

выглядит так, будто у тебя бесконечно оперативы и ты хочешь куда-то её применить )))

Вот вариант за линейное время работы (из предположения, что хэш-таблица работает в среднем за О(1))
без рекурсии
на js, переведи в ПХП сам

код

const array1 = [
    {page: '1.ru', title: 'title 1'},
    {page: '3.ru', title: 'title 3'},
    {page: '6.ru', title: 'title 6'},
];

const array2 = [
    {page: '666.ru', title: 'title 666', referer: '66.ru'},
    {page: '33.ru', title: 'title 33', referer: '3.ru'},
    {page: '66.ru', title: 'title 66', referer: '6.ru'},
];

function createTree(roots, notRoots) {
    if (!roots || !roots.length) { return []; }

    const childsMap = new Map();

    // строим карту (page => список_чилдов), создавая узлы дерева для чилдов
    notRoots.forEach((child) => {
        let childs = childsMap.get(child.referer);

        if (!childs) {
            childs = [];
            childsMap.set(child.referer, childs);
        }

        childs.push({
            page: child.page,
            title: child.title,
        });
    });

    // всем чилдам (вновь созданным узлам), которые попали в карту, проставляем чилдов
    childsMap.forEach((childs) => {
        childs.forEach((child) => {
            child.childs = childsMap.get(child.page) || [];
        })
    });

    // обходим корневые элементы, создаем для них узлы дерева, подставляем чилды по карте
    return roots.map((root) => {
        return {
            page: root.page,
            title: root.title,
            childs: childsMap.get(root.page) || []
        };
    })
}

console.log(createTree(array1, array2));

Comments

[pomozov]

Попробовал, но что-то не строится это дерево(

$array1 = [
    ['page' => '1.ru', 'title' => 'title 1'],
    ['page' => '3.ru', 'title' => 'title 3'],
    ['page' => '6.ru', 'title' => 'title 6']
];

$array2 = [
    ['page' => '666.ru', 'title' => 'title 666', 'referer' => '66.ru'],
    ['page' => '33.ru', 'title' => 'title 33', 'referer' => '3.ru'],
    ['page' => '66.ru', 'title' => 'title 66', 'referer' => '6.ru']
];

function createTree($roots, $notRoots) {
    if (!isset($roots) || !count($roots)) { return []; }
    
    $childsMap = [];
    
    // строим карту (page => список_чилдов), создавая узлы дерева для чилдов    
	foreach ($notRoots as $child) {
		$childs = $childsMap[$child['referer']];
        if (!$childs) {
            $childs = [];
			$childsMap[$child['referer']] = $childs;            
        }
        $childs[] = ['page' => $child['page'], 'title' => $child['title']];
    }
    
	// всем чилдам (вновь созданным узлам), которые попали в карту, проставляем чилдов
	foreach ($childsMap as $childs) {
		foreach ($childs as $child) {
			$child['childs'] = $childsMap[$child['page']] || [];
		}
	}
    
    // обходим корневые элементы, создаем для них узлы дерева, подставляем чилды по карте    
	return array_map (function ($root) use ($childsMap) {
		return [
            'page' => $root['page'],
            'title'=> $root['title'],
            'childs'=> $childsMap[$root['page']] || []
        ];
	}, $roots);
}

print_r(createTree($array1, $array2));

[Alexandroppolus]

pomozov, я нихрена не понимаю в пхп, и не могу сказать о правильности перевода. Например, $childs[] = ['page' ...] - это ведь просто добавление в конец массива, того самого, который лежит в карте?

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

Answer 2

[65536]

Как

рекурсивно.

а связи-то у вас где хранятся? в изначальных массивах нужны идентификаторы и ссылки на родительские идентификаторы. потом надо проиндексировать их по этим ссылкам, то есть надо сделать массив где ключами будут иды, а элементами - массивы с элементами соответствующего родителя. потом рекурсивно идем сверху вниз, взяли первый уровень, листаем смотрим есть ли в том индексе элементы, ссылающиеся на текущий элемент, если есть, то погружаемся. перед подгружением нужно записать в результирующий массив данные по текущему пути. именно перед, потому что если после погружения, то вложенное затрётся. понадобится функция для записи в массывы по пути (типа такой https://laravel.su/docs/8.x/helpers#method-array-set). путём должно быть перечисление идов через спецсимвол. текущий путь можно хранить во внешней переменной, при погружении добавлять к нему сегмент с идом, в который погрузились, после погружения убирать его

Answer 3

[wadowad]

Вот такой говнокод нахрапом, но нужно добавить везде проверки:

$tree = $array1;

$array = $array2;

//вытаскивает значения из массива с детьми, и если место куда вставить ребёнка не нашлось, помещает его в конец
//Внимание! Функция войдёт в рекурсию, если места для ребёнка не найдётся - этот момент нужно фиксить
function one(array &$tree, array &$array) {
	//if (empty($array)) return false;

	$search = array_shift($array);

	$temp = $tree;

	$tree = two($tree, $search);
	if (serialize($tree) == serialize($temp)) $array[] = $search;

	if (!empty($array)) one($tree, $array);
}

//ищет куда вставить детей
function two(array $array, array $search) {
	$tree = [];

	foreach($array as $key => $value) {
		$tree[$key] = $value;

		if ($value['page'] == $search['referer']) {
			$tree[$key]['childs'][] = $search;
		} elseif (!empty($value['childs'])) {
			$tree[$key]['childs'] = two($array[$key]['childs'], $search);
		}
	}

	return $tree;
}

one($tree, $array);

var_dump($tree);

Answer 4

[Григорий Васильков]

О, моя тема.

Храним каждое дерево в двух массивах.

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

$tree = [
  // parent_id => children
  '' => [ 1, 2, 3 ],
  1 => [ 4, 5 ],
  2 => [ 6 ]
];

// нужен чтоб сохранять чилды в разных функциях и потом находить "прошлый"
$parents = [
  1 => '',
  2 => '',
  3 => '',
  4 => 1,
  5 => 1,
  6 => 2
];

Это дело обходится либо рекурсией (что медленнее), либо стеком (что быстрее).

$stack = [ [ null, 0 ] ]; // null при проверке ключа станет пустой строкой, "рутом" дерева
while ([ $parent, $level ] = array_pop($stack)) {
  // выводим текущий элемент и минусами отодвигаем от левого края или... хз в твой массив добавляем например
  echo str_repeat('--', $level) . ' ' . $parent . PHP_EOL;

  $children = $tree[ $parent ] ?? [];
  
  end($children); // да, да, в обратном порядке закидываем
  while (null !== key($children)) {
    $stack[] = [ current($children), $level + 1 ];
    prev($children);
  }
}

Этот код обходит дерево в глубину, то есть элементы в стек будут попадать таким образом null-1-2-3-4-5-6, хотя если бы ты обходил это форичем то они бы попали в виде null-1-4-5-2-6-3 (сначала бы вывелись все первые уровни, потом все вторые, потом третьи)

То есть строить "вложенное" дерево никогда не нужно. Всегда можно обойтись двумя уровнями "родитель-потомок". Существует МНОГО фронтендеров, уверенных что деревья должны быть вложенные. Книжку им в руки.

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