Итерация через древовидную структуру

Question

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

Посмотрите на следующем, это ActionScript, но это похоже на Java и т.д.:

for(var i:int=0; i<parent.children.length; i++) 
{ 
    child = parent.children[i]; 
    if(child.nodeName == "A") 
    { 
    parent = child; 
    for(var j:int=0; j<parent.children.length; j++) 
    { 
     child = parent.children[j]; 
     if(child.nodeName == "B") 
     { 
     trace("B found"); 
     parent = child; 
     //now search for C etc... 
     } 
    } 
    } 
} 

Проблема возникает с линией «родитель = ребенок», я хочу, чтобы «перепрыгнуть» в то следующий набор детей , но, конечно, когда я возвращаюсь, я потерял ссылку на родителя выше. Каков обычный способ этого?

Answer 1

Рекурсия это прекрасная вещь для деревьев:

public function walkTree(node:Tree) 
{ 
    //here is where you want to check the node's name against your list of 
    //'nodes to shout out about' 
    trace("Node found: " + node.nodeName); 


    for(var i:int=0; i < node.children.length; i++) 
    { 
     walkTree(node.children[i]); 
    } 
} 

Примечание: Рекурсия опасно, если один из детей узел может иметь своего родителя (или его родительский родитель или родительский родительский родитель и т. д.), поскольку он попадает в цикл. При использовании рекурсии убедитесь, что ни один из дочерних элементов никогда не ссылается на родительский узел.

Answer 2

Сделать рекурсивную функцию, которая будет пересекать дерево и проверять узлы?

Некоторый код:

public function traverse(parent:Node, node:Node, search:Array):void 
{ 

    if (search.indexOf(node.nodeName) != -1) 
     trace("Found " + node.nodeName); 

    for(var i:int=0; i < node.children.length; i++) 
    { 
     traverse(node,node.children[i],search); 
    } 
}