Was ist ein „interner Knoten“ in einem binären Suchbaum?

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

  •  06-07-2019
  •  | 
  •  

Frage

Ich bin Scheuern im Internet für eine Definition des Begriffs „Interner Knoten.“ Ich kann nicht eine prägnante Definition. Jede Quelle Ich betrachte verwendet den Begriff, ohne ihn zu definieren, und die Verwendung ergibt keine richtige Definition dessen, was ein interner Knoten tatsächlich ist.

Hier sind die beiden Orte, die ich habe in erster Linie gesucht: http://planetmath.org/encyclopedia/ExternalNode.html nimmt an, dass interne Knoten Knoten sind, die aufweisen zwei Teilbäume, die nicht null sind, aber nicht sagen, was in dem ursprünglichen Baumknoten sind interne oder externe.

http: //www.math .bas.bg / ~ nkirov / 2008 / NETB201 / slides / CH06 / ch06-2.html dass interne Knoten existieren nur in der richtigen Binärbäumen zu einzuschleichen scheint und nicht nachgibt viele nützliche Informationen über sie.

Was eigentlich ein interner Knoten!?

War es hilfreich?

Lösung 

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

Wie das wunderbare Bild zeigt, interne Knoten sind Knoten zwischen der Wurzel des Baumes und die Blätter entfernt. Beachten Sie, dass die Wurzel ist auch ein interner Knoten außer im Fall ist es der einzige Knoten des Baumes.

Was in einem der Standorte über einen internen Knoten wird gesagt, mit zwei Kinder haben, ist für den Baum ein vollständiger binärer Baum, nicht für den Knoten zu sein intern zu sein.

Andere Tipps

Soweit ich es verstehe, es ist ein Knoten, der kein Blatt ist.

Von "Introduction to Algorithms", herausgegeben von Thomas H Cormen:

  

Ein Knoten ohne Kind ‚Blattknoten‘ bezeichnet. Ein Nicht-Blattknoten ein   'Interner Knoten'.

  

oder einen internen Knoten inneren Knoten ist eine beliebige   Knoten eines Baumes, der Knoten untergeordnet   und ist damit kein Blattknoten. Ein   Zwischenknoten zwischen der Wurzel und   die Blattknoten eine interne genannt   Knoten.

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

Die meisten upvoted Antwort ist falsch. Nach Mathematische Strukturen für Informatik von Judith Gersting, ein interner Knoten ist „Ein Knoten ohne Kinder ist ein Blatt des Baumes genannt; alle nicht-Blätter werden als interne Knoten "

So zum Beispiel (I = INTERN NODE): I / \ * I /\ * *

einen internen Knoten (auch als innere Knoten, inode für kurze oder Zweigknoten bezeichnet) ist ein Knoten eines Baums, der untergeordneten Knoten hat. In ähnlicher Weise ein externer Knoten (auch als äußereen Knoten, Blattknoten oder Endknoten bekannt) ist jeder Knoten, der nicht untergeordneten Knoten hat.

schnell und einfach.

Die interne Knoten: ein Knoten, der nicht die Wurzel ist und mindestens ein Kind

.

Im Allgemeinen ein interner Knoten ist jeder Knoten, der kein Blatt (ein Knoten ohne Kinder) ist.

In der erweiterten Binärbäumen (auch Vergleich Bäume), interne Knoten haben alle zwei Kinder, weil jeder interne Knoten zu einem Vergleich entspricht, die [The Art of Computer Programming (TAOCP) Vol.3 vorgenommen werden müssen Sortieren und Suchen, die Diskussion und Figur in Abschnitt 5.3.1, S. 181 (ed.2). By the way, ist die Verwendung dieser Bäume Paarungen darstellen (und byes) zur Eliminierung Turnieren wird in Abschnitt 5.4.1 dieses Materials gerichtet.]

Vinko des Diagramms spiegelt diese Unterscheidung, obwohl der Wurzelknoten entweder ein interner Knoten oder ein Blattknoten auch immer ist, zusätzlich zu dem einzigen Knoten ohne Elternteil.

Es gibt eine breitere Diskussion in Knuths Behandlung von Informationsstrukturen und Eigenschaften von Bäumen [TAOCP vol.1 Fundamental Algorithms, die Diskussion über Weglängen in den Bäumen in Abschnitt 2.3.4.5, Seiten 399-406 (ed.3) mit Übungen (viele arbeiten-out in der Rückseite des Buchs)].

Es ist nützlich zu bemerken, dass binäre Suchbäume (wo interner Knoten auch als auch mit bis zu zwei Kindern Einzelwerte hält) sind etwas anders [TAOCP Vol.3, Abschnitt 6.2.2]. Die Nomenklatur noch funktioniert, though.

Ein binärer Baum kann null, ein Knoten hat und maximal zwei Knoten haben kann. Ein Binärbaum einen linken Knoten und einen rechten Knoten in sich haben.

Die interne Knoten - ein Knoten mit mindestens einem Kind. Externe Knoten -. Ein Knoten ohne Kinder

oder ein interner Knoten innerer Knoten ist ein Knoten eines Baums, die untergeordneten Knoten aufweist und somit keinen Blattknoten oder einen Zwischenknoten zwischen der Wurzel und dem Blattknoten ist ein interner Knoten

genannt

Ein Knoten, der mindestens ein Kind hat.

Ya interner Knoten enthält nicht die Wurzel. Und ein vollständiger binärer Baum als Terminologie sagt jeder interne Knoten genau zwei Knoten haben sollte. Aber in einem einfachen binären Baum jeder interne Knoten haben atmost 2 Knoten heißt es nicht mehr als 2 Knoten enthalten kann, aber weniger als 2 ist permisable

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top