Как искать в дереве определенный класс узлов

У меня есть дерево, которое заполнено Node объектами. У каждого узла есть ArrayList, в котором хранятся его дочерние узлы, поскольку может быть неопределенное количество дочерних элементов, в отличие от двоичного дерева.

Как я могу пройти по дереву, чтобы найти конкретный узел, если у каждого узла есть несколько дочерних элементов, где у каждого дочернего элемента по очереди есть свои дочерние элементы и так далее. Я просто ищу общий способ сделать это итеративно, например, используя функцию, которая просматривает список массивов узла (хранение дочерних элементов), а также списки последующих дочерних массивов каждого ребенка.

Какие-либо предложения?

ОБНОВЛЕНИЕ

Это то, что я пробовал до сих пор:

return 
(
    (StrangeNode)current.ChildrenList
        .SingleOrDefault(c => 
            c.GetType().Name.ToString().Equals("StrangeNode"))
).myArrayList;

.net c# data-structures tree trie
person Palindrome    schedule 15.03.2012    source источник
comment
mattgemmell.com/2008/12/08/what-have-you -tried Это звучит как попытка заставить SO делать вашу домашнюю работу?   -  person Justin Pihony    schedule 15.03.2012
comment
На самом деле это не домашняя работа, я пытаюсь реализовать дерево, которое должно иметь особый тип узла в определенных точках дерева (т.е. другой класс)   -  person Palindrome    schedule 15.03.2012
comment
Он не имел в виду буквально, что ты пробовал?   -  person Louis Kottmann    schedule 15.03.2012
comment
Это то, что я пробовал до сих пор, но безрезультатно: return ((StrangeNode)current.ChildrenList.SingleOrDefault(c =› c.GetType().Name.ToString().Equals(StrangeNode))).myArrayList;   -  person Palindrome    schedule 15.03.2012

Ответы (2)


arrow_upward
0
arrow_downward

Итеративно вы можете сделать что-то вроде этого:

List<Node> nodes = new List<Node>();
nodes.add( rootnode )

for (int i=0; i < nodes.count; i++)
{

Node currentNode = nodes[i];

//do the processing to check here

nodes.add(currentNode.children) //not 100% sure how to do this, but you get the idea

}

Если вы хотите, чтобы это было сделано рекурсивно, это просто глубина, очень просто.

person Haedrian    schedule 15.03.2012
comment
Я не совсем понял это - вы говорите, что я добавляю всех дочерних элементов в массив и ищу в этом массиве «странный» узел? - person Palindrome; 15.03.2012
comment
Вот об этом. Вы проверяете текущий Node и засовываете дочерние элементы в массив. Затем вы проверяете следующий узел и также помещаете этих дочерних элементов в массив. В конце концов, вы пройдете через всех детей. - person Haedrian; 15.03.2012
comment
Однако, как это будет заботиться о детях детей? - person Palindrome; 15.03.2012
comment
Конечно, было бы. Сначала у вас будет только корневой узел. Затем вы добавляете дочерние элементы корня. Затем вы переходите к следующему узлу (Child 1) — и добавляете его дочерние элементы — и так далее. - person Haedrian; 15.03.2012

arrow_upward
0
arrow_downward

Двумя наиболее очевидными способами являются поиск в глубину и поиск в ширину. Вы можете найти примеры обоих в любом учебнике по алгоритмам или в Интернете, выполнив поиск. Вы можете реализовать этот поиск в глубину рекурсивно в 3-10 строк кода.

person tster    schedule 15.03.2012
comment
Я обновил свой вопрос тем, что пробовал до сих пор. Я хотел бы сделать это итеративно, если это возможно, а не рекурсивно. - person Palindrome; 15.03.2012
comment
какая польза делать это итеративно? - person tster; 15.03.2012
comment
На самом деле никакой пользы, я просто никогда не понимал рекурсию, хе-хе. - person Palindrome; 15.03.2012