Sind leer Binary Search Trees gültig?

Question

Ich habe zwei Fragen in Bezug auf binäre Suchbäume, die beide über leere Bäume.

1. Ist ein leerer Baum (null) gültig?
2. Ist ein Root-Knoten ohne Kinder gültig?

Answer 1

Ja, und ja.

Answer 2

Genau ein leerer Baum, was natürlich ist, hängt von den jeweiligen Implementierung, wie die Bedeutung des Wortes „gültig“ tut, aber im Allgemeinen würde ich „ja“ auf beiden Fragen sagen. Der leere Baum repräsentiert den Fall, dass die Menge von Entitäten Sie intersted in leer ist, und die einzelnen Knoten der Fall, wenn der Satz eine Einheit enthält.

Answer 3

Ein einzelner Knoten ohne Kinder ist sicherlich gültig und nach Binary Tree Structure :

  

A (änderbarer) binärer Baum, BiTree, kann   wird in einem leeren Zustand oder einem nicht-leeren   Zustand:

     

  
• Wenn es leer ist, enthält es keine Daten.
  
• Wenn es nicht leer ist, enthält es ein Datenobjekt das Wurzelelement genannt wird, und 2 verschiedene BiTree Objekte bezeichnet den linken Unterbaum und den rechten Unterbaum.
  

Für die Vollständigkeit, diese Wikipedia-Eintrag ist eine ziemlich nützliche Zusammenfassung der Terminologie und dergleichen.

Answer 4

  

ist ein leerer Baum (null) gültig?

Es gibt keinen Baum, wenn er leer ist. Daraus ergibt sich die Frage nach der Gültigkeit nicht auf.

  

Ist ein Wurzelknoten ohne Kinder gültig?

Ja. Das ist ein T-Shirt mit nur einem Element darin.

Answer 5

Ich glaube, Sie mischen zusammen Äpfel und Orangen:

1. null ist ein Wert in einigen Programmiersprachen, und es wird auf die konkrete Darstellung der Implementierung der Datenstruktur
im Zusammenhang
2. „Empty“ ist eine Eigenschaft der abstrakten Datenstruktur, die wir „binärer Suchbaum“
nennen

Nun, ein Baum ist eine geordnete Menge: nicht mehr und nicht weniger. Ein Satz kann leer sein, natürlich! Dies bedeutet, dass in den Implementierung , etwas Ähnliches wie:

MyTree tree = null

einen leeren Baum darstellen? Nun, es hängt von Ihrem Modell. Sie können denken, für ex, dass eine leere Unterstruktur sollte durch einen Knoten ohne Wert und mit den Hinweisen auf die Blätter zunichte gemacht: dargestellt wird. In diesem Modell, ein null Zeiger von einer logischen Perspektive bedeutungslos ist. Aber das ist nur ein Ansatz! Der Sentinel-basierter Ansatz ist eine Freude, mit zu programmieren, aber es ist Speicher expansive: Sie können dann mit nur null leeren Knoten modellieren. In diesem Fall kann ein null Zeiger ein leerer Baum sein.

Answer 6

Ein Binärbaum definiert werden kann rekursiv wie:

A single node with either no children, or with two children - 
each of which is a binary tree.

Answer 7

Ja beide Bedingungen erfüllt sind. Für einen binären Baum kann jeder Knoten hat null, eins oder zwei Kinder. Wenn ein Baum nur einen Wurzelknoten und keinen anderen Knoten hat dann ist es ein NULL-Baum genannt.