Je veux savoir si l'arbre binaire T2 est un sous-arbre de l'arbre binaire T1. J'ai lu que i Je suis un peu confus par cette méthode et je ne suis pas sûr de son exactitude. de wiki: "Un sous-arbre d'un arbre T est un arbre composé d'un nœud de T et de tous ses descendants dans T." / p> Dans l'exemple suivant: Si nous construisons les chaînes pour T2 et T1: Pré-commande T2: "1,2 , 3 " Les chaînes T2 sont des sous-chaînes de T1, donc en utilisant la méthode de correspondance de sous-chaîne décrite ci-dessus, nous devrions conclure T2 est un sous-arbree de T1. Cependant, T2 par définition ne devrait pas être un sous-arbre de T1 puisqu'il ne dispose pas de tous les descendants du nœud racine de T1. Il y a une discussion associée , qui semble conclure que la méthode est correcte. Est-ce que je manque quelque chose ici?
Pré-commande T1: "1,2,3,4" de
Inordorder T2: "2,1,3" de
Inordorder T1: "2,1,3,4"
6 Réponses :
question très intéressante. Vous semblez être correct. Je suppose que la question que vous mentionnez se pose en raison de différentes définitions de sous-arbre dans maths (théorie graphique) et l'informatique. Dans la théorie du graphique T2 est un sous-arbre approprié de T1.
La définition du sous-arbre d'un arbre doit être identique à la définition de la sous-chaîne d'une chaîne. Pensez-y comme ceci: 1. La sous-chaîne commence - avec, contient et finit par. 2. L'arbre doit également avoir la même définition mais généralisée en fonction de la structure de données d'arborescence. 3. La généralisation est de 1 dimension pour la chaîne à 2 dimensions pour l'arbre.
Je lis le même livre et je doutais sa solution aussi. Je suis proposé un autre contre-exemple qui ne tombe pas dans l'interprétation potentielle que l'utilisateur Icepack mentionne (d'un sous-arbre n'ayant pas nécessairement besoin de tous les descendants).
considère les arbres suivants Pré-commande T2: 'BAC' Encore une fois, les chaînes T2 sont des sous-chaînes de leurs homologues T1 et pourtant T2 n'est en aucun cas un sous-arbre de T1. Peut-être que dans l'auteur avaient excluté des doublons et mentionnait spécifiquement sa définition de sous-arbre, cela pourrait être correct, mais laissant échapper à cette information nous laisse sans choix que de considérer la solution incorrecte.
Pré-commande T1: 'CBAC'
Inorder T2: 'ABC'
Inordorder T1: 'ABCC'
Vous ne pouvez pas réutiliser C comme ça, ce n'est pas la façon dont la théorie fonctionne.
Je ne suis pas sûr de la théorie que vous parlez de. Je viens de remarquer que le livre ne mentionne aucune valeur des arbres n'ayant aucune valeur en double (le livre est très explicite dans la désignation lorsqu'il fait référence aux arbres de recherche binaires par opposition aux arbres binaires généraux. Ce cas n'était pas un arbre de recherche binaire).
"On pourrait construire des représentations de chaîne pour T2 et T1 à l'aide de Travershas de pré-commande et de commandes, et si les chaînes T2 sont des soustres de T1, T2 est un sous-arbre de T1". Cette théorie ne pourrait être correcte que si chaque nœud a un caractère unique. Si vous avez besoin de plus de caractères, vous auriez également besoin d'une méthode pour expliquer lorsque le début d'un nom de nœud est, tel que les noms de nœud, commencez par des majuscules et que tous les autres caractères sont minuscules.
Oh, je ne fais pas étiqueter les nœuds, ceux qui étaient destinés à être les valeurs des nœuds (peut-être que j'aurais dû utiliser des entiers), mais encore une fois, le livre n'a pas précisé pour ce problème qu'il n'y a pas de duplicate, et donc l'idée d'utiliser les représentations de chaîne dans l'ordre / pré-commandez pour déterminer si un sous-arbre de l'autre est incorrect. C'est tout ce que j'essayais d'illustrer ma réponse.
Quand il est indiqué que "on pourrait construire des représentations de chaîne pour T2 et T1", ce qui signifie avec une représentation de chaque nœud, pas leurs valeurs. De toute évidence, utiliser des valeurs est absolument inutile pour les raisons que vous décrivez dans votre réponse.
na ... Cette approche n'est pas correcte.parce, des différents arbres peuvent avoir la même traversée. Par exemple, dans l'exemple donné, l'arborescence est et les sous-arbres candidats sont p> et p> 30
/ \
4 10
\
6
La traversée dans l'ordre du dernier arbre n'est pas 4,30,10,6. C'est 4,6,30,10
En supposant que vous avez obtenu cela à partir du livre "craquer l'entretien de codage", l'auteur mentionne également que pour distinguer les nœuds avec les mêmes valeurs, il faut également imprimer les valeurs null.
Cela résoudrait également votre problème avec la définition d'un sous-arbre (qui est correcte comme décrit également dans le livre)
Pré-commande T2: "1, 2, NULL, NULL, 3, NULL, NULL" Pré-commande T1: "1, 2, NULL, NULL, 3, NULL, 4, NULL, NULL" Inordorder T2: "NULL, 2, NULL, 1, NULL, 3, NULL" Inordorder T1: "NULL, 2, NULL, 1, NULL, 3, NULL, 4, NULL"
Comme vous pouvez le constater, T2 n'est pas un sous-arbre de T1