Qu'est-ce qu'un & # 8220; noeud interne & # 8221; dans un arbre de recherche binaire?

StackOverflow https://stackoverflow.com/questions/265809

  •  06-07-2019
  •  | 
  •  

Question

Je recherche sur Internet une définition du terme "nœud interne". Je ne trouve pas de définition succincte. Chaque source que je regarde utilise le terme sans le définir, et l'utilisation ne donne pas une définition correcte de ce qu'est un nœud interne.

Voici les deux endroits où j'ai principalement regardé: http://planetmath.org/encyclopedia/ExternalNode.html suppose que les nœuds internes sont des nœuds qui ont deux sous-arbres qui ne sont pas nuls, mais ne disent pas quels nœuds de l'arborescence d'origine sont internes ou externes.

http: //www.math .bas.bg / ~ nkirov / 2008 / NETB201 / slides / ch06 / ch06-2.html semble insinuer que les nœuds internes n'existent que dans des arbres binaires appropriés et ne fournissent pas beaucoup d'informations utiles à leur sujet.

Qu'est-ce que est un noeud interne!?

Était-ce utile?

La solution 

     I         ROOT (root is also an INTERNAL NODE, unless it is leaf)
   /   \
  I     I      INTERNAL NODES
 /     / \
o     o   o    EXTERNAL NODES (or leaves)

Comme le montre l’image magnifique, les nœuds internes sont des nœuds situés entre la racine de l’arbre et les feuilles. Notez que la racine est également un nœud interne, sauf qu’il s’agit du seul nœud de l’arbre.

Ce qui est dit dans l'un des sites à propos d'un nœud interne qui doit avoir deux enfants, c'est que l'arbre soit un arbre binaire complet, et non pas que le nœud soit interne.

Autres conseils

Pour autant que je sache, c'est un nœud qui n'est pas une feuille.

D'après "Introduction aux algorithmes", édité par Thomas H Cormen:

  

Un nœud sans enfant s'appelle 'nœud feuille'. Un nœud non-feuille est un   "noeud interne".

  

Un noeud interne ou interne est un   noeud d'un arbre qui a des noeuds enfants   et n'est donc pas un nœud feuille. Un   noeud intermédiaire entre la racine et   les noeuds feuilles sont appelés internes   noeud.

Source: http://en.wikipedia.org/wiki/Tree_data_structure

La réponse la plus votée est incorrecte. Selon Structures mathématiques pour l'informatique de Judith Gersting, un nœud interne est "Un nœud sans enfant est appelé une feuille de l'arbre; tous les non-feuilles sont appelées noeuds internes "

Donc, par exemple (I = INTERNAL NODE):    je   / \  * JE      / \     * *

Un nœud interne (également appelé nœud interne, inode pour nœud abrégé ou nœud de branche) est tout nœud d'une arborescence comportant des nœuds enfants. De même, un nœud externe (également appelé nœud externe, nœud terminal ou terminal) est un nœud n’ayant pas de nœud enfant.

simple et rapide.

Noeud interne: noeud qui n’est pas la racine et qui a au moins un enfant.

Généralement, un nœud interne est un nœud qui n'est pas une feuille (un nœud sans enfants).

Dans les arbres binaires étendus (ainsi que les arbres de comparaison), les nœuds internes ont tous deux enfants, car chaque nœud interne correspond à une comparaison à effectuer [Le travail de programmation informatique (TAoCP) vol.3 - Tri et recherche, discussion et illustration dans la section 5.3.1, p.181 (ed.2). Soit dit en passant, l’utilisation de ces arbres pour représenter les appariements (et les byes) pour les tournois d’élimination est traitée dans la section 5.4.1 de ce document.]

Le diagramme de Vinko reflète cette distinction, bien que le nœud racine soit également toujours un nœud interne ou un nœud feuille, en plus d’être le seul nœud sans parent.

Il y a une discussion plus large dans le traitement par Knuth des structures d'informations et des propriétés des arbres [TAoCP vol.1 Algorithmes fondamentaux, discussion de la longueur des chemins dans les arbres dans la section 2.3.4.5, p.p. 399-406 (ed.3), y compris des exercices (beaucoup sont détaillés à la fin du livre)].

Il est utile de noter que les arbres de recherche binaires (où les nœuds internes contiennent aussi des valeurs uniques et peuvent avoir jusqu'à deux enfants) sont quelque peu différents [TAoCP vol.3, section 6.2.2]. La nomenclature fonctionne toujours.

Un arbre binaire peut avoir zéro, un nœud et au maximum deux nœuds. Un arbre binaire a un noeud gauche et un noeud droit en lui-même.

Noeud interne - un noeud avec au moins un enfant. Noeud externe - un noeud sans enfants.

Un nœud interne ou un nœud interne est un nœud d'un arbre qui a des nœuds enfants et n'est donc pas un nœud feuille ou un nœud intermédiaire situé entre les nœuds racine et feuille est appelé un nœud interne

Un nœud ayant au moins un enfant.

Un noeud interne n'inclut pas la racine. Et une arborescence binaire complète comme terminologie indique à chaque nœud interne doit avoir exactement 2 nœuds. Mais dans un simple arbre binaire, chaque noeud interne a au plus 2 noeuds, c’est-à-dire qu’il ne peut pas contenir plus de 2 noeuds mais que moins de 2 est autorisé

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top