Array in Binären Suchbaum umwandeln



  • Hallo zusammen,
    ich habe folgenden Code als Vorgabe bekommen.

    #include <iostream>
    #include <math.h>
    #include <assert.h>
    using namespace std;
    
    class BinaryNode {
    
    public:
    	BinaryNode(int key) {
    		this->key = key;
    		this->parent = this->left = this->right = NULL;
    	}
    
    	BinaryNode* getParent() { return this->parent; }
    	void        setParent(BinaryNode* p) { parent = p; }
    	BinaryNode* getLeft() { return this->left; }
    	void        setLeft(BinaryNode* l) { left = l; }
    	BinaryNode* getRight() { return this->right; }
    	void        setRight(BinaryNode* r) { right = r; }
    	int         getKey() { return this->key; }
    	void        setKey(int key) { this->key = key; }
    
    private:
    	BinaryNode* parent; // Eltern-Knoten
    	BinaryNode* left;   // linkes Kind
    	BinaryNode* right;  // rechtes Kind
    	int key;            // referenzierte Daten
    };
    
    
    class BinarySearchTree {
    public:
    	BinarySearchTree(void)
    	{
    		root = NULL;
    		arrOut = NULL;
    	}
    
    
    	BinaryNode* getRoot()
    	{
    		return root;
    	}
    
    	bool isEmpty(void) { return (root == NULL); }
    
    	// baut einen Binary-SearchTree auf!
    	void insert(int t) {
    		if (root == NULL) {
    			root = new BinaryNode(t);
    		}
    		else {
    			insertRecur(t, root);
    		}
    	}
    
    	// lösche Element aus Baum
    	void remove(BinaryNode* node)
    	{
    		// node ist Blatt
    		if (node->getRight() == NULL && node->getLeft() == NULL) {
    			removeLeaf(node);
    		}
    		// node hat einen Unterbaum
    		else if (node->getRight() == NULL || node->getLeft() == NULL) {
    			removeSingle(node);
    		}
    		// beide Teilbäume vorhanden: Tausche mit min. des re. Teilbaums
    		else {
    			BinaryNode* minRight = findMinBelow(node->getRight());
    			node->setKey(minRight->getKey());   // kopiere Inhalte
    			remove(minRight);  // muss Blatt oder Knoten ohne li. Teilbaum sein
    		}
    	}
    
    	void removeLeaf(BinaryNode* leaf)
    	{
    		if (leaf != root) { // Blatt ist nicht Wurzel
    			BinaryNode* parent = leaf->getParent();
    			if (parent->getLeft() == leaf) // linkes Kind 
    				parent->setLeft(NULL);
    			else                             // rechtes Kind
    				parent->setRight(NULL);
    		}
    		delete leaf;
    	}
    
    	void removeSingle(BinaryNode* node)
    	{
    		BinaryNode* child = (node->getLeft() == NULL ? node->getRight() : node->getLeft());
    		// Fall: Wurzel
    		if (node == root) {
    			root = child;
    			child->setParent(NULL);
    			delete node;
    		}
    		else {  // Fall: Zwischenknoten
    			BinaryNode* parent = node->getParent();
    			if (node == parent->getLeft()) { // linkes Kind von Eltern
    				parent->setLeft(child);
    			}
    			else { // rechtes Kind von Eltern
    				parent->setRight(child);
    			}
    			child->setParent(parent);
    			delete node;
    		}
    	}
    
    	// suche nach k; NULL als Ergebnis, falls k nicht vorhanden
    	BinaryNode* searchNode(int k)
    	{
    		return searchNodeRecur(root, k);
    	}
    
    	BinaryNode* searchNextNode(int k, BinaryNode* prior = NULL)
    	{
    		if (prior == NULL)
    			return searchNodeRecur(root, k);
    		else
    			return searchNodeRecur(prior->getRight(), k);
    	}
    
    	BinaryNode* findMin(void)
    	{
    		return findMinBelow(root);
    	}
    
    	BinaryNode* findMax(void)
    	{
    		return findMaxBelow(root);
    	}
    
    	BinaryNode* findPrev(BinaryNode* node) {
    		// linker Teilbaum vorhanden
    		if (node->getLeft() != NULL)
    			return findMaxBelow(node->getLeft());
    
    		// verfolge "linke Flanke" rückwarts
    		BinaryNode* parent = node->getParent();
    		while (parent != NULL && parent->getLeft() == node) {
    			node = parent;
    			parent = node->getParent();
    		}
    		return parent;
    	}
    
    	void inOrder(void) { inOrderRecur(root); }
    
    	//Liefert die Tiefe eines Baumes
    	int getMaxDepth(BinaryNode* node)
    	{
    		if (isEmpty())
    		{
    			return 0;
    		}
    		int d1 = 0;
    		int d2 = 0;
    		if (node->getLeft() != NULL) {
    			d1 = getMaxDepth(node->getLeft());
    		}
    		if (node->getRight() != NULL) {
    			d2 = getMaxDepth(node->getRight());
    		}
    		return (max(d1, d2) + 1);
    	}
    
    
    
    	/************************************************************************/
    	/* Hilfsfunktion zur Ausgabe des Baumes                                 */
    	/************************************************************************/
    	void printTree()
    	{
    		//unschön, weil schon mal woanders berechnet: 
    		int depth = getMaxDepth(root);
    		loadToArray(depth);
    		int nLineWidth = 2 << depth;
    
    		int idx = 0;
    		for (int d = 0; d < depth; d++) {
    			for (int j = 0; j < (1 << d); j++) {
    				int nNumSkips = (2 << (depth - d)) - 2;
    				for (int s = 0; s < nNumSkips / 2; s++) {
    					cout << " ";
    				}
    
    				if (arrOut[idx] >= 0) {
    					cout << arrOut[idx];
    				}
    				else {
    					cout << " ";
    				}
    				int nNumSpaces = (1 << (depth - d));
    				for (int s = 0; s < nNumSpaces; s++) {
    					cout << " ";
    				}
    				idx++;
    			}
    			cout << "|" << endl; //markiert das Zeilenende (zum debuggen...)
    		}
    	}
    
    
    private:
    
    	/************************************************************************/
    	/* Hilfsfunktion zur Ausgabe des Baumes                                 */
    	/************************************************************************/
    	void loadToArray(int depth)
    	{
    		//maximale Anzahl der Knoten im Baum
    		int maxNumNodes = int((1 << depth) - 1);
    		//arrOut ist das später sequenziell auszugebende Array.
    		if (arrOut != NULL)
    		{
    			delete[] arrOut;
    		}
    		arrOut = new int[maxNumNodes];
    		for (int i = 0; i < maxNumNodes; i++)
    		{
    			arrOut[i] = -1;
    		}
    		loadToArray(root, 0, 0);
    	}
    
    	/************************************************************************/
    	/* Hilfsfunktion zur Ausgabe des Baumes                                 */
    	/************************************************************************/
    	void loadToArray(BinaryNode* node, int depth, int index)
    	{
    		//j ist der Index des Arrays, wo der Knoten gespeichert werden muss.
    		int j = (1 << depth) + index - 1;
    		arrOut[j] = node->getKey();
    		if (node->getLeft() != NULL)
    		{
    			loadToArray(node->getLeft(), depth + 1, (index << 1) + 0);
    		}
    		if (node->getRight() != NULL)
    		{
    			loadToArray(node->getRight(), depth + 1, (index << 1) + 1);
    		}
    	}
    
    	// min-node unterhalb
    	BinaryNode* findMinBelow(BinaryNode* node)
    	{
    		while (node->getLeft() != NULL)
    			node = node->getLeft();
    
    		return node;
    	}
    
    	// max-node unterhalb
    	BinaryNode* findMaxBelow(BinaryNode* node)
    	{
    		while (node->getRight() != NULL)
    			node = node->getRight();
    
    		return node;
    	}
    
    
    	// rekursives Einfügen (Binary-SearchTree)!
    	void insertRecur(int t, BinaryNode* curr) {
    		// (rekursiv) links einfügen
    		if (curr->getKey() > t)
    		{
    			if (curr->getLeft() == NULL)
    			{
    				BinaryNode* newNode = new BinaryNode(t);
    				newNode->setParent(curr);
    				curr->setLeft(newNode);
    			}
    			else {
    				insertRecur(t, curr->getLeft());
    			}
    		}
    		// (rekursiv) rechts einfügen
    		else {
    			if (curr->getRight() == NULL) {
    				BinaryNode* newNode = new BinaryNode(t);
    				newNode->setParent(curr);
    				curr->setRight(newNode);
    			}
    			else {
    				insertRecur(t, curr->getRight());
    			}
    		}
    	}
    
    	// rekursive Suche
    	BinaryNode* searchNodeRecur(BinaryNode* node, int k)
    	{
    		if (node == NULL || node->getKey() == k)
    			return node;
    
    		if (k <= node->getKey())
    			return searchNodeRecur(node->getLeft(), k);
    		else
    			return searchNodeRecur(node->getRight(), k);
    	}
    
    
    	void inOrderRecur(BinaryNode* curr) {
    		if (curr) {
    			inOrderRecur(curr->getLeft());
    			cout << curr->getKey() << ", ";
    			inOrderRecur(curr->getRight());
    		}
    	}
    
    	BinaryNode* root;
    
    	int* arrOut;
    };
    
    int main()
    {
    	BinaryNode* res = NULL;
    
    	BinarySearchTree tree;
    	int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
    
    	/************************************************************************/
    	/* Rufen Sie hier Ihre Einfügeoperation auf                             */
    	/************************************************************************/
    
    	//tree.printTree(); //Kommentarzeichen entfernen
    
    	cout << "=====================================\n";
    	cout << "Sortiertes Ergebnis (in-order):\n";
    	//tree.inOrder();   //Kommentarzeichen entfernen
    	cout << endl;
    
    	return 0;
    }
    

    Ist die Aufgabe, dass ein Array[15] zu einem Binären Suchbaum eingefügt werden soll.
    Weiß vielleicht jemand, was genau ich nun implemieren soll oder einen Ansatz wie ich vorgehen kann ?

    Vielen Dank im Voraus.



  • @student35 sagte in Array in Binären Suchbaum umwandeln:

    Ist die Aufgabe, dass ein Array[15] zu einem Binären Suchbaum eingefügt werden soll.
    Weiß vielleicht jemand, was genau ich nun implemieren soll oder einen Ansatz wie ich vorgehen kann ?

    Was genau du implementieren sollst steht hoffentlich klar formuliert auf deinem Aufgabenblatt. Da ein Array als Ganzes einzufügen hier keinen Sinn macht, ist deine Aufgabenstellung vermutlich durch diesen Ansatz abgedeckt:

    1. Versuche zu verstehen, was die Member-Funktionen (Methoden) des BinarySearchTree machen (du solltest wissen, wie so ein Baum in der Theorie funktioniert).
    2. Finde die Member-Funktion, die ein Element in den Suchbaum einfügt.
    3. Rufe diese Member-Funktion des tree-Objekts für den Wert jedes Array-Elements auf (innerhalb einer Schleife über Array-Elemente).

    P.S.: Über den mangelhalften Vorgabe-Code schweige ich mich mal weitgehend aus und frage mich, warum man für sowas nicht einfach Java/C# oder so nimmt. Damit kann man sich wunderbar und aus dem Stand aufs wesentliche konzentrieren, wenn man Algorithmen und Datenstrukturen lehren will. Da muss man dann auch kein schlechtes C++ machen, nur weil C++ ne Wissenchaft für sich ist und man da keine Zeit für hat, weil ja A&D gemacht werden soll. 😞 ... kannste natürlich nix für, @student35 ... ich erwähne das nur weil man hier im Forum leider oft gruseligen Dozenten-Code zu sehen bekommt. Falsche Sprachwahl für das Problem "lehre A&D" IMHO.



  • Hallo @Finnegan,
    Danke für deine Antwort, mittlerweile hab ich es geschafft 🙂



  • @student35
    Ne Lösung zu posten wäre schön, damit andere auch was davon haben.



  • #include <iostream>
    #include <math.h>
    #include <assert.h>
    using namespace std;
    
    class BinaryNode {
    
    public:
    	BinaryNode(int key) {
    		this->key    = key;
    		this->parent = this->left = this->right = NULL;
    	}
    
    	BinaryNode* getParent()              { return this->parent;  }
    	void        setParent(BinaryNode* p) { parent = p; }
    	BinaryNode* getLeft()                { return this->left;  }
    	void        setLeft(BinaryNode* l)   { left = l; }
    	BinaryNode* getRight()               { return this->right; }
    	void        setRight(BinaryNode* r)  { right = r; }
    	int         getKey()                 { return this->key;  }
    	void        setKey(int key)          { this->key = key;  }
    
    private:
    	BinaryNode* parent; // Eltern-Knoten
    	BinaryNode* left;   // linkes Kind
    	BinaryNode* right;  // rechtes Kind
    	int key;            // referenzierte Daten
    };    
    
    
    class BinarySearchTree {
    public:
    	BinarySearchTree(void)   
    	{ 
    		root = NULL; 
    		arrOut = NULL;
    	}
    
    
    	BinaryNode* getRoot()
    	{
    		return root;
    	}
    
    	bool isEmpty(void) { return (root == NULL); }
    
    	// baut einen Binary-SearchTree auf!
    	void insert(int t) {
    		if ( root == NULL ) {
    			root = new BinaryNode(t);
    		}
    		else {
    			insertRecur(t, root);
    		}
    	}
    
    	// lösche Element aus Baum
    	void remove(BinaryNode* node)
    	{
    		// node ist Blatt
    		if ( node->getRight() == NULL && node->getLeft() == NULL ) { 
    			removeLeaf(node);
    		}
    		// node hat einen Unterbaum
    		else if ( node->getRight() == NULL || node->getLeft() == NULL ) { 
    			removeSingle(node);
    		}
    		// beide Teilbäume vorhanden: Tausche mit min. des re. Teilbaums
    		else {
    			BinaryNode* minRight = findMinBelow(node->getRight());
    			node->setKey(minRight->getKey());   // kopiere Inhalte
    			remove(minRight);  // muss Blatt oder Knoten ohne li. Teilbaum sein
    		}
    	}
    
    	void removeLeaf(BinaryNode* leaf)
    	{
    		if ( leaf != root ) { // Blatt ist nicht Wurzel
    			BinaryNode* parent = leaf->getParent();
    			if ( parent->getLeft() == leaf ) // linkes Kind 
    				parent->setLeft(NULL);
    			else                             // rechtes Kind
    				parent->setRight(NULL);
    		}
    		delete leaf;
    	}
    
    	void removeSingle(BinaryNode* node)
    	{
    		BinaryNode* child= (node->getLeft()==NULL ? node->getRight():node->getLeft());
    		// Fall: Wurzel
    		if ( node == root ) {
    			root = child;
    			child->setParent(NULL);
    			delete node;
    		}
    		else {  // Fall: Zwischenknoten
    			BinaryNode* parent = node->getParent();
    			if ( node == parent->getLeft() ) { // linkes Kind von Eltern
    				parent->setLeft(child);
    			}
    			else { // rechtes Kind von Eltern
    				parent->setRight(child);
    			}
    			child->setParent(parent);
    			delete node;
    		}
    	}
    
    	// suche nach k; NULL als Ergebnis, falls k nicht vorhanden
    	BinaryNode* searchNode(int k) 
    	{ return searchNodeRecur(root, k); }
    
    	BinaryNode* searchNextNode(int k, BinaryNode* prior=NULL) 
    	{ 
    		if ( prior == NULL ) 
    			return searchNodeRecur(root, k); 
    		else
    			return searchNodeRecur(prior->getRight(), k); 
    	}
    
    	BinaryNode* findMin(void) 
    	{ return findMinBelow(root); }
    
    	BinaryNode* findMax(void) 
    	{ return findMaxBelow(root); }
    
    	BinaryNode* findPrev(BinaryNode* node) {
    		// linker Teilbaum vorhanden
    		if ( node->getLeft() != NULL )          
    			return findMaxBelow(node->getLeft());
    
    		// verfolge "linke Flanke" rückwarts
    		BinaryNode* parent = node->getParent(); 
    		while ( parent != NULL && parent->getLeft() == node ) {
    			node   = parent;
    			parent = node->getParent();
    		}
    		return parent;
    	}
    
    	void inOrder(void)   { inOrderRecur(root); }
    
    	//Liefert die Tiefe eines Baumes
    	int getMaxDepth(BinaryNode* node) 
    	{
    		if(isEmpty())
    		{
    			return 0;
    		}
    		int d1 = 0; 
    		int d2 = 0;
    		if(node->getLeft() != NULL) {
    			d1 = getMaxDepth(node->getLeft());
    		}
    		if(node->getRight() != NULL) {
    			d2 = getMaxDepth(node->getRight());
    		}
    		return (max(d1,d2) + 1);
    	}
    
    
    
    	/************************************************************************/
    	/* Hilfsfunktion zur Ausgabe des Baumes                                 */
    	/************************************************************************/
    	void printTree()
    	{
    		//unschön, weil schon mal woanders berechnet: 
    		int depth = getMaxDepth(root);
    		loadToArray(depth);
    		int nLineWidth = 2 << depth;
    
    		int idx = 0;
    		for(int d = 0; d < depth; d++) {
    			for(int j = 0; j < (1 << d); j++) {
    				int nNumSkips = (2<<(depth-d))-2;
    				for(int s = 0; s < nNumSkips/2; s++) {
    					cout << " ";
    				}
    
    				if (arrOut[idx] >= 0) {
    					cout << arrOut[idx];
    				} else {
    					cout << " ";
    				}
    				int nNumSpaces = (1<<(depth-d));
    				for(int s = 0; s < nNumSpaces; s++) {
    					cout << " ";
    				}
    				idx++;
    			}
    			cout << "|" << endl; //markiert das Zeilenende (zum debuggen...)
    		}
    	}
    
    
    private:
    
    	/************************************************************************/
    	/* Hilfsfunktion zur Ausgabe des Baumes                                 */
    	/************************************************************************/
    	void loadToArray(int depth)
    	{
    		//maximale Anzahl der Knoten im Baum
    		int maxNumNodes = int((1 << depth) - 1);
    		//arrOut ist das später sequenziell auszugebende Array.
    		if(arrOut!=NULL) 
    		{
    			delete [] arrOut;
    		}
    		arrOut = new int[maxNumNodes];
    		for(int i = 0; i < maxNumNodes; i++)
    		{
    			arrOut[i] = -1;
    		}
    		loadToArray(root,0,0);
    	}
    
    	/************************************************************************/
    	/* Hilfsfunktion zur Ausgabe des Baumes                                 */
    	/************************************************************************/
    	void loadToArray(BinaryNode* node, int depth, int index)
    	{	 
    		//j ist der Index des Arrays, wo der Knoten gespeichert werden muss.
    		int j =  (1 << depth) + index - 1;
    		arrOut[j] = node->getKey();
    		if(node->getLeft() != NULL)
    		{
    			loadToArray(node->getLeft(), depth + 1, (index << 1) + 0);
    		}
    		if(node->getRight() != NULL)
    		{
    			loadToArray(node->getRight(), depth + 1, (index << 1) + 1);
    		}	  
    	}
    
    	// min-node unterhalb
    	BinaryNode* findMinBelow(BinaryNode* node) 
    	{
    		while ( node->getLeft() != NULL )
    			node = node->getLeft();
    
    		return node;
    	}
    
    	// max-node unterhalb
    	BinaryNode* findMaxBelow(BinaryNode* node) 
    	{
    		while ( node->getRight() != NULL )
    			node = node->getRight();
    
    		return node;
    	}
    
    
    	// rekursives Einfügen (Binary-SearchTree)!
    	void insertRecur(int t, BinaryNode *curr) {
    		// (rekursiv) links einfügen
    		if ( curr->getKey() > t ) 
    		{
    			if ( curr->getLeft() == NULL ) 
    			{
    				BinaryNode* newNode = new BinaryNode(t);
    				newNode->setParent(curr);
    				curr->setLeft(newNode); 
    			}
    			else {
    				insertRecur(t, curr->getLeft());
    			}
    		}
    		// (rekursiv) rechts einfügen
    		else {
    			if ( curr->getRight() == NULL ) {
    				BinaryNode* newNode = new BinaryNode(t);
    				newNode->setParent(curr);
    				curr->setRight(newNode); 
    			}
    			else {
    				insertRecur(t, curr->getRight());
    			}
    		}
    	}
    
    	// rekursive Suche
    	BinaryNode* searchNodeRecur(BinaryNode* node, int k) 
    	{
    		if ( node == NULL || node->getKey() == k )
    			return node;
    
    		if ( k <= node->getKey() ) 
    			return searchNodeRecur(node->getLeft(), k);
    		else                      
    			return searchNodeRecur(node->getRight(), k);
    	}
    
    
    	void inOrderRecur(BinaryNode* curr) {
    		if ( curr ) {
    			inOrderRecur(curr->getLeft());
    			cout << curr->getKey() << ", ";
    			inOrderRecur(curr->getRight());
    		}
    	}
    
    	BinaryNode* root;
    
    	int* arrOut;
    };
    
    void myInsert(BinarySearchTree* tree, int* a, int start, int end)
    {
    	if (start == end)
    		return;
    
    	int mid = (start + end) / 2;
    	tree->insert(a[mid]);
    
    	myInsert(tree, a, start, mid);
    	myInsert(tree, a, mid+1, end);
    }
    
    int main()
    {
    	BinaryNode* res = NULL;
    
    	BinarySearchTree tree;
    	int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
    
    	myInsert(tree, a, 0, 15);
    
    	tree.printTree(); 
    
    	cout << "=====================================\n"; 
    	cout << "Sortiertes Ergebnis (in-order):\n"; 
    	tree.inOrder();   
    	cout << endl;
    	
    	return 0;
    }
    

    Das wäre meine Lösung.
    Gäbe es Verbesserungen oder fählt jemand ein Fehler aus ?



  • @student35 sagte in Array in Binären Suchbaum umwandeln:

    Das wäre meine Lösung.
    Gäbe es Verbesserungen oder fählt jemand ein Fehler aus ?

    Habs jetzt nur grob überflogen, sieht abr okay aus. Ich kenne die genauen Anforderungen immer noch nicht, aber ich hätte erwartet, dass eine simple insert-Schleife gereicht hätte.

    Schön ist allerdings, dass du mit deinem rekursiven "Midpoint-Insert" gleich einen balanchierten baum erzeugst, wenn das Array sortiert ist - zumindest wenn ich das auf die Schnelle richtig interpretiere. Beim Schleifen-Insert wäre der baum für dieses spezielle Array sonst zu einer verketteten Liste degeneriert (die natürlich immer noch ein Binärer Baum ist, nur eben nicht sonderlich balanciert).

    Das fürht so natürlich nicht immer zu balancierten Bäumen, aber ich vermute das kommt wahrschenlich als nächstes dran, wie man die mit beliebigen Inputs ohne vorheriges Sortieren erzeugt.

    P.S.: Ich sagte ja ich habs nur überflogen - hast du das überhaupt mal kompiliert? Wie funktioniert das mit dem BinarySearchTree*-Parameter, dem du ein Nicht-Pointer-Variable übergibst? Bau das mal und lass es laufen - ich dachte du hättest das schon gemacht und überprüft, ob das Ergebnis korrekt ist (???).



  • @Finnegan .. du hast recht, mir wurden eigentlich keine Fehler angezeigt und weil ich gerade an einem anderen Projekt sitze, habe ich es eben nicht kompiliert. Da muss noch mal drüber schauen. Danke für den Hinweis, wäre mir garnicht mehr ausgefallen ☺


Log in to reply