Bien les gars, on m'a posé cette question dans une interview aujourd'hui et cela va comme suit:
"Dit si un arbre binaire est contenu dans un autre arbre binaire ou non (contient implique à la fois la structure et la valeur des nœuds)"
j'ai pensé à l'approche suivante:
aplatir l'arborescence plus grande comme suit: (J'ai réellement écrit du code pour cela , maintenant pour un sous-arbre plus petit, nous devons correspondre à ce modèle. : où à l'époque i Pensée, ce sera un problème de correspondance de modèle de regex trivial dans Java, mais je suis bambouillé. En fait maintenant, je me sens, je viens de transformer le problème (créé un monstre d'un autre). existe une simple regex une doublure pour correspondre à ces modèles? Je comprends qu'il pourrait y avoir d'autres approches pour résoudre ce problème et cela pourrait ne pas être le meilleur. Je me demande simplement si cela est résoluble. {-} implique un sous-arbre vide gauche ou droit, chaque sous-arboré est enfermé dans {} paranthèse) {. *} désigne un sous-arbre vide ou non vide.
4 Réponses :
Je ne suis pas sûr de ce que l'intervieweur signifiait exactement par "contenue dans un autre arbre binaire". Si l'intervieweur demandait une méthode de vérifier si un sous-arbre de B, voici une méthode qui ne nécessite pas de regex du tout:
La raison pour laquelle vous voulez inclure les feuilles NULL est due au fait que plusieurs nœuds ont la même valeur, le pré-commande et l'utilisateur peuvent ne pas suffire. Voici un exemple: Vous pouvez également vérifier cela: Vérification des sous-arbres à l'aide des chaînes de pré-commande et d'inondation Lisez également ceci pour plus d'informations sur les travaux de pré-commande et d'inonder des arbres binaires: < / p> http://fr.wikipedia.org/wiki/tree_traversal < / P> Maintenant, s'il ne voulait pas dire juste des sous-arbres, le problème peut devenir plus compliqué en fonction de ce que l'intervieweur signifiait par une "pièce". Vous pouvez regarder la question en tant que problème d'isomorphisme sous-graphique (les arbres ne sont qu'un sous-ensemble de graphiques) et ceci est NP-complet. http://fr.wikipedia.org/wiki/subpgraph_isomorphism_problem Il peut y avoir de meilleures approches puisque les arbres sont beaucoup plus restreints et plus simples que les graphiques.
Cela ne fonctionne que pour détecter si un arbre est un sous-arbre d'un autre, de ne pas détecter si un arbre est "contenu à l'intérieur" une autre (éventuellement pas comme un sous-arbre).
Cela ne peut-il pas être fait dans une seule pré-route? Par exemple, si vous générez la chaîne de type LISP où (valeur la valeur et dont les cordes de sous-arbres gauche et droite sont
@Joshuataylor - Vous avez besoin de chèques. Lisez le fil que Joowani lie à des exemples de la raison.
@Tedhopp les exemples Il n'incluent aucune ponctuation, comme je l'ai fait dans mon commentaire. Avec ponctuation, l'arbre qui a B comme racine et A comme enfant gauche est (BA nil) et l'arbre qui a A comme racine et B comme l'enfant de droite est (un nil b) . Avec la ponctuation, je ne pense pas que deux travers sont nécessaires. (Notez que cela pourrait toujours être fait avec l'entraînement dans l'ordre, car (A b nil) et (nil a b) est aussi distinct.)
Je ne pense pas que cela fonctionne pour des parties des arbres. Considérons l'arbre d'un nœud contenant un; La chaîne de pré-commande sera "A .." (Utiliser "." Pour représenter une feuille nulle). Cet arborescence est contenu dans n'importe quel arbre qui a un nœud. Cependant, l'arbre à trois nœuds avec une racine et des enfants B et C a la chaîne de traversée de pré-commande "AB..C .." et cela ne contient pas la sous-chaîne "A.".
Oui, vous êtes juste Ted, cela ne fonctionne que sur les sous-arbres. Je vais clarifier cela dans ma réponse.
Vous pouvez le faire à l'aide d'un chèque de sous-chaîne comme décrit dans les autres réponses et en utilisant simplement un em> traverse (pré-commande, en ordre ou post-commande), tant que vous êtes Impression de l'entière em> de chaque noeud dans l'arborescence, pas seulement leurs valeurs. Par exemple, un arbre binaire est soit Chaque arbre a maintenant une représentation imprimée EM> sans ambiguïté, et donc un arbre t em> est un sous-arbre d'un arbre s em> si et seulement si la représentation de chaîne de t em> est une sous-chaîne de la représentation de chaîne de s em>. p> par exemple, l'arborescence p>
null code> ou li>
(valeur droite de l'arbre de gauche) code>, où gauche-arborescence code> et arborescence de droite code> sont remplacés par la représentation des sous-arbres de gauche et de droite. Li>
ul> (A (B (D null null) (E null null)) (C null null))
(B (D null null) (E null null))
(D null null)
(E null null)
(C null null)
Strictement parlant, Regex n'est pas équipé pour faire face aux crochets imbriqués. La nidification peut être jumelée avec Expressions régulières récursives , mais le moteur Regex de Java ne prend pas en charge les expressions récursives. Dans Perl ou PHP, vous pouvez utiliser un modèle quelque chose comme pour faire correspondre une structure d'arborescence, mais vous ne seriez toujours pas en mesure de spécifier les valeurs des nœuds d'enfants à des niveaux spécifiques. P > Donc, il n'y a malheureusement aucune ligne facile de regex qui résoudra ce problème. Regex n'est pas l'outil dont vous avez besoin pour ce travail. P> Afin de répondre à cette question, je vous recommanderais de construire votre grand arbre et de votre petit arbre, puis appeler largetree.contains (smalltree) code) code > Utilisation de la classe suivante: p> public class BTreeNode
{
public String value;
public BTreeNode left;
public BTreeNode right;
public bool contains(BTreeNode tree)
{
bool retVal = visit(tree, this);
if (!retVal && left != null)
retVal = left.contains(tree.left);
if (!retVal && right != null)
retVal = right.contains(tree.right);
return retVal;
}
private bool visit(BTreeNode small, BTreeNode large)
{
bool retVal;
if (small == null)
{
retVal = true;
}
else if (small.value.equals(large.value))
{
retVal = visit(small.left, large.left) && visit(small.right, large.right);
}
else
{
retVal = false;
}
return retVal;
}
}
ex: - Veuillez voir l'exemple d'arbre binaire ci-joint exemple T1 et T2.
Veuillez noter que ce problème n'est pas identique que le sous-arbre problème. Le Binarytree T2 est contenu dans l'arbre binaire T1 si T2 est présent de manière structurelle la même disposition de T1 et T1 peut contenir une structure supplémentaire [qui n'a pas d'importance].
J'ai résolu ce problème avec le code ci-dessous. C'est un peu trop impliqué pour expliquer mais s'il vous plaît comprenez-le en débogage. La façon dont vous appelez la fonction est à cette ligne ci-dessous. Tree1 est T1, Tree2 est T2 et taille2 est la taille de l'arbre T2.
retour (contientinernal (arbre1.getroot (), Tree2.getroot (), Taille2));
"Structure" signifie-t-il "le même objet" ou "anequals () [avec une implémentation appropriée]? Par exemple, si l'arborescence est une feuille avec une valeur" 4 "et deux ont également une feuille avec une valeur" 4 "( Mais qui est un objet différent de celui de l'arbre), l'arbre est-il contenant un arbre?
Je ne vois pas une exigence dans la question posée initialement d'utiliser des expressions régulières. Cette partie de la question de l'entretien était-elle? Les reg-exès semblent vraiment comme le mauvais outil entièrement pour ce travail.
Avec @darkfalcon, je soupçonne qu'un algorithme que doit traverser l'intégralité des deux arbres pourrait ne pas être ce que les intervieweurs espéraient. Après tout, après avoir regardé les rares nœuds de deux arbres, vous pouvez déterminer quels sous-arbres ont peut-être un chevauchement et qui ne le font pas. Même si vous souhaitez utiliser des présentations de cordes des arbres, tant que vos délimiteurs sont équilibrés, vous ne pouvez pas le faire simplement en vérifiant si la chaîne de l'arbre éventuellement contenue est une sous-chaîne de l'arbre éventuellement contenant?
@Joshuataylor - Comment "regarder" Top quelques nœuds "fonctionne-t-il? Il n'y a rien sur les arbres triés de quelque manière que ce soit.
@Tedhopp Oh, très bon point! J'avais supposé des arbres de recherche binaires, mais vous avez absolument raison, cela n'est pas mentionné dans la question. OK, si C'est un arbre de recherche binaire, il peut y avoir des solutions qui ne nécessitent pas de traverser tout l'arbre. Bonne prise!
Je suppose que "contenus à l'intérieur" ne signifie pas "sous-arbre de"? Donc, par exemple, l'arbre constitué d'un seul nœud ayant un est contenu dans l'arbre à trois nœuds ayant une à la racine et des enfants B et C?
@Tedhopp, bien que le problème soit définitivement sous-spécifié, semble être une interprétation étrange de «contenue à l'intérieur». Après tout, "l'arbre constitué d'un seul nœud ayant un" est "un nœud dont la valeur est un sous-arbre vide est l'arbre vide et dont le sous-arbre vide est l'arbre vide" et l'arbre à trois nœuds ayant un La racine et les enfants B et C "n'ont pas de nœud comme ça. Cependant, l'interprétant où l'arborescence vide dans l'élément possible est interprétée comme une carte générique dans l'arbre contenant possible, est certainement un autre exercice intéressant.
@Tedhopp: Votre interprétation est correcte. En d'autres termes, nous pouvons couper des branches du plus grand arbre d'une manière pour obtenir exactement le plus petit. Au moins c'est ce que j'ai compris à partir de la spécification de problème.
@aryan dans ce cas, alors aucune des réponses jusqu'à présent (Joowani's ou Mine) convient; ils ne traitent que de trouver des sous-arbres d'un arbre. Le problème que vous décrivez peut être plutôt plus difficile.
@Joshuataylor - C'est fondamentalement le problème des isomorphismes isomorphistiques étiquetés limités aux graphiques qui sont des arbres binaires.
@Tedhopp en effet, pour l'isomorphisme général sous-programme, il n'y a pas d'algorithme polynomial connu; Je ne sais pas s'il y a pour le cas particulier d'arbres binaires. Cette interprétation en ferait une question d'entrevue étonnamment difficile. (Bien que si quelqu'un a répondu, ils auraient probablement quelque chose à offrir, d'être sûr.)