Question sur la structure des données de l'arbre: Comment pouvons-nous remplir tous les pointeur successeur inorder de tous les nœuds de l'arbre?

Question

Le noeud de l'arbre contient 3 pointeurs * gauche, * droite et * Successeur.

Struct node{ 
    int data; 
    struct node *left; 
    struct node *right; 
    struct node *successor; 
}; 


     A 
    /\ 
     B C 
    /\/\ 
    D E F G 

afinde Traversal: DBEAFCG * Note: * A afinde successeurs F, C et G.

**Function prototype:** void FillSuccessorNodes(struct node *root); 

nœud racine de l'arbre qui nous est donnée et nous devons remplir le pointeur successeur pour tous les nœuds.

cas 1) certains des pointeurs Successeur peuvent être NULL. Dans ce cas, vous devez remplir ce pointeur avec Successeur Inorder immédiat.

Exemple: si A> Successeur == NULL, puis remplissez A> = Successeur F

cas 2) certains des pointeurs de successeur peut corriger points qui ont déjà successeurs. Ce cas Vous n'avez pas besoin de modifier les pointeurs successeurs.

Exemple: 1) A> successeur = F est valide

 2) A->successor = C is valid 

    3) A-successor = G is valid . All these three cases you no need to modify successor pointer since these already pointing to correct successor nodes. 

cas 3) Certains des pointeurs successeurs sont pas NULL mais ces pointeurs pointant vers successeurs INVALID-à-dire qu'il pourrait être afinde successeur ou une certaine valeur de déchets. Dans ce cas, vous devez remplir ces nœuds avec des nœuds successeurs immédiats.

Exemple:

 1) A->successor = B is invalid since B is not successor node , so we have to correct it to A->successor = F. 

    2) A->successor = 0x23237463478 is invalid since it is pointing to garbage value. So we we have to correct it to A->successor = F. 

1) Interviewer m'a demandé du temps solution efficace en O (n) la complexité du temps. Espace supplémentaire autorisé. 2) elle a donné un indice que nous pouvons utiliser HASHing.

Si vous connaissez la solution à ce problème, faites-le moi savoir s'il vous plaît.

Answer 1

La question et l'indice me semblent trompeurs. Puisque vous devez vérifier tous les nœuds pour vérifier si leurs successeurs ne sont pas valides, et puisque vous devez calculer le successeur pour savoir ce que signifie invalide, vous pouvez aussi utiliser une traversée O (n) standard, par exemple:

#include <utility> 
using namespace std; 

typedef pair<node*, node*> node_pair; 

node_pair setInOrderSuccessors(node* root) 
{ 
    node_pair result(root, root); 

    if (root->left) { 
     const node_pair pair = setInOrderSuccessors(root->left); 
     result.first = pair.first; 
     pair.second->successor = root; 
    } 

    if (root->right) { 
     const node_pair pair = setInOrderSuccessors(root->right); 
     result.second = pair.second; 
     root->successor = pair.first; 
    } 

    return result; 
} 

void FillSuccessorNodes(node *root) 
{ 
    const node_pair pair = setInOrderSuccessors(root); 
    pair.second->successor = 0; 
} 

Answer 2

Il ne nécessite qu'une petite modification pour traverser la traversée, vous devez rappeler le prédécesseur et définir predecessot-> successor = current.

stack<node*> s; 
node* t = root ,*pred=NULL; 
while(true) 
{ 
    if(t){ 
      s.push(t); 
      t= t->left; 
      continue; 
    }   
    if(s.empty()) { break;} 
    t= s.top(); 
    if(NULL != pred && pred->succesor != t) 
    { 
     pred->succesor = t;  
    } 
    pred = t; 
    s.pop();   
    cout<<t->c; 
    t= t->right; 
}