Перемещение каждого узла дерева на заданную глубину

Question

У меня есть двоичное дерево, точно такое же, как семейное древо. с тем, что я называю «Ведущим ребенком» в качестве корня, с обоими родителями ниже, затем с 4 бабушками и дедушками ниже этого, а затем 8 бабушками и дедушками ниже этого. Итак, в основном двоичное дерево глубиной 4 поколения.

Я хочу, чтобы иметь возможность перемещаться по каждому узлу и извлекать информацию (то есть имя) каждого узла и хранить его в массиве - у массива, конечно, будет 15 элементов для 4 поколений (1 + 2 + 4 + 8). Я изо всех сил пытаюсь сделать это рекурсивно. Все примеры, которые я нашел в сети, которые используют обычные методы (предварительный заказ, порядок, пост-порядок), просто останавливаются при достижении пустого узла, но это НЕ то, что я хочу сделать: я хочу, чтобы каждый узел чтобы быть посещенным, но останавливаться, когда все узлы были посещены из 4-х поколений (или любого заданного количества поколений). Главное - остановиться ровно на 4 поколения, даже если некоторые из узлов пустые или Null. Может ли кто-нибудь предоставить решение, пожалуйста, ?. Это было таксировать мою голову веками Спасибо за чтение

Answer 1

Вот реализация в MIU (помирились):

traverse(node): 
    traverse_(node, 0) 

traverse_(node, i): 
    if i >= 4: 
     return 

    # Do stuff here. 

    traverese_(node.left, i + 1) 
    traverese_(node.right, i + 1) 

Теперь вам просто нужно вызвать traverse на корневом узле

.

Answer 2

Рекурсивный поиск по глубине действительно остановится, когда он достигнет листового узла, то есть узла, у которого нет детей (обратите внимание, что то, что вы можете назвать «родителями» в генеалогическом дереве, на самом деле называется «дети» «с точки зрения графика»). Однако, поскольку это рекурсивный алгоритм, «остановка» просто означает, что алгоритм вернется к узлу, из которого он пришел, и попробуйте другие дочерние элементы этого узла. Таким образом, алгоритм в целом не останавливается. Стандартный DFS, будь то префикс, инфикс или постфикс, будет посещать все дерево. Единственное, что вам нужно сделать, это добавить дополнительный параметр в рекурсивную функцию: отслеживать текущую глубину.