1
votes

Plus petit ancêtre commun de deux feuilles dans un arbre

J'ai l'arborescence suivante:

std::vector<Node*> ancestors1;
std::vector<Node*> ancestors2;
temp_node = node1->parent;
while(temp_node!=nullptr) {
    ancestors1.push_back(temp_node);
    temp_node = temp_node->parent;
}
temp_node = node2->parent;
while(temp_node!=nullptr) {
    ancestors2.push_back(temp_node);
    temp_node = temp_node->parent;
}
Node* common_ancestor = nullptr;
if (ancestors1.size() < ancestors2.size()) {
    ptrdiff_t t = ancestors1.end() - ancestors1.begin();
    std::vector<Node*>::iterator it1 = ancestors1.begin();
    std::vector<Node*>::iterator it2 = ancestors2.end() - t;
    while(it1!=ancestors1.end()) {
        if (*it1 == *it2) {
            common_ancestor = *it1;
        }
        ++it1;
    }
} else {
    ptrdiff_t t = ancestors2.end() - ancestors2.begin();
    std::vector<Node*>::iterator it2 = ancestors2.begin();
    std::vector<Node*>::iterator it1 = ancestors1.end() - t;
    while(it2!=ancestors2.end()) {
        if (*it1 == *it2) {
            common_ancestor = *it1;
        }
        ++it2;
    }
}
return common_ancestor

Où chaque nœud a au plus un parent mais peut avoir plusieurs enfants. J'essaie de trouver le plus petit ancêtre commun de deux nœuds (node1 et node2) qui n'ont pas d'enfants.

Voici mon code actuel:

struct Node {
   int data;
   Node* parent = nullptr;
}

Ce code ne fonctionne pas toujours et je ne sais pas pourquoi.

algorithm c++ tree

10 commentaires

Essayez de créer l'arborescence la plus petite et la plus simple qui "ne fonctionne pas toujours", et utilisez un débogueur pour parcourir le code afin de déterminer quel pourrait être le problème.

Créez une fonction pour lister les ancêtres au lieu de répéter la logique. Vous avez typo btw, comme vous mettez les ancêtres de node2 dans ancestors1

Une seule itération se déplace, vous ne recherchez donc qu'un seul ancêtre.

faites simplement ++ it1; ++ it2; dans les deux côtés des blocs if-else.

Merci pour le conseil. J'ai corrigé le problème de l'itérateur, mais c'est toujours un peu faux. J'essaie de faire ce que @Some programmeur a dit, mais le test qui ne fonctionne pas est très compliqué.

it2 = ancestors2.end () - t - pourquoi? les deux chemins doivent commencer à partir de la racine. Ne pourriez-vous pas simplement parcourir les deux chemins depuis le début et sortir dès qu'ils diffèrent?

@ 500 - Erreur de serveur interne Je veux parcourir les deux chemins en même temps, ce qui ne fonctionne que si l'itérateur pointe vers deux nœuds de même hauteur, car l'ancêtre commun le plus bas est évidemment à la même hauteur que lui-même.

Je ne pense pas que nous soyons tout à fait sur la même longueur d'onde :) - Disons par exemple que l'ancêtre commun est le troisième nœud compté à partir de la racine, ça va être le cas dans les deux chemins quelle que soit leur longueur respective, non?

@ 500-InternalServerError: Au fur et à mesure que les ancêtres sont construits, nous avons {subchildA, childA, root} (et de même {subsubchild, subchildB, childA, root} , nous devons appeler inverser d'abord

@ Jarod42: Oui, vous avez raison.

3 Réponses :

0
votes

J'ai trouvé le problème. En plus de devoir déplacer les deux itérateurs au lieu d'un seul (merci Jarod42 et v78), je dois également sortir de la boucle while dès que je trouve le plus petit ancêtre commun (sinon il retourne le plus grand ancêtre commun).

while(it1!=ancestors1.end()) {
        if (*it1 == *it2) {
            common_ancestor = *it1;
            break;
        }

0 commentaires

2
votes

Désolé, je n'ai pas pu résister.

Mis à part les fautes de frappe et les bugs, je pense que cela peut paraître encore plus simple:

Lowest common ancestor: 2

Résultat:

#include <cassert>
#include <algorithm>
#include <iostream>
#include <vector>

struct Node {
  int data;
  Node *parent = nullptr;
};

Node* findCommonAncestor(Node *pNode1, Node *pNode2)
{
  // find paths of pNode1 and pNode2
  std::vector<Node*> path1, path2;
  for (; pNode1; pNode1 = pNode1->parent) path1.push_back(pNode1);
  for (; pNode2; pNode2 = pNode2->parent) path2.push_back(pNode2);
  // revert paths to make indexing simple
  std::reverse(path1.begin(), path1.end());
  std::reverse(path2.begin(), path2.end());
  // compare paths
  Node *pNode = nullptr; // ancestor
  size_t n = std::min(path1.size(), path2.size());
  for (size_t i = 0; i < n; ++i) {
    if (path1[i] == path2[i]) pNode = path1[i];
    else break;
  }
  // done
  return pNode;
}

int main()
{
  // sample tree:
  /*     1
   *     |
   *     2
   *    / \
   *   3   4
   *       |
   *       5
   */
  Node node1 = { 1, nullptr };
  Node node2 = { 2, &node1 };
  Node node3 = { 3, &node2 };
  Node node4 = { 4, &node2 };
  Node node5 = { 5, &node4 };
  Node *pNode = findCommonAncestor(&node3, &node5);
  if (pNode) {
    std::cout << "Lowest common ancestor: " << pNode->data << '\n';
  } else {
    std::cout << "No common ancestor found!\n";
  }
}

Démo en direct sur coliru

Bien que l'utilisation des itérateurs s aide à garder le code général…

Je considérerais ceci comme l'un des cas où le fait de s'en tenir à un ancien tableau (alias std :: vector ) simplifie les choses.

1 commentaires

Beaucoup plus simple en effet. Merci.

0
votes

Vous ne devriez pas avoir besoin d'espace supplémentaire pour résoudre ce problème pendant cette période:

// measure depths
size_t depth1=0;
for (Node *n = node1; n; n=n->parent, ++depth1);
size_t depth2=0;
for (Node *n = node2; n; n=n->parent, ++depth2);

// move the deeper one up until they're the same depth
for (;depth1 > depth2; node1 = node1->parent, --depth1);
for (;depth2 > depth1; node2 = node2->parent, --depth2);

// move them both up until they match
while(node1 != node2) {
    node1 = node1->parent;
    node2 = node2->parent;
}

return node1;

0 commentaires