carlos1976
Grünschnabel
Hallo zusammen,
ich habe folgendes Problem, ich möchte einen sortierten Array int a[] = {1, 2, ..., 15} in einen Biänaren Suchbaum umwandeln der vollständig ausgeglichen ist.
Dazu hab ich folgende 2 Funktionen zur Verfügung die die Wurzel und die Blätter erzeugen:
So bekommt man den Baum ausgeglichen:
1. Der Median (mittlere Wert) der Schlüssel wird zur Wurzel.
2. Die Schlüssel die kleiner als dieser Median sind, bilden den linken Teilbaum
der Wurzel, während die grösseren Schlüssel den rechten Teilbaum bilden.
3. Das gleiche Vorgehen wird dann angewendet um die Teilbäume zu bilden.
Wie implementiere ich eine Funktion, die die Elemente eines (beliebigen) sortierten
Arrays in einer Reihenfolge einfügt, die einen vollständig ausgeglichenen Suchbaum
entstehen lässt?
Danke für Eure Hilfe!
Hier der gesamte Code:
ich habe folgendes Problem, ich möchte einen sortierten Array int a[] = {1, 2, ..., 15} in einen Biänaren Suchbaum umwandeln der vollständig ausgeglichen ist.
Dazu hab ich folgende 2 Funktionen zur Verfügung die die Wurzel und die Blätter erzeugen:
Code:
void insert(int t) {
if ( root == NULL ) {
root = new BinaryNode(t);
}
else {
insertRecur(t, root);
}
}
Code:
// 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());
}
}
}So bekommt man den Baum ausgeglichen:
1. Der Median (mittlere Wert) der Schlüssel wird zur Wurzel.
2. Die Schlüssel die kleiner als dieser Median sind, bilden den linken Teilbaum
der Wurzel, während die grösseren Schlüssel den rechten Teilbaum bilden.
3. Das gleiche Vorgehen wird dann angewendet um die Teilbäume zu bilden.
Wie implementiere ich eine Funktion, die die Elemente eines (beliebigen) sortierten
Arrays in einer Reihenfolge einfügt, die einen vollständig ausgeglichenen Suchbaum
entstehen lässt?
Danke für Eure Hilfe!
Hier der gesamte Code:
Code:
#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;
}
