Qu'est ce qu'un "noeud interne" dans un arbre de recherche binaire?
je cherche 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 fournit pas une définition correcte de ce qu'est réellement un noeud interne.
Voici les deux endroits que j'ai principalement cherché:
http://planetmath.org/encyclopedia/ExternalNode.html suppose que les noeuds internes sont des noeuds qui ont deux sous-arbres qui ne sont pas nuls, mais qui ne disent pas quels noeuds dans l'arbre original sont internes ou externes.
http://www.math.bas.bg/~nkirov/2008/NETB201/slides/ch06/ch06-2.html semble insinuer que les noeuds internes n'existent que dans les arbres binaires appropriés et ne fournissent pas beaucoup d'informations utiles à leur sujet.
Ce qui un noeud interne!?
13 réponses
I ROOT (root is also an INTERNAL NODE, unless it is leaf)
/ \
I I INTERNAL NODES
/ / \
o o o EXTERNAL NODES (or leaves)
la magnifique montre l'image, les noeuds internes sont des nœuds situés entre la racine de l'arbre et les feuilles. Notez que la racine est aussi un noeud interne sauf dans le cas où c'est le seul noeud de l'arbre.
Ce qui est dit dans l'un des sites sur un noeud interne ayant deux enfants est que l'arbre soit un arbre binaire complet, pas pour le nœud interne.
pour autant Que je comprends, c'est un noeud qui n'est pas une feuille.
Un noeud interne ou interne nœud est tout nœud d'un arbre qui a des nœuds enfants et n'est donc pas un nœud feuille. Un intermédiaire nœud entre la racine et les nœuds feuille est appelée interne nœud.
De "Introduction Aux Algorithmes", édité par Thomas H Cormen:
un noeud sans enfant s'appelle 'Leaf node'. Un noeud non-foliaire est un "internes " nœud".
La plupart des upvoted réponse est incorrecte. Selon Structures mathématiques pour L'Informatique par Judith Gersting, un noeud interne est "Un nœud sans enfants est appelé une feuille de l'arbre; tous les non-feuilles sont appelées nœuds internes"
ainsi, par exemple (I = noeud interne):
I
/ \
* I
/\
* *
un noeud interne (aussi connu sous le nom de noeud interne, inode ou noeud de branche) est n'importe quel noeud d'un arbre qui a des noeuds d'enfant. De même, un noeud externe (aussi appelé noeud externe, noeud foliaire ou noeud terminal) est tout noeud qui n'a pas de noeud enfant.
rapide et simple.
noeud interne: noeud qui n'est pas la racine et qui a au moins un enfant.
généralement, un noeud interne est tout noeud qui n'est pas une feuille (un noeud sans enfant).
dans les arbres binaires étendus (aussi les arbres de comparaison), les noeuds internes ont tous deux enfants parce que chaque noeud interne correspond à une comparaison qui doit être faite [The Art of Computer Programming (TAoCP) vol.3 Tri et recherche, discussion et figure à la section 5.3.1, p. 181 (ed.2). Par ailleurs, l'utilisation de ces arbres pour représenter les liaisons (et revoir) pour l'élimination des tournois abordée dans la section 5.4.1 du présent matériel.]
le diagramme de Vinko reflète cette distinction, bien que le noeud racine soit toujours un noeud interne ou un noeud foliaire, en plus d'être le seul noeud sans parent.
il y a une discussion plus large dans le traitement par Knuth des structures d'information et des propriétés des arbres [TAoCP vol.1 algorithmes fondamentaux, discussion de la longueur des chemins dans les arbres, section 2.3.4.5, p. p. 399-406 (éd.3) y compris les exercices (nombreux travaillé dans le dos du livre)].
il est utile de noter que les arbres de recherche binaires (où les noeuds internes contiennent aussi des valeurs uniques ainsi que jusqu'à deux enfants) sont quelque peu différents [TAoCP vol.3, section 6.2.2]. La nomenclature fonctionne toujours, cependant.
un arbre binaire peut avoir zéro, un noeud et un maximum de deux noeuds. Un arbre binaire a un noeud gauche et un noeud droit en lui-même.
un noeud interne ou noeud interne est tout noeud d'un arbre qui a des noeuds d'enfant et n'est donc pas un noeud de feuille ou un noeud intermédiaire entre la racine et les noeuds de feuille est appelé un noeud interne
le noeud interne Ya n'inclut pas la racine. Et un arbre binaire complet comme la terminologie dit chaque noeud interne devrait avoir exact 2 noeuds. Mais dans un arbre binaire simple chaque noeud interne ont au plus 2 noeuds I. e il ne peut pas contenir plus de 2 noeuds mais moins de 2 est permissible
noeud interne-noeud avec au moins un enfant. Noeud externe-un noeud sans enfant.