Sind structs notwendig in binäre Suchbäume

Question

Ich habe für BSTs irgend Code sieht und ich kann sehen, dass jeder Knoten eine Struktur ist. Ist das notwendig?

Answer 1

int flat_tree[ 1000 ][ 3 ];
    // for each tree node, value is stored in element [id][0]
                        // id of left_child stored in element [id][1]
                        // id of right_child stored in element [id][2]

...

Ich werde nicht weiter gehen mit diesem.

Im Allgemeinen structs / classes ist für jede Art von verknüpften Datenstruktur verwendet. Auch im Allgemeinen, jedes Merkmal des Typs Systems besiegt werden kann oder ignoriert und Sie können in einer Reihe von ints in sehr schmerzhafter Art und Weise alles (Heapzuordnung usw.) tun.

Answer 2

Nein, könnte es sich um eine Klasse sein. Es kann kein primitiv sein, weil sie einen Wert speichern muss und verweisen auch auf Kinder.

Nun, sollte ich sagen, dass Sie auch Ihre BST als Array darstellen könnte, wo die linken und rechten Kinder des Knotens an Position i sind in Positionen 2 * i + 1 und 2 * i + 2 sind. Aber dann würden Sie zum Umstellen des Formats kümmern, und Sie würden einen besonderen Wert benötigen null darzustellen, und löschen Operationen ziemlich kompliziert werden. Ich glaube nicht, diesen Ansatz als etwas empfehlen andere als eine akademische Übung.

Answer 3

Es ist nicht zwingend notwendig.
Aber da die Daten ein Knoten zusammen mit den beiden Verbindungen enthält zusammen eine logische Einheit bilden sie in der Regel zusammen in einer Struktur gebracht werden. So dass es einfacher wird, um Code-Funktionen, die einen Knoten als Argument nehmen oder einen Knoten zurück.

Answer 4

Nein, nicht genau genommen. In den Fortran Tagen, benutzten die Menschen parallel Arrays oder zweidimensionalen Arrays.

Tony Hoares Abschnitt "Strukturierte Programmierung" von Dahl, Dijkstra, und Hoare, sprach über Datenstrukturierung und Datensatztypen.

Answer 5

Sie können tun einfacher als parallele Anordnungen, wenn Ihre Nutzlast einen sentinal Wert gibt zu: Sie einen impliziten Baum verwenden können (das heißt, nicht mit Links die Mühe überhaupt).

payload_type a[tree_size];

nur eine lange flache Anordnung enthält nur Nutzlast Werte mit der Position in der Anordnung, codierend Verknüpfungsstruktur:

• a[0] ist root
• a[1] ist Wurzel-> links
• a[2] ist Wurzel-> rechts
• a[3] ist Wurzel-> links> links
• a[4] heißt Wurzel-> links> rechts
• ...

Für den Knoten an der Position i, gehen Sie zu 2 * i + 1 für links und 2 * i + 2 für die rechte

Sie initialisieren alle sentinal Werte und beginnen die Dinge Hinzufügen ...