Struktur mit mehreren untergeordneten Knoten und dem nächsten Knoten
Ich möchte einen Baum mit den folgenden Eigenschaften erstellen:
- Jeder Knoten kann 1 "next node" haben.
- Jeder Knoten kann mehrere untergeordnete Knoten haben.
- Die Anzahl der untergeordneten Knoten kann von Knoten zu Knoten variieren
Ich dachte an eine Struktur, die so aussah:
%Vor%Die Anzahl der Kinder an jedem Knoten muss parametrisiert werden. Ich bin mir nicht sicher, wie ich das machen soll. Vielen Dank im Voraus!
Bearbeiten : Lassen Sie mich versuchen, es anhand eines Beispiels zu definieren: Nehmen wir den Startknoten. Jetzt werde ich zur Kompilierzeit definieren, dass es 3 NextNodes geben wird und jede dieser NextNodes wird 2 ChildNodes haben. Dies ist bei Depth=0 . Bei Depth = 1 (d. H. Für jeden untergeordneten Knoten von Depth=0 ) gebe ich an, dass es 4 NextNodes geben wird und für jede dieser NextNodes gibt es 3 ChildNodes und so weiter. Hoffe ich kann es richtig vermitteln. Bitte frag, ob ich irgendwo nicht klar bin.
Edit2 : Hier ist ein Bild:
3 Antworten
Dies ist ein N-ary-Baum. Ich schlage vor, Sie in Baum und Knoten zu teilen
%Vor%Jetzt können Sie alle Operationen der Baumstruktur durchführen
hier ein Beispiel
%Vor%Sie können die Bibliothek Boost.Graph verwenden.
>Sehr kompliziert auf den ersten, aber bieten eine effiziente Datenspeicherung und hoch optimierte Graph-Algorithmus-Implementierungen.
Von der Website:
Algorithmen
Die BGL-Algorithmen bestehen aus einem Kernsatz von Algorithmusmustern (implementiert als generische Algorithmen) und einem größeren Satz von Graphalgorithmen. Die Kernalgorithmusmuster sind
- Breite erste Suche
- Tiefe erste Suche
- Einheitliche Kostensuche
Die Algorithmenmuster berechnen selbst keine sinnvollen Größen über Graphen; Sie sind lediglich Bausteine für den Aufbau von Graphalgorithmen. Die Graphalgorithmen in der BGL enthalten derzeit
- Dijkstras kürzeste Wege
- Bellman-Ford Kürzeste Wege
- Johnsons All-Pairs Shortest Paths
- Kruskals minimaler spannender Baum
- Prims minimaler Spannbaum
- Verbundene Komponenten
- Stark verbundene Komponenten
- Dynamisch verbundene Komponenten (mit disjunkten Sets)
- Topologische Sortierung transponieren
- Umkehr Cuthill Mckee Bestellung
- Kleinste letzte Vertex-Bestellung
- Sequentieller Vertex Coloring
Datenstrukturen
Die BGL bietet derzeit zwei Graphenklassen und einen Kantenlistenadapter an:
- adjazenzliste
- adjacency_matrix
- Kantenliste
Die Klasse adjacency_list ist das universelle "Schweizer Armeemesser" der Graphenklassen. Es ist hoch parametrisiert, so dass es für verschiedene Situationen optimiert werden kann: Der Graph ist gerichtet oder ungerichtet, erlaubt oder verbietet parallele Kanten, effizienten Zugriff auf nur die Out-Kanten oder auch auf die In-Kanten, schnelles Einfügen und Entfernen von Ecken Kosten für zusätzliche Platzkosten usw.
Die Klasse adjacency_matrix speichert Kanten in einem | V | x | V | Matrix (wobei | V | die Anzahl der Scheitelpunkte ist). Die Elemente dieser Matrix repräsentieren Kanten im Graphen. Adjazenzmatrixdarstellungen sind besonders geeignet für sehr dichte Graphen, d. H. Solche, bei denen die Anzahl der Kanten sich | V | 2 nähert.
Die Klasse edge_list ist ein Adapter, der jede Art von Kanteniterator verwendet und einen Kantenlistengraphen implementiert.
Das größte Problem, das Sie hier haben, sind unklare Anforderungen: " Die Anzahl der Kinder an jedem Knoten muss parametrisiert werden " besonders in Kombination mit " Die Anzahl der untergeordneten Knoten kann variieren ein Knoten zum anderen ".
Versuchen Sie herauszufinden, was genau das bedeutet und es sollte nicht so schwer sein, es zu implementieren. So wie es jetzt aussieht, würde ich nicht wissen, wie man es tut, weil ich nicht weiß, was zu tun ist: Müssen Sie die Anzahl der Knoten speichern, müssen Sie ein Maximum an Knoten haben, tut es das Maximum muss zur Kompilierzeit bekannt sein, ...?
Bearbeiten Sie anhand des Beispiels: Ich bin mir des nächsten Knotens nicht sicher, weil Sie sagen, dass es 3 Next-Nodes gibt, aber die Anforderungen geben an, dass es 1 Next-Node pro Node gibt (wie Sie in Ihrer Baumstruktur anzeigen).
Wenn Sie die Anzahl der Knoten basierend auf der Tiefe parametrisieren müssen, müssen Sie wahrscheinlich Ihre Tiefe speichern oder als Parameter übergeben und eine feste Anordnung von Knoten pro Tiefe erstellen, die Sie beim Erstellen der untergeordneten Knoten konsultieren.
Dann müssen Sie wissen, was zu tun ist, wenn die Tiefe das Array überschreitet (stoppen Sie Ihren Baum oder verwenden Sie eine Standardanzahl von Knoten)
Tags und Links c pointers data-structures tree