Печать иерархии двоичного дерева с использованием метода итеративного углубления в глубину или в ширину

Question

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

Если бы я использовал рекурсивный метод, который не просто эмулировал бы метод итеративной ширины - я бы мог / мог бы использовать итерационное углубление в глубину решение?

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

Вот код моего древовидного класса, создание которого создает древовидную структуру вызовов рекурсии функций Фибоначчи; Я изменил это так, чтобы сохранить уровень в каждом Node:

from collections import deque

class FibTree(object):
"""Class which builds binary tree from Fibonacci function call graph"""
def __init__(self, n, parent, level=None):
    if level is None:
        level = 0
    self.n = n
    self.parent = parent
    self.level = level
    if n < 2:
        self.left = None
        self.right = None
        self.value = n
    else:
        self.left = FibTree(n - 1, self, level + 1)
        self.right = FibTree(n - 2, self, level + 1)
        self.value = self.left.value + self.right.value

Реализован метод итеративного обхода шириной:

def level_order_breadth_first_traversal(self):
    """Level order Breadth First Traversal, returning nodes by level"""
    this_level = deque([self])  
    while this_level:
        next_level = deque()
        yield this_level
        while this_level:
            u = this_level.popleft()
            if u.left is not None:
                next_level.extend([u.left])
            if u.right is not None:
                next_level.extend([u.right])
        this_level = next_level

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

РЕДАКТИРОВАТЬ: чтобы показать мой обход уровня углубления в Iteratve, попытаться распечатать мое двоичное дерево в порядке уровней:

def _getChildren(self,node):
    """Method to expand node"""
    hasLeft = node.left is not None
    hasRight = node.right is not None
    if hasLeft:
        yield node.left
    if hasRight:
        yield node.right

def dls(self, node, depth):
    """Depth Limited Search"""
    if (depth == 0):
        return node
    elif (depth > 0):
        print "(" + repr(node.i) + ")" + repr(node.value),
        children = self._getChildren(node)
        for child in children:
            self.dls(child, depth-1)
    else:
        return False

def iterative_deepening(self):
    """Iterative Deepening to print out binary tree level order"""
    depth = 0
    while True:
        result = self.dls(self, depth)
        if result is not False:
            return result
        depth += 1

При вызове метода iterative_deepening просто возвращается узел root вместо списка узлов в порядке уровней.

Спасибо Alex

Answer 1

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

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

Answer 2

Вы можете выполнить свою задачу, используя любой путь.

Если у вас уже есть нерекурсивное решение, придерживайтесь его!Это лучше по памяти.Хотя BFS хранит все узлы в памяти, поэтому она слишком тяжелая для памяти (O (ветви ^ глубина)).

С DFS, которая легче в памяти (O (ветви * глубина)), вы можете пометить уровень узла в самом классе Node при прохождении узлов.Вы также можете сохранить map<level, List<Node>>, где уровень равен целому.

Если ваше дерево настолько велико, что вы не хотите идти до конца, то хорошей идеей будет использование итеративной DFS.

Answer 3

Я использовал BFS / DFS на графиках.Рассмотрим следующий график

                            v1-------------> v2-
                            |                |  -
                            |                |    -
                            |                |      -
                            |>               |>       - >
                            v4------------> v3----------> v6
                            -               |
                              -             |
                                -           |
                                  -         |>
                                    -------- > v5

В BFS вы начинаете с посещения начальной вершины v1.После посещения начальной вершины вы затем посещаете вершины, смежные с начальной вершиной.

Let us start with vertex v1.
Traverse v1.
Vertices(unvisited) adjacent to v1 are v2, v4.
Traverse v2, v4.
Vertices(unvisited) adjacent to v2 are v3, v6.
Traverse v3, v6.
Vertices(unvisited) adjacent to v4 are v5.
Traverse v5.
Vertices(unvisited) adjacent to v3 is nill.
Vertices(unvisited) adjacent to v6 is nill.
Vertices(unvisited) adjacent to v5 is nill. End.

Реализация с использованием очереди .

Algorithm: BFS(v)
1. Visit the starting vertex, v and insert it into the queue.
2. Repeat step 3 until the queue becomes empty.
3. Delete the front element from the queue. Visit all it's unvisited adjacent vertices and insert them into the queue.

If the graph is not connected then it's not possible to traverse the whole graph from a single vertex. 
So we need to execute the preceding algorithm repeatedly for all unvisited vertices in the graph.

1. Repeat step 2 for each vertex, v in the graph
2. If v is not visited:
    a. Call BFS(v)


Queue representation                    Vertices visited
--------------------------------------------------------
v1                                          v1
--------------------------------------------------------
v2 v4                                       v1, v2, v4
--------------------------------------------------------
v4 v3 v6                                    v1, v2, v4, v3, v6
--------------------------------------------------------
v3 v6 v5                                    v1, v2, v4, v3, v6, v5
--------------------------------------------------------
v6 v5                                       v1, v2, v4, v3, v6, v5
--------------------------------------------------------
v5                                          v1, v2, v4, v3, v6, v5
--------------------------------------------------------
empty                                       v1, v2, v4, v3, v6, v5
--------------------------------------------------------

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

Let us first traverse v1.
Vertices adjacent to v1 which are unvisited are v2 and v4. Let us choose v2.
Traverse v2.
Vertices adjacent to v2 which are unvisited are v3 and v6. Let us choose v3.
Traverse v3.
Vertices adjacent to v3 which are unvisited are v6 and v5. Let us choose v5.
Traverse v5.
Vertices adjacent to v5 which are unvisited are nill. So backtrack. 
Vertices adjacent to v3 which are unvisited is v6. Choose v6.
Traverse v6.
Vertices adjacent to v6 which are unvisited are nill. So backtrack. 
Vertices adjacent to v3 which are unvisited are nill. So backtrack. 
Vertices adjacent to v2 which are unvisited are nill. So backtrack. 
Vertices adjacent to v1 which are unvisited v4. Choose v4.
Traverse v4.
Vertices adjacent to v4 which are unvisited are nill. So backtrack. 
Vertices adjacent to v1 which are unvisited are nill. End. 

Реализация с использованием stack

Algorithm: DFS(v)
1. Push the starting vertex, v into the stack
2. Repeat until the stack becomes empty.
    a. Pop a vertex from stack.
    b. Visit the popped vertex.
    c. Push all the unvisited vertices adjacent to the popped vertex into the stack.

If the graph is not connected then its not possible to traverse the whole graph from a single vertex. 
So we need to execute the preceding algorithm repeatedly for all unvisited vertices in the graph.

1. Repeat step 2 for each vertex, v in the graph
2. If v is not visited:
    a. Call DFS(v)


Stack representation                    Vertices visited
--------------------------------------------------------    
    v1
--------------------------------------------------------    
    v2                                      v1      
    v4
--------------------------------------------------------
    v3                                      v1, v2
    v6
    v4
--------------------------------------------------------
    v5                                      v1, v2, v3
    v6
    v4
--------------------------------------------------------
    v6                                      v1, v2, v3, v5
    v4
--------------------------------------------------------
    v4                                      v1, v2, v3, v5, v6
--------------------------------------------------------
    empty                                   v1, v2, v3, v5, v6, v4
--------------------------------------------------------