Baum

Hallo
ich bin gerade dabei mich ein wenig in ADT's reinzufuchsen, doch leider bleib ich an den Bäumen hängen.
Folgenden Baum will ich erzeugen

8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13

Wäre euch sehr verbunden wenn ihr mir meinen Denkfehler vor Augen führt.
hier mein Versuch den Baum zu implementieren: (vergesst showTree() )

#include "stdafx.h"
#include "stdlib.h"

typedef struct Tree{
int key;
struct Tree *left;
struct Tree *right;
struct Tree *parent;
};

static struct Tree *root;

void insTree(int key){
struct Tree *temp = root;
bool isLeaf = false;
temp = (Tree *)malloc(sizeof(struct Tree));
//falls Tree leer
if(root == NULL){
root = temp;
temp->key = key;
temp->parent = NULL;
temp->right = NULL;
temp->left = NULL;
}
else{
temp = root;
while(isLeaf == false){
//bleibt hier hängen
if(key <= temp->key){
if(temp->left == NULL) isLeaf = true;
else temp = temp->left;
}
else{
if(temp->right == NULL) isLeaf = true;
else temp = temp->right;
}
}
}
//Einfügen des neuen Blattes
if(key <= temp->key){
temp->parent = temp;
temp->left = temp;
temp->right = NULL;
temp->key = key;
}
if(key > temp->key){
temp->parent = temp;
temp->right = temp;
temp->left = NULL;
temp->key = key;
}
}

void showTree(){
struct Tree *element = root;
printf("\n%i", element->key);
}

int main(void){
root = NULL;
insTree(8);
insTree(3);
insTree(10);
insTree(1);
insTree(6);
insTree(14);
insTree(4);
insTree(7);
insTree(13);
showTree();
}

Mario Sandler

Benutzt bitte code-Tags, dass kann ja kein Mensch lesen.
Vll wärs auch net schlecht wenn du uns sagen würdest wo genau dein Problem ist

CStoll

Erstens: sfds

Zeitens:

