Baum Traversal - Start bei Blättern mit nur Elternzeiger?

Ist es konzeptionell möglich, einen Baum zu haben, in dem Sie ihn durchlaufen, indem Sie an einem bestimmten Blattknoten (statt am Stammknoten) beginnen und Elternzeiger verwenden, um zur Wurzel zu gelangen?Baum Traversal - Start bei Blättern mit nur Elternzeiger?

Ich frage dies, da ich sah jemanden implementieren einen Baum und sie verwendet ein Array, um alle Blatt Knoten/externe Knoten und jeder der leaf/externen Knoten zeigen nur auf ihre Elternknoten und diese Elternpunkt zu ihren Eltern Knoten usw., bis Sie zu dem Wurzelknoten gelangen, der keine Eltern hat. Ihre Implementierung würde also erfordern, dass Sie an einem der Blätter beginnen, um an eine beliebige Stelle im Baum zu gelangen, und Sie könnten nicht "nach unten" gehen, da ihre Baumknoten keine Kinderzeiger, sondern nur Elternzeiger haben.

Ich fand diese Implementierung interessant, da ich nichts dergleichen gesehen habe, aber ich war neugierig, ob es immer noch als ein "Baum" betrachtet werden könnte. Ich habe noch nie einen Baum gesehen, bei dem man an den Blättern traversiert statt an der Wurzel. Ich habe auch nie einen Baum gesehen, wo die Baumknoten nur Elternzeiger und keine Kinderzeiger haben.

Quelle

2013-03-11 user2157871

Sie haben grundsätzlich Ihre eigene Frage beantwortet. Ja, das ist völlig in Ordnung. Windows Presentation Foundation ist ein gutes Beispiel dafür, warum Sie dies tun möchten. nämlich relative Datenbindung; d. h. durchquere den Baum, bis du etwas gefunden hast, und binde ihn dann fest. Siehe: http://stackoverflow.com/questions/84278/how-doi-i-use-wpf-bindings-with-relativesources Eine interessantere Frage ist * warum * du willst und warum du nur _parent_ willst Links. –

Ja, diese Struktur existiert. Es wird oft genannt.

Spaghetti-Stapel sind nützlich, um die Beziehung "ist ein Teil von" darzustellen. Wenn Sie beispielsweise eine Klassenhierarchie so darstellen möchten, dass das Upcasting effizient ist, können Sie die Klassenhierarchie als Spaghetti-Stack darstellen, in dem der Knoten für jeden Typ einen Zeiger auf seinen übergeordneten Typ speichert. Auf diese Weise ist es einfach zu finden, ob ein Upcast gültig ist, indem man einfach vom Knoten nach oben geht.

Sie werden auch oft in Compilern verwendet, um Informationen zum Scoping zu verfolgen. Jeder Knoten repräsentiert einen Bereich im Programm, und jeder Knoten hat einen Zeiger auf den Knoten, der den darüber liegenden Bereich darstellt.

Hoffe, das hilft!

Quelle

2013-03-11 18:02:33 templatetypedef

Wenn ein Array A von Blattknoten angegeben ist, ist Traversieren möglich. Wenn nur ein einzelner Blattknoten angegeben wird, kann ich den Baum nicht durchqueren. Pseudocode:

// initial step 
add all nodes in A to a queue Q 

//removeNode(Q) returns pointer to node at front of Q 
while((node = removeNode(Q)) != NULL) 
    /* do your operation on node */ 
    add node->parent to Q

Quelle

2013-03-11 18:02:35 Bhaskar

Baum Traversal - Start bei Blättern mit nur Elternzeiger?

Antwort

Verwandte Themen