Droite Threading un arbre binaire

Je vais avoir un sacré temps à essayer de comprendre celui-ci. Partout où je regarde, il me semble que je ne trouve que des explications sur la façon de traverser la liste de façon non récursive (la partie que je comprends). Quelqu'un peut-il marteler comment exactement je peux parcourir la liste au départ et trouver les nœuds prédécesseur/successeur réels afin que je puisse les marquer dans la classe de nœud? Je dois être capable de créer un arbre de recherche binaire simple et parcourir la liste et rediriger les liens nuls vers le prédécesseur/successeur. J'ai eu un peu de chance avec une solution un peu comme ce qui suit:Droite Threading un arbre binaire

thread(node n, node p) { 
    if (n.left !=null) 
     thread (n.left, n); 
    if (n.right !=null) { 
     thread (n.right, p); 
    } 
    n.right = p; 
}

Source

2009-07-29 Anonymous

trouver les nœuds prédécesseur/successeur? est-ce la même chose que le parent et les enfants? Pourquoi créez-vous un arbre avec des trous? – nlucaroni

Pour clarifier pour quelqu'un d'autre qui n'a pas entièrement saisi votre question, je suppose que vous essayez de lier chaque nœud d'un arbre binaire à son prédécesseur et successeur en ordre (comme décrit ici: http: //en.wikipedia. org/wiki/Threaded_binary_tree), n'est-ce pas? – Suppressingfire

D'après votre description, je suppose que vous avez un nœud avec une structure ressemblant à quelque chose comme:

Node { 
    left 
    right 
}

... et que vous avez un arbre binaire de ces configurations en utilisant la gauche et la droite, et que vous voulez réattribuer des valeurs à gauche et à droite de sorte qu'il crée une liste à liaison double à partir d'une première traversée en profondeur de l'arbre.

La racine (sans jeu de mots) problème avec ce que vous avez jusqu'à présent est que le "noeud p" (court pour précédent?) Qui est passé pendant la traversée doit être indépendant de l'endroit où dans l'arbre vous actuellement sont - il doit toujours contenir le nœud précédemment visité. Pour ce faire, chaque fois que le thread est exécuté, il doit référencer la même variable "précédente". J'ai fait du pseudo code Python-ish avec un C-ism - si vous n'êtes pas familier, '&' signifie "référence à" (ou "ref" en C#), et "*" signifie "déréférencement et donnez-moi l'objet qu'il pointe ".

Node lastVisited 
thread(root, &lastVisisted) 

function thread(node, lastVisitedRef) 
    if (node.left) 
    thread(node.left, lastVisitedRef) 
    if (node.right) 
    thread(node.right, lastVisitedRef) 

    // visit this node, reassigning left and right 
    if (*lastVisitedRef) 
    node.right = *lastVisitedRef 
    (*lastVisitedRef).left = node 
    // update reference lastVisited 
    lastVisitedRef = &node

Si vous allez implémenter dans C, vous aviez réellement besoin d'un double pointeur pour maintenir la référence, mais l'idée est la même - vous devez conserver l'emplacement du « dernier nœud visité » pendant toute la traversée.

Source

2009-07-31 04:36:04

Droite Threading un arbre binaire

Répondre

Questions connexes