Durschnittliche Pfadlänge (Baum)

Noch nen Tip zu Beweis, versuch doch mal nen Binärbaum mit 16 Elementen zu bauen, dessem durschnittliche Pfadlänge != 4 ist

volkard

void printTree( Node* treeRoot , int len)
{
if ( treeRoot != NULL )
{
printTree(treeNode->left,len+1);
cout << treeRoot->data <<' '<<len<< endl;
printTree(treeNode->right,len+1);
}
}

so könntest du zu jedem wert auch noch ausgeben, wie lang der pfad dahin war.

und das dann nicht ausgeben, sondern auf eine *hüstel* globale variable aufaddieren und nachher durch die anzahl der elemente teilen.

Sengi

vielen dank. werd ich gleich direkt mal machen und dann mal hier eine endfassung posten vielleicht gibts ja später mal welche die sich dafür interessieren *G*

Sengi

hmm irgendwie kommt da nciht so ganz raus was raus kommen soll... als pfadlänge wird immer nur eine einzige 1 ausgegeben *grübel*

#include <iostream>
using namespace std;

struct Node
{
	int data;
	Node* left;
	Node* right;
};

int pfad_gesamt = 0;

Node* newLeafNode ( int data )
{
	Node* new_node = new Node;
	new_node ->data = data;
	new_node->left = NULL;
	new_node->right = NULL;

	return new_node;
};

Node* insertLeafNode ( Node* treeRoot, int data )
{
	if (treeRoot == NULL)	
	{
		return newLeafNode(data);
	}

	if ( data <= treeRoot->data )
	{
		treeRoot->left = insertLeafNode(treeRoot->left, data);
	}
	else
	{
		treeRoot->right = insertLeafNode(treeRoot->right, data);
	}
};

/** Iterative Implementation
Node* insertLeafNode( Node* treeRoot, int data )
{
    Node** nPtr = &treeRoot;
    while ( *nPtr != NULL )
    {
        Node* n = *nPtr;
        if ( data <= n->data )
            nPtr = &n->left;
        else
            nPtr = &n->right;
    }
    *nPtr = newLeafNode(data);
    return treeRoot;
}
**/

void printTree( Node* treeRoot, int len)
{
	if ( treeRoot != NULL )
	{
		printTree(treeRoot->left,len+1);
		cout << len << endl;
		pfad_gesamt += len;
		printTree(treeRoot->right,len+1);
	}
}

int main()
{
	int pfad_gesamt = 0;
	Node* treeRoot = NULL;
	int data,data_anzahl;

	cout << "Werteeingabe: ";
	cin >> data;

	while ( data >= 0 )
	{
		treeRoot = insertLeafNode(treeRoot,data);
		cout << "Werteeingabe: ";
		cin >> data;
		data_anzahl++;
	}

	cout << "Binaerer Baum: " << endl;
	printTree(treeRoot,1);

	return 0;

}

hab nur kein plan warum

volkard

Sengi schrieb:

hmm irgendwie kommt da nciht so ganz raus was raus kommen soll... als pfadlänge wird immer nur eine einzige 1 ausgegeben *grübel*

hab nur kein plan warum

gut, daß du fragst. mir scheint, insertLeafNode gibt meistens unfug zurück. es kann in diesen baum nur das erst blatt gehängt werden, wie das da aussieht.

Sengi

und warum? ich seh gerade in der funktion keinen fehler...

Bashar

Da fehlt offensichtlich mindestens eine return-Anweisung. Sowas sollte man schon sehen :p

Sengi

*kopf gegen wand hau* thx

finix

Sengi schrieb:

Ich habe hier einen binäre Baum und soll folgendes die durchschnittliche Anzahl von Knoten eines Pfades = mittlere Pfadlänge ausgeben.

Beim Einfügen die Länge des Pfades auf die Gesamtlänge addieren, (beim Entfernen substrahieren,) durch die ebenso gespeicherte Anzahl der Knoten dividieren.
Den Baum am besten in eine Klasse packen, sonst husten sich hier sicher noch einige zu Tode wenn sie deine globalen Variablen sehen
(Als Template?)

Sengi schrieb:

hmm irgendwie kommt da nciht so ganz raus was raus kommen soll... als pfadlänge wird immer nur eine einzige 1 ausgegeben *grübel*

