При обходе дерева породите сначала
У нас есть тот же сценарий - связь WCF к серверу, сервер использует LINQtoSQL.
Мы используем.ToArray () при запросе объектов с сервера, потому что это "недопустимо" для клиента для изменения списка. (Значение, нет никакой цели поддерживать ".Add", ".Remove", и т.д.).
, В то время как все еще на сервере, однако, я рекомендовал бы оставить его, поскольку это - значение по умолчанию (который не является IEnumerable, а скорее IQueryable). Таким образом, если Вы хотите отфильтровать еще больше на основе некоторых критериев, фильтрация, ВСЕ ЕЩЕ на стороне SQL, пока не оценено.
Это - очень важный момент, поскольку это означает невероятное увеличение производительности или потери в зависимости от того, что Вы делаете.
ПРИМЕР:
// This is just an example... imagine this is on the server only. It's the
// basic method that gets the list of clients.
private IEnumerable<Client> GetClients()
{
var result = MyDataContext.Clients;
return result.AsEnumerable();
}
// This method here is actually called by the user...
public Client[] GetClientsForLoggedInUser()
{
var clients = GetClients().Where(client=> client.Owner == currentUser);
return clients.ToArray();
}
Вы видите то, что происходит там? Метод "GetClients" собирается вызвать загрузку ВСЕХ 'клиентов' от базы данных... ТОГДА оператор Where, окажется, в методе GetClientsForLoogedInUser отфильтрует его.
Теперь, заметьте небольшое изменение:
private IQueryable<Client> GetClients()
{
var result = MyDataContext.Clients;
return result.AsQueryable();
}
Теперь, фактической оценки не произойдет, пока ".ToArray" не называют..., и SQL сделает фильтрацию. НАМНОГО лучше!
10 ответов
Псевдокод:
NodesToVisit = some stack or some list
NodesToVisit.Push(RootNode)
While NodesToVisit.Length > 0
{
CurNode = NodesToVisit.Pop()
For each Child C in CurNode
NodesToVisit.Push(C)
Visit(CurNode) (i.e. do whatever needs to be done)
}
Изменить : Рекурсивный или нет?
To be technically correct, and as pointed out by AndreyT and others in this post, this approach is a form of a recursive algorithm, whereby an explicitly managed stack is used in lieu of the CPU stack and where the recursion takes place at the level of the While loop. This said, it differs from a recursive implementation per se in a couple of subtle yet significant ways:
- Only the "variables" are pushed onto the stack; there is no "stack frame" and associated return address on the stack, the only "return address" is implicit to the while loop, and there is but one instance of it.
- The "stack" could be used as a list whereby the next "frame" could be taken anywhere in the list, without braking the logic in any way.
Если у вас есть ссылки на всех потомков, а также на родителя, то нерекурсивный алгоритм довольно тривиален. Просто забудьте, что у вас есть дерево. Подумайте об этом как о лабиринте, где каждая связь родитель-потомок представляет собой обычный двунаправленный коридор от одного перекрестка до другого. Все, что вам нужно сделать, чтобы пройти весь лабиринт, - это свернуть в следующий коридор слева на каждом перекрестке. (В качестве альтернативы представьте себе, что вы идете по лабиринту, всегда касаясь левой рукой стены с левой стороны). Если вы начнете от корневого соединения (и будете двигаться в любом направлении), вы пройдете все дерево, всегда посещая родителей раньше детей. Каждый «коридор» в этом случае будет пройден дважды (в одном направлении и в другом), и каждый «перекресток» (узел) будет посещен во столько раз, сколько «коридоров»
Вы ищете обход предварительного заказа. Я думаю, вы можете сделать это нерекурсивно с помощью очередь:. В псевдокоде:
Создайте пустую очередь, затем нажмите корневой узел.
while nonempty(q)
node = pop(q)
visit(node)
foreach child(node)
push(q,child)
Использовать набор узлов. Ставим рут в комплект для запуска. Затем в цикле вытащите узел из набора, посетите его, а затем поместите его дочерние элементы в набор. Когда набор пуст, все готово.
В псевдокоде:
currentList = list( root )
nextList = list()
while currentList.count > 0:
foreach node in currentList:
nextList.add(node.children)
currentList = nextList
I would disagree with breadth first search as space complexity is often the bane of that specific search algorithm. Possibly using the iterative deepening algorithm is a better alternative for this type of use, and it covers the same type of traversal as breadth first search. There are minor differences in dealing with the fringe from breadth-first search, it shouldn't be too hard to (pseudo) code out though.
Вот действительно нерекурсивный подход: без стека, постоянное пространство. Этот код Python предполагает, что каждый узел содержит список дочерних узлов и что объекты узла не определяют равенство, так что функция 'index' сравнивает идентичности:
def walkTree(root, visit_func):
cur = root
nextChildIndex = 0
while True:
visit_func(cur)
while nextChildIndex >= len(cur.children) and cur is not root:
nextChildIndex = cur.parent.children.index(cur) + 1
cur = cur.parent
if nextChildIndex >= len(cur.children):
break
cur = cur.children[nextChildIndex]
nextChildIndex = 0
Я уверен, что это можно немного улучшить, сделать лаконичнее и легче читается, но в этом суть.
Если вы начинаете с корневого узла и посещаете только родительские / дочерние узлы, которые вы уже посетили, нет способа пройти по дереву так, чтобы вы посетили узел перед посещением его предков.
Подойдет любой вид обхода, сначала в глубину (рекурсивный / на основе стека), в ширину (на основе очереди), с ограничением глубины или просто извлекая их из неупорядоченного набора.
] «Лучший» метод зависит от дерева. Сначала ширина будет хорошо работать для очень высокого дерева с небольшим количеством ветвей. Сначала глубина будет хорошо работать для деревьев с множеством ветвей.
Поскольку узлы на самом деле имеют указатели на своих родителей, существует также алгоритм постоянной памяти, но он намного медленнее.
Build up a list of nodes at the root (level 0), iterate over each node in turn and look for direct children (whose parent node is the node we are currently looking from) (level 1), when finished with level 0 move on to iterating level 1, and so on until you have no remaining unvisited nodes.