POSTORDER_next

SideWinder

Binary tree ohne parent-Zeiger, iterativ, keine Marker.

Hat da jemand eine Quelle? Irgendwie kann man bei Google nichts finden ohne parent-Zeiger ?! Oder ich bin blind...

MfG SideWinder

SideWinder

Falls es hilft: Ist eigetnlich ein threaded binary tree.

MfG SideWinder

volkard

wenn ich mir das bilchen auf http://www.coder-wiki.de/Algorithmen/Traversierung-preOrdner anschaue und überlegen, wie ich ohne speicher preorder_next(E) finden soll, geb ich gleich auf.
edit: threaded ist er also. aber threaded kann viel bedeuten. am einfachten wärs, wenn er so gethreaded wäre, daß jeder knoten einen zeiger auf sein preorder_next hat.

Christoph

SideWinder schrieb:

Falls es hilft: Ist eigetnlich ein threaded binary tree.

Threaded im Sinne von "statt null-zeiger haben die Blätter Zeiger auf in-order-Nachbarn"? Falls ja, könnte folgendes funktionieren (Pseudocode):

next_preorder(Node v) {
  if(v.has_left_child())
    return v.left;
  if(v.has_right_child())
    return v.right;

  Node w = v.right; // in-order-Nachfolger von v
  while(w && !w.has_right_child())
    w = w.right; // in-order-Nachfolger von w
  if(!w)
    return NO_SUCCESSOR;
  return w.right;
}

v.has_right_child() soll dabei true sein genau dann, wenn der pointer "v.right" kein Fädel-Zeiger ist.

Ich kann nicht sagen, ob das so funktioniert (ungetestet) aber vielleicht geht es ja in die richtige Richtung.

SideWinder

@voikard: preorder_next habe ich sogar selbst geschafft *freu* Leider ist er nicht preorder-gethreaded Er ist inorder-gethreaded.

@Christoph: Danke für den Ansatz (oder die Lösung), ich werde mir das sofort genauer ansehen.

MfG SideWinder

SideWinder

Ach damn. Entschuldige Christoph. Entschuldigung an alle. Ich suche postorder_next

MfG SideWinder

volkard

habs ein wenig versucht und alles war nicht hübsch.
mir scheint, es läuft alles darauf hinaus, daß gelegrntlich in den fallunterscheidungen folgende schleife auftaucht, die ich netterweise auslagere:

Knoten* getParent(Knoten* pos)
{
  assert(pos!=root);
  Knoten* parent=pos;
  while(parent->left!=pos && parent->right!=pos)
    pos=pos->next;
  return pos:
}

SideWinder

Danke, ich glaube ich habe nun im Knuth etwas gefunden. Kann es sein, dass der mein Verständnis von Postorder als Endorder bezeichnet und sein Postorder ein Inorder darstellt?

MfG SideWinder

SideWinder

Der Algorithmus im Knuth funktioniert nicht, Spitze. Ich hoffe ich krieg nun einen dieser $2,xx-Schecks.

Hab aber auf Basis von ihm einen Algorithmus entwickeln können der funktioniert. Muss ihn noch ausgiebig testen.

Besten Dank für eure Hinweise.

MfG SideWinder