BFS vs DFS

[Coder007]

Hi,

wie kann ich die BFS in eine DFS umwandeln? Kann man das noch eleganter lösen als mit stack oder queue?

Bye

#include <iostream>
#include <queue>
using namespace std;

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

	int value;

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

class tree
{
private:
	class node *root;

public:
	class treeiterator
	{
	private:
		std::queue<class node*> st;
		class tree *ptree;
		class node *now;

	public:
		treeiterator(class tree *ptree_tmp): now(NULL)
		{
			ptree = ptree_tmp;
		}

		void begin()
		{
			now = ptree->get_root_node();
		}

		void end()
		{
			now = NULL;
		}

		class node *get_node()
		{
			return now;
		}

		treeiterator &next()
		{
			if(now->left)
			{
				st.push(now->left);
			}
			if(now->right)
			{
				st.push(now->right);
			}

			if(!st.empty())
			{
				now = st.front();
				st.pop();
			}
			else
			{
				now = NULL;
			}

			return *this;
		}

		bool operator== (treeiterator &it)
		{
			return this->get_node() == it.get_node();
		}

		bool operator!= (treeiterator &it)
		{
			return this->get_node() != it.get_node();
		}

		node operator*()
		{
			return *get_node();
		}
	};

	tree(): root(NULL) {}

	class node *get_root_node()
	{
		return root;
	}

	bool insert(int val)
	{
		class node *now = root;
		class node *n = new node;
		class node *prv = NULL;
		n->value = val;

		if(!root)
		{
			root = n;
		}
		else
		{
			// search parent node
			while(now)
			{
				prv = now;

				if(val < now->value)
				{
					now = now->left;
				}
				else if(val > now->value)
				{
					now = now->right;
				}
			}

			now = prv;

			if(val > now->value)
			{
				now->right = n;
			}
			else
			{
				now->left = n;
			}
		}

		return true;
	}

	class node *search(class node *root, int val)
	{
	}

	bool delete_node(int val)
	{
	}

	bool remove(class node *n)
	{
	}

	class treeiterator begin()
	{
		class treeiterator it(this); 
		it.begin(); 
		return it;
	}

	class treeiterator end()
	{
		class treeiterator it(this); 
		it.end(); 
		return it;
	}
};

int main()
{
	tree t;
	t.insert(4);
	t.insert(3);
	t.insert(2);
	t.insert(1);
	t.insert(5);

	tree::treeiterator it(&t);
	for(it = t.begin(); it != t.end(); it = it.next())
	{
		cout << (*it).value << endl;

	}

	return 0;
}

[knivil]

wie kann ich die BFS in eine DFS umwandeln?

Was meinst du damit?

[tnagraan]

@knivil: BFS, DFS.

Kann man das noch eleganter lösen als mit stack oder queue?

Was meinst du damit?

[Coder007]

knivil schrieb:

wie kann ich die BFS in eine DFS umwandeln?

Was meinst du damit?

ich brauche die queue nur gegen einen stack auswechseln...dann habe ich eine DFS...

[tnagraan]

Coder007 schrieb:

ich brauche die queue nur gegen einen stack auswechseln...dann habe ich eine DFS...

Ist mir schon klar, aber was ist die Frage?

[hustbaer]

Coder007 schrieb:

wie kann ich die BFS in eine DFS umwandeln?

Ich denke indem du die Queue durch nen Stack ersetzt.

Kann man das noch eleganter lösen als mit stack oder queue?

Müsste sich schön machen lassen wenn du im Iterator zusätzlich zum aktuellen Knoten auch den nächsten zu besuchenden Knoten abspeicherst (oder alternativ den vorigen Knoten - ist im Prinzip das selbe).

Dann weisst du immer was der letzte Schritt war, und kannst daraus den nächsten ableiten.

Bei "runter" nimmst du als nächstes die erste verfügbare Richtung aus: links-runter, rechts-runter, hoch.
Bei "von-links-kommend-hoch" nimmst du als nächstes die erste verfügbare Richtung aus: rechts-runter, hoch.
Und bei "von-rechts-kommend-hoch" nimmst du als nächstes: hoch.

Und wenn nix mehr geht (kein "hoch" mehr da) bist du fertig.

[Tachyon]

Ich mache es immer ähnlich wie der TO. Was meinst Du denn mit "eleganter"? Codemäßig wäre vermutlich ein rekusriver Algorithmus eleganter. Aber von der Praktikabiltät und Flexibilität her, ist die Nachbildung der Rekursion über die passenden Container schon ziemlich optimal.

[hustbaer]

Öh...
Wen sprichst du jetzt an?

[Tachyon]

hustbaer schrieb:

Öh...
Wen sprichst du jetzt an?

Den TO. Steht da sogar.

[hustbaer]

Nein, steht da nicht.
Da steht "Ich mache es immer ähnlich wie der TO. Was meinst Du denn mit ...".
Das "der TO" (3. Person) im ersten Satz impliziert dass du jmd anderen ansprichst.

[Tachyon]

hustbaer schrieb:

Nein, steht da nicht.
Da steht "Ich mache es immer ähnlich wie der TO. Was meinst Du denn mit ...".
Das "der TO" (3. Person) im ersten Satz impliziert dass du jmd anderen ansprichst.

Ist ja gut. Irgendwie übellaunig, heute?

[Eisflamme]

Man kann jedoch implizieren, dass er den TO meint, weil elegant im ersten Satz des OP steht. Böse Zungen könnten sogar sagen, dass man das nur dann nicht erkennt, wenn man den OP nicht im Kopf hat, aber das wäre natürlich albern und hier auch gar nicht zutreffend.

[hustbaer]

Tachyon schrieb:

hustbaer schrieb:

Nein, steht da nicht.
Da steht "Ich mache es immer ähnlich wie der TO. Was meinst Du denn mit ...".
Das "der TO" (3. Person) im ersten Satz impliziert dass du jmd anderen ansprichst.

Ist ja gut. Irgendwie übellaunig, heute?

Nein. Dein Beitrag war nur nicht zu verstehen, also hab ich nachgefragt.
Dann schreibst du "steht sogar da", was es aber nicht tut, und ich hab mir die Freiheit genommen darauf hinzuweisen.
Irgendwie empfindlich, heute?

[hustbaer]

@Eisflamme
Wenn da erst "der TO" steht, und dann im nächsten Satz auf einmal "Du", ohne einen Hinweis darauf dass hier ein Wechsel der Ansprechperson stattgefunden hat (von "die Allgemeinheit" zu "der TO") ...
Dann ist für mich klar dass das "Du" im 2. Satz nicht an den TO gerichtet sein kann, denn sonst wäre im ersten Satz ja auch schon "Du" gestanden.

Von daher war ich mir wirklich nicht 100% sicher wen er meint.