tree iterator

wie mach ich das nun hier?

volkard

iter schrieb:

wie mach ich das nun hier?

Vielleicht sowas in der Art:

void start_at_end()
        {
            now = NULL;
        }

leider brauche ich bei dieser version: bool visited_left und bool visited_right...
gehts auch ohne, wenn ich den parent pointer verwende?

class node
{
public:
	class node *parent;
	class node *left;
	class node *right;

	bool visited_left;
	bool visited_right;
	int value;

	node(): parent(NULL), left(NULL), right(NULL), value(0), visited_left(false), visited_right(false) {}
};

		treeiterator &next() // next iterator for Depth first Search
		{
			if(!now->visited_left)
			{
				if(now->left)
				{
					now->visited_left = true;
					now = now->left;

					return *this;
				}
			}
			if(!now->visited_right)
			{
				if(now->right)
				{
					now->visited_right = true;
					now = now->right;

					return *this;
				}
			}
			if(now->visited_left && now->visited_right && now == ptree->get_root_node())
			{	
				now = NULL;
			}
			else
			{
				now = now->parent;
				return next();
			}

			return *this;
		}

krümelkacker

Du musst Dir im Baum keine extra Traversierungs-Flags merken; denn die Reihenfolge steht ja fest und du kannst den kompletten Baum von überall aus navigieren, wenn du parent-Links hast. Im Iterator brauchst Du auch nur einen Zeiger, wenn mich nicht alles täuscht.

Ein traversiertechnischer Nachfolger für die inorder-Reihenfolge müsste sich so bestimmen lassen. Pseudo-Code:

node* leftmost_node(node* tree)
{
  assert(tree!=0);
  while (tree->left) tree = tree->left;
  return tree;
}

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

node* next_inorder(node* current)
{
  assert(current!=0);
  if (current->right) return leftmost_node(current->right);
  return closest_right_ancestor(current);
}

wobei du hier leftmost_node gleich noch für den begin-Iterator wiederverwenden kannst.

Die anderen Traversierungen (next_preorder und next_postorder) sollten jetzt auch nicht komplizierter sein ...

Alle Angaben ohne Gewähr, da Code ungetestet.

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.