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:
- Versuche zu verstehen, was die Member-Funktionen (Methoden) des
BinarySearchTree
machen (du solltest wissen, wie so ein Baum in der Theorie funktioniert). - Finde die Member-Funktion, die ein Element in den Suchbaum einfügt.
- 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.
- Versuche zu verstehen, was die Member-Funktionen (Methoden) des
-
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