Vissza

Labor 8

Bináris fák

Adott az alábbi 3 forrásállományból ( btree.h, btree.c, tesztbtree.c ) álló bináris fa programmodul. Teszteljük a programmodult legalább 3 típusra, majd bővítsük ki a következő függvényekkel, adott esetben alkalmazva a megadott  függvény  deklarációkat:

  • Állományban levő értékekkel töltsünk fel egy bináris fát, ahol az állományba preorder sorrendbe adjuk meg az értékeket.
  • Implementáljuk az inorder, postorder algoritmusokat.
  • Határozzuk meg a bináris fa magasságát.
  • Határozzuk meg a levélcsúcsok számát.
  • Vizsgáljuk meg hogy két bináris fa egyenlő-e?
  • Cseréljük fel a bal és jobb részfákat.
  • Készítsünk másolatot a bináris fáról.

btree.h

#ifndef _BTREE_H
#define _BTREE_H

#include <stdio.h>
#include <stdlib.h>
#define ENDOFREAD -1

enum TRAV { PREORDER, INORDER, POSTORDER };
struct Bnode{
    void * inf;
    struct Bnode * llink;
    struct Bnode * rlink;
};
typedef struct Bnode * BNODEPTR;

struct Btree{
    BNODEPTR root;
};
typedef struct Btree * BTREEPTR;

BTREEPTR createtree(); //a binaris fa letrehozasa
BNODEPTR readtree(); //a binaris fa leolvasasa
void destroy( BTREEPTR ); //memoria felszabaditas
void printtree( BTREEPTR t, enum TRAV mode ); // a binaris fa informacioinak a kiiratasa
void preorder( BNODEPTR );
void inorder ( BNODEPTR );
void postorder( BNODEPTR );
#endif

btree.c

#include "btree.h"

BTREEPTR createtree(){
    BTREEPTR t = ( BTREEPTR ) malloc( sizeof(struct Btree) );
    t->root = readtree();
    return t;
}

void destroy( BTREEPTR t){
    //...
}

BNODEPTR readtree(){
    BNODEPTR n = createnode();
    if( n == NULL )
        return NULL;
    else{
        n->llink = readtree();
        n->rlink = readtree();
        return n;
    }
}

void printtree( BTREEPTR t, enum TRAV mode ){
    switch( mode ){
        case PREORDER : preorder ( t->root ); break;
        //case INORDER : inorder ( t->root ); break;
        //case POSTORDER: postorder( t->root ); break;
    }
}

void preorder( BNODEPTR r ){
    if( r != NULL ){
        printnode( r );
        preorder( r->llink);
        preorder( r->rlink);
    }
}

tesztbtree.c

#include "btree.h"

/* egy egész típusú csúcspont létrehozása */
BNODEPTR createnode(){
    int * inf = ( int * ) malloc( sizeof( int ));
    printf("\nINF: ");
    scanf("%d",inf);
    if( *inf == ENDOFREAD ){
        free( inf );
        return NULL;
    }
    else{
        BNODEPTR p = (BNODEPTR) malloc( sizeof(struct Bnode) );
        p->inf = inf;
        return p;
    }
}

void printnode( BNODEPTR p ){
    printf("%6d\t",*(int * )(p->inf));
}

int main(){
    BTREEPTR f = createtree();
    printf("\nPREORDER: ");
    printtree( f, PREORDER );
}