temp = (Tree *)malloc(sizeof(struct Tree)); 
//falls Tree leer 
if(root == NULL){ 
  ...
} 
else
{ 
  temp = root; // MEMORY-LEAK
  ...

In Zeile 8 biegst du den Zeiger 'temp' um auf die Wurzel des bisherigen Baumes - damit verlierst du den Bezug zu dem Speicherplatz, den du für den neuen Knoten vorbereitet hast.

<sorry> für die Formatierung, bin neu im Forum
Hallo
ich bin gerade dabei mich ein wenig in ADT's reinzufuchsen, doch leider bleib ich an den Bäumen hängen.
Folgenden Baum will ich erzeugen

Wäre euch sehr verbunden wenn ihr mir meinen Denkfehler vor Augen führt.
hier mein Versuch den Baum zu implementieren: (vergesst showTree() )

#include "stdafx.h"
#include "stdlib.h"

typedef struct Tree{
	int key;
	struct Tree *left;
	struct Tree *right;
	struct Tree *parent;
};

static struct Tree *root;

void insTree(int key){
	struct Tree *temp = root;
	bool isLeaf = false;
	temp = (Tree *)malloc(sizeof(struct Tree));
	//Wurzel
        if(root == NULL){
		root = temp;
		temp->key = key;
		temp->parent = NULL;
		temp->right = NULL;
		temp->left = NULL;
	}
	//Auffinden der Stelle für das neue Blatt
        else{
		temp = root;
		while(isLeaf == false){
                        //Debuger bleibt in der IF Bedingung hängen (ka wieso)
			if(key <= temp->key){
				if(temp->left == NULL) isLeaf = true;
				else temp = temp->left;
			}
			else{
				if(temp->right == NULL) isLeaf = true;
				else temp = temp->right;
			}
		}
	}
	if(key <= temp->key){
		temp->parent = temp;
		temp->left = temp;
		temp->right = NULL;
		temp->key = key;
	}
	if(key > temp->key){
		temp->parent = temp;
		temp->right = temp;
		temp->left = NULL;
		temp->key = key;
	}
}

void showTree(){
	struct Tree *element = root;
	printf("\n%i", element->key);
}

int main(void){
	root = NULL;
	insTree(8);
	insTree(3);
	insTree(10);
	insTree(1);
	insTree(6);
	insTree(14);
	insTree(4);
	insTree(7);
	insTree(13);
	showTree();
}

CStoll

Selbst wenn der Quelltext jetzt schöner formatiert ist, das obengenannte Problem besteht immer noch - mit der Zuweisung 'temp=root;' verlierst du den letzten möglichen Zugriff auf den per malloc() angeforderten Speicher, danach überschreibst du das jeweils letzte gefundene Blatt mit den neuen Daten.

Zur Lösung benötigst du einen zweiten Tree*, mit dem du die Einfügestelle suchen kannst (oder du veschiebst das malloc() bis zu der Stelle, wo du die Zielposition hast und ein neues Blatt erzeugen willst).

also die neue Formatierung hab ich in dem Moment erstellt als Cstol seine Antwort gepostet hat, also hab ich davon nix mitbekommen.
Aber danke für eure Hinweise ich hab es jetzt folgendermaßen gelöst,
allerdings bleibt der Debuger jetzt an den Stellen hängen an denen ich einen Pointer von element(Parentknoten an den temp angefügt werden soll) auf temp setzen will
Wie gesagt ich bin Anfänger seht es mir bitte nach.

[code]
[ccp]
void insTree(int key){
struct Tree *temp;
struct Tree *element = root;
bool isLeaf = false;
temp = (Tree *)malloc(sizeof(struct Tree));
if(root == NULL){
root = temp;
temp->key = key;
temp->parent = NULL;
temp->right = NULL;
temp->left = NULL;
}
else{
while(isLeaf == false){
if(key <= element->key){
if(element->left == NULL) isLeaf = true;
else{
element = element->left;
}
}
else{
if(element->right == NULL) isLeaf = true;
else{
element = element->right;
}
}
}
}
if(key <= temp->key){
element->left = temp;//Debuger bleibt hängen
temp->parent = element;
temp->left = NULL;
temp->right = NULL;
temp->key = key;
}
if(key > temp->key){
element->right = temp;//Debuger bleibt hängen
temp->parent = element;
temp->right = NULL;
temp->left = NULL;
temp->key = key;
}
}
[/ccp]
[/code

Joey

OMG ich weiß was ihr jetzt zum letzten Post sagen wollt, sry!
kann das jemand löschen?

---also die neue Formatierung hab ich in dem Moment erstellt als Cstol seine Antwort gepostet hat, also hab ich davon nix mitbekommen.
Aber danke für eure Hinweise ich hab es jetzt folgendermaßen gelöst,
allerdings bleibt der Debuger jetzt an den Stellen hängen an denen ich einen Pointer von element(Parentknoten an den temp angefügt werden soll) auf temp setzen will
Wie gesagt ich bin Anfänger seht es mir bitte nach. ---

void insTree(int key){
	struct Tree *temp;
	struct Tree *element = root;
	bool isLeaf = false;
	temp = (Tree *)malloc(sizeof(struct Tree));
	if(root == NULL){
		root = temp;
		temp->key = key;
		temp->parent = NULL;
		temp->right = NULL;
		temp->left = NULL;
	}
	else{
		while(isLeaf == false){
			if(key <= element->key){
				if(element->left == NULL) isLeaf = true;
				else{
					element = element->left;
				}
			}
			else{
				if(element->right == NULL) isLeaf = true;
				else{
					element = element->right;
				}
			}
		}
	}
	if(key <= temp->key){
		element->left = temp;//Debuger mag diese Stelle nicht
		temp->parent = element;
		temp->left = NULL;
		temp->right = NULL;
		temp->key = key;
	}
	if(key > temp->key){
		element->right = temp;//Debuger mag diese Stelle nicht
		temp->parent = element;
		temp->right = NULL;
		temp->left = NULL;
		temp->key = key;
	}
}

CStoll

Und was genau sagt der Debugger an diesen Stellen, wo er hängenbleibt?

(btw, der Teil, der in beiden Zweigen identisch abläuft, kann aus dem if() herausgezogen werden. Und anstelle zweier gegenläufiger if()s kannst du auch if()-else verwenden)

PS: Ist es eigentlich Absicht, daß du nach der Schleife key mit 'temp->key' vergleichst? (das zu vergleichende Baumelement ist in 'element')

Joey

if(key <= element->key){//Protest des Debugers
	element->left = temp;
	temp->parent = element;
	temp->left = NULL;
	temp->right = NULL;
	temp->key = key;
}

Debuger:
element 0x00000000 {key=??? left=??? right=??? ...} Tree *
key CXX0030: Fehler: Ausdruck kann nicht ausgewertet werden
left CXX0030: Fehler: Ausdruck kann nicht ausgewertet werden
right CXX0030: Fehler: Ausdruck kann nicht ausgewertet werden
parent CXX0030: Fehler: Ausdruck kann nicht ausgewertet werden

PS. kann mal bitte ein Moderator, die misslungenen Posts von mir entfernen? thx

Joey

Hab meinen Fehler gefunden, die letzten beiden IF-Konstrukte gehören in den Else Zweig, und nicht auserhalb.
Danke für eure Hilfe.