Comment afficher la position actuelle d'un nœud d'arbre

Question

J'ai une mise en œuvre de la structure de l'arbre qui ressemble à ceci:

class Node { 

    let value: String 

    var parentNode: Node? 
    var childenNode = [Node]() 

    func appendNode(node: Node) { 
     childenNode.append(node) 
     node.parentNode = self.parentNode 
    } 

    func isLeaveNode(node: Node) -> Bool{ 
     if node.childenNode.isEmpty { 
      return true 
     } else { 
      return false 
     } 
    } 

    init(value: String) { 
     self.value = value 
    } 
} 

Je veux avoir une fonction qui retourne le chemin qu'il a fallu pour arriver au noeud courant . Par exemple: disons que j'ai un noeud de congé node et le chemin qu'il a fallu pour arriver à ce noeud de congé est Main Menu -> Setting -> User Options -> Set User Options, alors je veux une fonction qui retourne ce chemin: E.g. func path(node: Node) -> path. Comment puis-je l'implémenter?

J'ai essayé d'utiliser une boucle for-in pour effectuer une boucle dans le nœud parent. Cependant, depuis Node n'est pas conforme au protocole sequence, cela ne peut pas être fait.

Merci beaucoup! Toute aide est la bienvenue!

Answer 1

Vous pouvez définir une fonction récursive itère à travers les nœuds en utilisant parentNode jusqu'à ce qu'il atteigne la racine comme ceci:

func getPath()->[Node]{ 
    return self.parentNode == nil ? [self] : [self] + self.parentNode!.getPath() 
} 

Je l'ai testé en utilisant l'exemple suivant:

let grandParent = Node(value: "grand") 
let parent = Node(value: "parent") 
parent.parentNode = grandParent 
let child = Node(value: "child") 
child.parentNode = parent 
child.getPath() //returns [grandParent, parent, child] 

L'opérateur ternaire dans la fonction est juste raccourci pour

func getPath()->[Node]{ 
    if self.parentNode == nil { 
     return [self] 
    } else { 
     return [self] + self.parentNode!.getPath() //this is the recursive call 
    } 
} 

self.parentNode == nil signifie que nous avons trouvé le nœud racine, donc c'est le cas de base de l'appel récursif, nous devons juste retourner la valeur actuelle. Si self.parentNode != nil, cela signifie que nous sommes sur un nœud enfant, la valeur de retour sera un tableau du nœud actuel + le résultat de l'appel récursif.

Answer 2

Si la récursivité est nouvelle pour vous, vous pouvez également essayer une approche itérative. En suivant la réponse de David.

func getPath() -> [Node] { 
    var currentNode = self 
    var path: [Node] = [] 
    while currentNode != nil { 
    path += [currentNode] 
    currentNode = currentNode.parentNode 
    } 
    return path 
}