title image


Smiley Re: Wie: Baum -> Array?
Irgendwie blicke ich deine Baumstruktur nicht so ganz. Also nehme ich einfach mal eine klassische Struktur. Unterschieden werden zwei (drei) Knotentypen. Ein Knoten kann entweder Blatt oder innerer Knoten sein. Ein innerer Knoten ist Vater von mindestens einem weiteren Knoten. Ein Blatt ist ein Knoten für den gilt, dass es kein innerer Knoten ist. Nur Blätter haben einen (auslesbaren) Wert. Ein ausgezeichneter Knoten [r] existiert in jedem Baum (r: root/Wurzel) [r] kann ein Blatt sein, dann besteht der Baum aus nur diesem einen Knoten oder [r] kann ein innerer Knoten sein. Jeder innere Knoten kann beliebig viele Kinderknoten haben.

Beispiel: [r]

--------- /|\

/ | \

/ | \

/ | \

/ | \

/ | \

/ | \

/ | \

[a] [b] [c]

/| /|\ |

/ | / | \ {1}

/ | / | \

[d] [e] [f] [g] [h]

/|\ \ /|\ \ |\

/ | \ {2} / | \ {3} | \

/ | \ / | \ | \

[i] [j] [k] [l] [m] [n] [o] [p]

| | | | | | | |

{4} {5} {6} {7} {8} {9} {10} {11}Diese Datenstruktur lässt sich sehr leicht in einem Array $dataTree unterbringen. Jeder Knoten belegt genau eine Position im Array wobei der Wurzelknoten [r] die Position 0 $dataTree[0] besitzt. Jeder Knoten an Position $pos (mit $pos < count($dataTree) ) hat entweder einen Wert (und) oder eine Menge von Kinderknoten. Zu diesem Zwecke existieren pro Knoten an Position $pos drei Werte:$dataTree[$pos]['Wert'] = null oder Wert$dataTree[$pos]['KinderStart'] >= 0$dataTree[$pos]['KinderEnde'] >= $dataTree[$pos]['KinderStart']Steht in $dataTree[$pos]['KinderStart'] eine 0, so steht auch in $dataTree[$pos]['KinderEnde'] eine 0 und es handelt sich um ein Blatt. In diesem Fall sollte in $dataTree[$pos]['Wert'] ein Wert ungleich null stehen. Steht in $dataTree[$pos]['KinderStart'] ein Wert größer 0, so ist dies der Index im Array an dem sich der erste Kinderknoten findet usw.. Da im Feld $dataTree[$pos]['Wert'] auf null und nicht auf 0 geprüft werden kann gibt es keine Einschränkung was für Werte hier stehen können. Da der Knoten mit dem Index 0 immer die Wurzel ist, ist klar, dass der Index 0 niemals ein 'echtes' Kind indizieren kann.

 

Mein Beispielbaum im Array:// Der Wurzelknoten [r] - Innerer Knoten mit Kindern

$dataTree[0]['Wert'] = null;

$dataTree[0]['KinderStart'] = 1;

$dataTree[0]['KinderEnde'] = 3;

 

// Knoten [a] - Innerer Knoten mit Kindern

$dataTree[1]['Wert'] = null;

$dataTree[1]['KinderStart'] = 4;

$dataTree[1]['KinderEnde'] = 5;

 

// Knoten [b] - Innerer Knoten mit Kindern

$dataTree[2]['Wert'] = null;

$dataTree[2]['KinderStart'] = 6;

$dataTree[2]['KinderEnde'] = 8;

 

// Knoten [c] - Blatt mit Wert

$dataTree[3]['Wert'] = 1;

$dataTree[3]['KinderStart'] = 0;

$dataTree[3]['KinderEnde'] = 0;

 

// Knoten [d] - Innerer Knoten mit Kindern

$dataTree[4]['Wert'] = null;

$dataTree[4]['KinderStart'] = 9;

$dataTree[4]['KinderEnde'] = 11;

 

// Knoten [e] - Blatt mit Wert

$dataTree[5]['Wert'] = 2;

$dataTree[5]['KinderStart'] = 0;

$dataTree[5]['KinderEnde'] = 0;

 

// ...

 

// Knoten [h] - Innerer Knoten mit Kindern

$dataTree[8]['Wert'] = null;

$dataTree[8]['KinderStart'] = 15;

$dataTree[8]['KinderEnde'] = 16;

 

// ...

 

// Knoten [o] - Blatt mit Wert

$dataTree[15]['Wert'] = 10;

$dataTree[15]['KinderStart'] = 0;

$dataTree[15]['KinderEnde'] = 0;

 

// Knoten [p] - Blatt mit Wert

$dataTree[16]['Wert'] = 11;

$dataTree[16]['KinderStart'] = 0;

$dataTree[16]['KinderEnde'] = 0;Der Baum kann, so im Array gespeichert, sehr einfach rekursiv durchlaufen werden. Ergänzend könnte sich auch jeder Knoten seinen Vater merken, so könnte man sich noch besser im Baum bewegen. Für die typischen Suchläufe im Baum ist dies allerdings nicht nötig.

 

Diese Art der Datenspeicherung hat einen eklatanten Nachteil gegebüber einem 'echten' Baum. Neue Knoten sollte man hier immer nur an die Blätter hängen (und sie somit zu inneren Knoten machen). Ansonsten muss man das gesamte Array neu organisieren. Will man also auch den Einfügekomfort eines 'echten' Baumes haben, so sollte man sich eine entsprechende Klasse programmieren.

 


Gruß Chris
This is the course in advanced physics. That means the instructor finds the subject confusing. If he didn't, the course would be called elementary physics. -- Louis Alvarez --
 


geschrieben von

Login

E-Mail:
  

Passwort:
  

Beitrag anfügen

Symbol:
 
 
 
 
 
 
 
 
 
 
 
 
 

Überschrift: