nombre total de l'ordre de l'arbre avec 3 noeuds

Je reçois des réponses mitigées sur internet

J'ai aussi vu une question à DONC mais il n'a pas m'a beaucoup aidé

Ce que devrait être la réponse?

Aussi est-ce un arbre?
```
    a
   /
  b
 /
c
```

C'est un peu incertaine; peut-être les différentes réponses renvoient à des définitions de "ordonné arbre"; il faut, par exemple, être pris en compte si les bords sont dirigés.
Oui, c'est un arbre, alors je voudrais également répondre à de 12.
Ce que j'envisage (avec orientation) se réfère apparemment à en.wikipedia.org/wiki/Arborescence_(graph_theory)
est-il binaire?
de manière affectée en introduisant le terme correct pour ces types de structures de données. Ça m'énerve quand l'ordinateur, les scientifiques utilisent des termes mathématiques et de symboles flippantly.

OriginalL'auteur | 2014-04-16

2

Reportez-vous à la lien, c'est un très beau livre sur le comptage du nombre des arbres ordonnés.

Merci de poster des liens sur les commentaires, ou de fournir plus de détails sur l'algorithme de sorte que la réponse est utile sans le lien, qui peut passer en mode hors connexion.

OriginalL'auteur mitansh1398
1

Tout d'abord, oui, votre exemple est un arbre en vertu de toute définition raisonnable, sauf si vous êtes exigeant de l'arbre pour être "complet", qui est mentionné nulle part. Je soupçonne donc que les réponses sur ces deux pages sont (sans surprise) de mal.

Deuxièmement, je n'aime pas la façon dont la question est formulée dans le second lien, car il ne fait pas clair ce que signifie l'égalité. Sommes-nous simplement à la recherche pour les arbres qui sont topologiquement le même (même structure, qui est, le placement des nœuds) ou que l'on recherche pour l'égalité des arbres qui contiennent un ensemble de trois nœuds spécifiques, comme dans le premier lien. Donc, je vais m'en tenir à la question dans le premier lien.

Je suis en utilisant la définition suivante de l'ordre de l'arbre. Parce qu'il n'a pas d'importance pour cette question, je vais ignorer le cas limite d'un arbre vide, bien que la définition pourrait être rédigé de façon à inclure l'arbre vide comme un candidat si vous le souhaitez. Ordre de l'arbre est constitué d'un nœud racine avec une liste vide (une séquence ordonnée) des enfants, chacun de qui est aussi l'ordre de l'arbre.

Cette définition englobe de toute évidence votre exemple. La racine est Un, il a un seul enfant, B, qui a un seul enfant C, qui n'a pas d'enfants (une liste vide d'enfants).

Nous allons procéder de manière récursive sur le nombre de nœuds N que nous plaçant dans un arbre. Nous allons supposons que T(N) le nombre de différents arbres ordonnés qui peut être construit à partir d'un ensemble fixe de N (étiquetés) nœuds.

Cas De Base: N = 1. Si nous avons exactement un nœud, nous pouvons construire un seul arbre dont le nœud est la racine. Donc T(1) = 1.

Deuxième Cas: N = 2. Il y a deux choix pour le nœud racine. Le nœud restant est nécessairement le premier et le seul enfant de la racine. Donc T(2) = 2.

Troisième Cas: N = 3. Il y a maintenant trois choix pour le nœud racine. Une fois que nous avons sélectionné un nœud racine, nous avons à nouveau deux cas:
- Cas A: Le nœud racine a deux enfants, chacun de qui est l'ordre de l'arbre avec deux éléments. Il y a deux façons nous avons pu commander les deux nœuds restants. Il y a donc 3*2 = 6 possible arbres ordonnés avec trois nœuds étant donné que le nœud racine a deux enfants.
- Cas B: Le nœud racine a un enfant, qui est nécessairement un ordre arbre avec deux éléments. Il y a des T(2) = 2 différentes façons dont on peut construire un arbre ordonné de les deux autres éléments, il y a donc un total de 3*2 = 6 possible arbres ordonnés avec trois nœuds étant donné que le nœud racine a qu'un seul enfant.
Ces deux subcases couvrir toutes les possibilités et qu'ils ne se chevauchent pas (ils partition de la possible arbres ordonnés avec trois nœuds), nous pouvons donc ajouter: T(3) = 6 + 6 = 12.

Si vous êtes intéressé dans la question plus générale, il est un peu plus compliqué et je ne sais pas la réponse, je ne sais si la réponse est connue. L'approche que je prendrais serait quelque chose comme ceci:

Cas général: N. Il y a une racine. Le reste N - 1 nœuds doit se trouver dans les sous-arbres de la racine. Si vous regardez le nombre de partition de N - 1 (le nombre de façons de rompre N - 1 en groupes). Alors aurait à regarder le nombre de façons de choisir les éléments qui vont dans chaque groupe. Et puis, regardez le nombre d'arbres ordonnés qui pourrait être faite à partir du nombre de nœuds qui sont dans chaque groupe.

De toute façon, il y a d'autres approches. Mais c'est peut-être au-delà de la portée de cette question.

REMARQUE: Une question qui pourrait se poser est de savoir si ou non j'ai oublié de compter quelque chose comme
```
    A                      A
   /                       \
  B           and            B
 /                           \
C                              C
```
Mais comme l'a ordonné des arbres, ce sont les mêmes. Ils ont été affichés ici comme s'ils étaient des arbres binaires (où chaque nœud a deux enfants qui peut être vide de sous-arbres). Mais avec des arbres ordonnés, nous venons de soins que la racine est la même et que les enfants sont égaux. Ainsi, dans les deux cas ci-dessus, les racines sont à la fois A. Dans les deux cas, la racine a un seul enfant B. Et dans les deux cas, l'enfant a un seul enfant C. Donc les arbres sont les mêmes.

OriginalL'auteur Jeremy West

Vous devez vous connecter pour publier un commentaire.