Для начала этот вопрос не является дубликатом этого, но основывается на нем.
Взятие дерева в том вопросе как пример,
1
/ \
2 3
/ / \
4 5 6
Как Вы изменили бы свою программу для печати его так,
1
2 3
4 5 6
вместо генерала
1
2
3
4
5
6
Я в основном ищу интуиции на самом эффективном способе сделать это - у меня есть вовлечение метода, добавляющее результат к списку и затем цикличное выполнение через него. Более эффективный путь мог бы состоять в том, чтобы сохранить последний элемент на каждом уровне, поскольку он выталкивается, и распечатайте новую строку позже.
Идеи?
Just build one level at a time, e.g.:
class Node(object):
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def traverse(rootnode):
thislevel = [rootnode]
while thislevel:
nextlevel = list()
for n in thislevel:
print n.value,
if n.left: nextlevel.append(n.left)
if n.right: nextlevel.append(n.right)
print
thislevel = nextlevel
t = Node(1, Node(2, Node(4, Node(7))), Node(3, Node(5), Node(6)))
traverse(t)
Edit: if you're keen to get a small saving in maximum consumed "auxiliary" memory (never having simultaneously all this level and the next level in such "auxiliary" memory), you can of course use collection.deque
instead of list
, and consume the current level as you go (via popleft
) instead of simply looping. The idea of creating one level at a time (as you consume --or iterate on-- the previous one) remains intact -- when you do need to distinguish levels, it's just more direct than using a single big deque plus auxiliary information (such as depth, or number of nodes remaining in a given level).
However, a list that is only appended to (and looped on, rather than "consumed") is quite a bit more efficient than a deque (and if you're after C++ solutions, quite similarly, a std::vector using just push_back
for building it, and a loop for then using it, is more efficient than a std::deque). Since all the producing happens first, then all the iteration (or consuming), an interesting alternative if memory is tightly constrained might be to use a list anyway to represent each level, then .reverse
it before you start consuming it (with .pop
calls) -- I don't have large trees around to check by measurement, but I suspect that this approach would still be faster (and actually less memory-consuming) than deque
(assuming that the underlying implementation of list [[or std::vector]] actually does recycle memory after a few calls to pop
[[or pop_back
]] -- and with the same assumption for deque, of course;-).
A version that doesn't require extra storage:
std::deque<Node> bfs;
bfs.push_back(start);
int nodesInThisLayer = 1;
int nodesInNextLayer = 0;
while (!bfs.empty()) {
Node front = bfs.front();
bfs.pop_front();
for (/*iterate over front's children*/) {
++nodesInNextLayer;
nodes.push_back(child);
}
std::cout << node.value;
if (0 == --nodesInThisLayer) {
std::cout << std::endl;
nodesInThisLayer = nodesInNextLayer;
nodesInNextLayer = 0;
} else {
std::cout << " ";
}
}
P.S. sorry for the C++ code, I'm not very fluent in Python yet.
Sounds like breadth-first traversal to me.
Breadth-first traversal is implemented with a queue. Here, simply insert in the queue a special token that indicate that a newline must be printed. Each time the token is found, print a newline and re-insert the token in the queue (at the end -- that's the definition of a queue).
Start the algorithm with a queue containing the root followed by the special newline token.