Was gibst du denn für Werte ein? Kann es sein das deine 1 in der Tat sofort gefunden wird?

Sengi schrieb:

int pfad_gesamt = 0;
// ...

int main()
{
  int pfad_gesamt = 0;
  // ...
}

Du greifst nirgends auf pfad_gesamt in main zu, und es macht wohl auch nicht was du denkst: in main überdeckt es dein globales pfad_gesamt, deine Funktionen "sehen" nur das globale.
Lass das am besten ganz weg, mach ne Klasse, ansonsten schau dir noch mal an was wie wo überdeckt und/oder sichtbar ist.

Davon ab, wie volkard schon feststellte ist deine rekursive insertLeafNode Funktion kaputt; sie gibt (abgesehen von anderen Fehlern?) ausschließlich für die Wurzel den neuen Knoten zurück, sollte sich so eigentlich nicht (zumindest nicht ohne Warnings) kompilieren lassen.

Außerdem bietet sich eine "private" Suchfunktion an, die entweder den Knoten des gesuchten Werts oder, falls nicht vorhanden, den potentiellen Elternknoten zurückliefert. Macht alles ein wenig einfacher.

Tipps für google: AVL, BB[alpha], Red Black Tree, ...

Sengi

ok gut danke

templates soweit waren wir leider noch nicht.
hab das alles nun mal berücksichtigt (oder es versucht) und dabei ist dann das hier rausgekommen:

#include <iostream>
using namespace std;

struct Node
{
    int data;
    Node* left;
    Node* right;
};

int pfad_gesamt = 0;

Node* newLeafNode ( int data )
{
    Node* new_node = new Node;
    new_node ->data = data;
    new_node->left = NULL;
    new_node->right = NULL;

    return new_node;
};

Node* insertLeafNode ( Node* treeRoot, int data )
{
    if (treeRoot == NULL)   
    {
        return newLeafNode(data);
    }

    if ( data <= treeRoot->data )
    {
        treeRoot->left = insertLeafNode(treeRoot->left, data);
    }
    else
    {
        treeRoot->right = insertLeafNode(treeRoot->right, data);
    }
	return treeRoot;
};

/** Iterative Implementation
Node* insertLeafNode( Node* treeRoot, int data )
{
    Node** nPtr = &treeRoot;
    while ( *nPtr != NULL )
    {
        Node* n = *nPtr;
        if ( data <= n->data )
            nPtr = &n->left;
        else
            nPtr = &n->right;
    }
    *nPtr = newLeafNode(data);
    return treeRoot;
}
**/

void printTree( Node* treeRoot, int len)
{
    if ( treeRoot != NULL )
    {
        printTree(treeRoot->left,len+1);
        cout << "Länge: " << len << endl;
		pfad_gesamt += len;
        printTree(treeRoot->right,len+1);
    }
}

int main()
{

    Node* treeRoot = NULL;
    int data,data_anzahl = 0;
	double ergebnis;

    cout << "Werteeingabe: ";
    cin >> data;

    while ( data >= 0 )
    {
        treeRoot = insertLeafNode(treeRoot,data);
        cout << "Werteeingabe: ";
        cin >> data;
        data_anzahl++;
    }

    cout << "Binaerer Baum - Statistik - : " << endl;
    printTree(treeRoot,1);
	cout << "Summe aller Pfade: " << pfad_gesamt << endl;
	ergebnis = pfad_gesamt / data_anzahl;
	cout << "Anzahl an Elementen: " << data_anzahl << endl;
	cout << "Pfadmittelwert " << ergebnis << endl;

    return 0;

}

bissle besser?

Jester

Gast2222111 schrieb:

Noch nen Tip zu Beweis, versuch doch mal nen Binärbaum mit 16 Elementen zu bauen, dessem durschnittliche Pfadlänge != 4 ist

Kein Problem.

Gehe einfach beim einfügen so vor, wie es im Code geschrieben wird.

Füge jetzt die Elemente 1,...,16 in genau dieser Reihenfolge ein.
Die durchschnittliche Pfadlänge wird dann 8 sein oder sowas in der Gegend zumindest.

Bei ausbalancierten Bäumen stimmt's natürlich.