Binary Tree für ein Wöterbuch

torgem

Hi!
Ich habe folgendes Problem. Ich will einen Binary Tree erzeugen. Ich habe eine Hand voll Wörter, die ich in der richtigen (alphabetischen) Reihenfolge in den Baum einfügen muss. Eine Funktion, die einen Knoten erzeugt, ist gegeben:

/*************************************************/
/*Name: init_node
**Purpose: Initialize one node
**Parameters: a word and two pointers to different nodes
**Returns: pointer to a binary tree node or NULL if unsuccessful
**Note: the casting
*************************************************/
BTREE init_node(char *word, BTREE p1, BTREE p2){
   BTREE    t;
   int len;

   if((t=new_node()) == NULL)
      fprintf(stderr,"Error from new_node(): NULL-pointer returned");
   else{
      len=strlen(word);
      t->str =malloc(len*sizeof(char)+1);
      strcpy(t->str,word);
      t->left = p1;
      t->right = p2;
   }/* end of if */
   return t;
}/* end of init_node */

Ich brauche eine rekursive insert Funktion, die den Baum anlegt...

feigling

static struct dict_node *
dict_add_node(struct dict_node *node, struct dict_node *new_node)
{
	int cmp;

	if(!node)
		node = new_node;
	else if((cmp = strcasecmp(new_node->key, node->key)) < 0)
		node->left = dict_add_node(node->left, new_node);
	else if(cmp > 0)
		node->right = dict_add_node(node->right, new_node);

	return node;
}

Viel Spass.

torgem

Danke für den Code! Aber ich muss die vorgegebene init_node Funktion benutzen...

c.rackwitz

def make_tree(value, left, right):
    return (value, left, right)

def tree_value(t):
    return t[0]

def tree_left(t):
    return t[1]

def tree_right(t):
    return t[2]

def ins_value(v, tree):
    if tree == ():
        return make_tree(v, (), ())
    else:
        if v == tree_value(tree):
            return tree
        elif v < tree_value(tree):
            return make_tree(tree_value(tree),
                             ins_value(v, tree_left(tree)),
                             tree_right(tree))
        elif v > tree_value(tree):
            return make_tree(tree_value(tree),
                             tree_left(tree),
                             ins_value(v, tree_right(tree)))

viel spass, sollte lesbarer pseudocode (python) sein. hab absichtlich arrays statt "structs" verwendet.

edit: b-tree != binaerer baum.
b-trees sind spezielle baeume, die selbstbalancierend sind. du willst selbstbalanciertende baeume. lies dich dazu in die materie ein.

torgem

Benötige den Code in C. Kenne mich mit Python leider nicht so gut aus

c.rackwitz

denk dir einfach das waere pseudocode.

was ist eigentlich dein problem?

wie man ein element in einen baum einfuegt

wie man das in c schreibt

torgem

Beides

Also es sieht folgendermaßen aus. Ich habe einen Textfile mit einem längeren Text. Dort extrahiere ich mit fgets() und strtok() die einzelnen Wörter raus und lege diese in einem Array ab. Nun muss ich diese Wörter in alphabetischer Reihenfolge in einen binären Suchbaum übertragen und dabei die im Headerfile (siehe oben) definierte Funktion init_node benutzen. Jetzt weiß ich nicht genau wie ich eine rekursive Funktion zum richtigen Einfügen der Wörter in den Suchbaum in C implementiere. Ich muss ja immer ein Wort und dann noch zwei Poiter zu Knoten übergeben. Das ist mein Problem...

pass auf: die einfuegefunktion nimmt einen baum und einen string. sie gibt einen (neuen) baum zurueck.
also haben wir
BTREE insert(char *word, BTREE *tree);

jetzt musst du wissen, welche faelle die funktion haben kann:
enweder der baum ist leer (also == NULL)
oder der baum ist nicht leer (dann sehen wir weiter)

wenn tree==NULL, dann gibst du einfach einen neuen baum zurueck, naemlich so:
return init_node(word, NULL, NULL);

deine init_node funktion ist falsch, weil sie fuer die zweige keine pointer akzeptiert. das BTREE struct muss ebenfalls pointer und keine weiteren structs des selben typs in sich haben.

ist tree != NULL (nach dem return bei tree==NULL steht das fest), dann hast du folgende faelle:
strcmp(word, tree->str)...
== 0
> 0
< 0

bei ==0 ist offensichtlich, dass das wort schon im baum ist.
bei <0 und >0 gibst du einen neuen baum zurueck, der so aufgebaut ist:
hat tree->str als str
hat den einen zweig genau wie tree
der andere zweig wird so erstellt:
- dynamisch speicher holen
- *newmemory = insert(word, tree->left oder right);
- dann einfach diesen pointer als neuen zweig angeben

torgem

void addleaf(BTREE * root, char * word) {

	/*Check if the current node is still empty*/
        if(*root == NULL) {
		/*Add a new leaf to the tree!*/
                (*root) = init_node(word, NULL, NULL);
        }
        else {
                /*Do nothing if the word has already been inserted*/
                if (strcasecmp((*root)->str, word) == 0) {
                        return;
                }
				/*Compare the new word with with the leaf an move to the left or
				to the right*/
                else if(strcasecmp((*root)->str, word) > 0) {
                        addleaf(&(*root)->left, word);
                }
                else {
                        addleaf(&(*root)->right, word);
                }

        }
}

net 0

guckt ihr: http://www.ecestudents.ul.ie/Course_Pages/BEng_CE/Modules/CE4703/Sample/binaryTree.c
und:
http://www.fas.harvard.edu/~lib50/Lectures/week8/trees/

baeume gehen nicht ohne dynamischen speicher, torgem.