tree iterator

hm...bist du dir sicher das funktioniert so?
warum das hier?

if (current->right) return leftmost_node(current->right);

krümelkacker

iter schrieb:

bist du dir sicher das funktioniert so?

Ziemlich.

iter schrieb:

warum das hier?

if (current->right) return leftmost_node(current->right);

Wenn "current" der aktuelle Knoten in der inorder-Traversierung ist, dann haben wir den linken Teilbaum schon komplett abgegrast (falls es den überhaupt gibt). Als nächstes wäre also der rechte Teilbaum dran. Und was ist der "erste" Knoten eines Baumes im inorder-Sinne? Das ist doch der Knoten, der am "weitesten links steht". Den erreiche ich über leftmost_node(wurzel). Die Wurzel des rechten Teilbaums ist ja current->right.

wie soll er den linken teilbaun abgrasen wenn du mit dem rechten startest?

if (current->right) return leftmost_node(current->right);

ich gehe davon aus das du mit root startest...
dann ist current->right ...doch root->right

krümelkacker

Entscheide dich doch erstmal, in welcher Reihenfolge Du dem Nutzer die Knoten präsentieren willst. Ich bin jetzt von einer inorder-Traversierung ausgegangen. Und da fängt man nicht mit der Wurzel sondern mit leftmost_node(wurzel) an.

in der gleichen reihenfolge wie hier:

treeiterator &next() // next iterator for Depth first Search
		{
			if (now->right) 
			{
				stack.push(now->right);
			}
			if (now->left) 
			{
				stack.push(now->left);
			}

			if (!stack.empty()) 
			{ 
				now = stack.top(); 
				stack.pop();
			}
			else
			{
				now = NULL;
			}

                        return *this;
}

also pr-order transversal

krümelkacker

Auch das ließe sich dank parent-Links ohne stack im Iterator realisieren.

Für einen Suchbaum ist diese Reihenfolge nicht praktisch, da der Nutzer keine sortierte Sequenz sehen würde. Deswegen bin ich von inorder ausgegangen. Aber das ist ja deine Sache mit der Reihenfolge.

Jetzt nachdem du die inorder-Variante gesehen hast, die im übrigen funktioniert (habe sie jetzt getestet), sollte es für dich kein Problem sein, darauf zu kommen, wie die preorder-Variante aussieht. Meine Hilfe zum Tarif "kostenlos" hast Du zu diesem Thema jetzt ausgereizt.

solution:

class node* closest_right_ancestor1(class node* from)
		{
		  assert(from!=0); 
		  for (node* p = from; p != 0; p = p->parent)
		  {
			if (p->left == from) return p->right; 
			from = p;
		  }
		  return 0; // does not exist 
		}

		treeiterator &next() // next iterator for Depth first Search
		{
			assert(now!=0); 
			if (now->left)
			{
				now = now->left;
				return *this;
			}
			if (now->right) 
			{
				now = now->right; 
				return *this;
			}
			now = closest_right_ancestor(now);
		}

kann man breath first search auch ohne zusätzlichen speicher implementieren?

krümelkacker

Das ist keine Lösung. Es erzeugt bei

[2]
     /   \
  [1]     [3]

die Endlosschleife: 2,1,2,1,2,1,2,1,...

Außerdem fehlt da noch ein return am Ende.

Und lass das class bei class node* weg.

closest_right_ancestor hast du auch verschlimmbessert. Aber die brauchst du hier eh nicht, die Funktion.