Return to Snippet

Revision: 38682
at January 6, 2011 06:04 by tomislav_matic


Initial Code
#include "c_zadatak.h"
//#include "b_zadatak.h"
#include <iostream>

using namespace std;


int main(void) {
    btree T;
    cout << "Test 1, init" << endl;
    InitB(1, &T);
    cout << "Test gotov " << endl;

    cout << "Test 2, init, label, root (ispis: 1)" << endl;
    cout << LabelB(RootB(&T), &T) << endl;
    
    cout << "Test gotov " << endl;  
  
    cout << "Test 3, create left, create right (ispis: 1, 1, 0)" << endl;
    cout << CreateLeftB(42, RootB(&T), &T) << endl;
    cout << CreateRightB(43, RootB(&T), &T) << endl;

    
    cout << CreateLeftB(42, RootB(&T), &T) << endl;
    cout << "Test gotov " << endl;
    cout << "Test 4, delete" << endl;
    DeleteB(LeftChildB(RootB(&T), &T), &T);
    cout << "Test gotov " << endl;

    cout << "Test 5, delete (ispisuje 1)" << endl;
    cout << CreateLeftB(7, RootB(&T), &T) << endl;
    cout << "Test gotov " << endl;

    cout << "Test 6, parent (ispisuje 1)" << endl;
    cout << LabelB(ParentB(RightChildB(RootB(&T), &T), &T), &T) << endl;
    cout << "Test gotov " << endl;

    cout << "Test 7, change label (ispisuje 666)" << endl;
    ChangeLabelB(666, RootB(&T), &T);
    cout << LabelB(RootB(&T), &T) << endl;
    cout << "Test gotov " << endl;
    return 0;
}


//Biblioteka  B.polja ///

struct element {
    int label;
    int used;
};

struct bt {
    element elements[10000];
};

typedef bt btree;
typedef int node;



node ParentB(node n, btree *T) {
    return n/2;
}

node RootB(btree *T) {
    return 1;
}

void InitB(int x, btree *T) {
    T->elements[1].used = 1;
    T->elements[1].label = x;
    for (int i = 2; i < 10000; i++) {
        T->elements[i].used = 0;
    }
}

node LeftChildB(node n, btree *T) {
    if (T->elements[n*2].used == 1) 
        return n*2;
    else 
        return 0;
}

node RightChildB(node n, btree *T) {
    if (T->elements[n*2 +1].used == 1) 
        return n*2 +1;
    else 
        return 0;
}

int LabelB(node n, btree *T) {
    return T->elements[n].label; 
}

void ChangeLabelB(int x, node n, btree *T) {
    T->elements[n].label = x;
}

void DeleteB(node n, btree *T) {
    if (LeftChildB(n, T)) {
        DeleteB(LeftChildB(n, T), T);
    }
    if (RightChildB(n, T)) {
        DeleteB(RightChildB(n, T), T);
    }
    T->elements[n].used = 0;
}

bool CreateLeftB(int x, node n, btree *T) {
    if (LeftChildB(n, T) != 0) {
        return false; 
    }
    else {
        T->elements[n*2].used = 1;
        T->elements[2*n].label = x;
        return true;
    }
}

bool CreateRightB(int x, node n, btree *T) {
    if (RightChildB(n, T) != 0) {
        return false; 
    }
    else {
        T->elements[n*2 +1].used = 1;
        T->elements[2*n +1].label = x;
        return true;
    }
}



Biblioteka C.pokazivaca


#include <cstdlib>

struct element {
    int label;
    element *left,*right;
};

typedef element *node;
typedef element btree;




node RootB(btree *T) {
    return T;
}

void InitB(int x, btree *T) {
    T->label = x;
    T->left = NULL;
    T->right = NULL;
}

node LeftChildB(node n, btree *T) {
    return (n->left);
}

node RightChildB(node n, btree *T) {
    return (n->right);
}

node rekurzivna(node cvor, node trazeni, btree *T) {
    if (cvor->left == trazeni || cvor->right == trazeni) {
        return cvor;
    }
    node tmp;
    tmp = rekurzivna(cvor->left, trazeni, T);
    if (tmp != NULL) return tmp;
    tmp = rekurzivna(cvor->right, trazeni, T);
    if (tmp != NULL) return tmp;
    
    return NULL;
}

node ParentB(node n, btree *T) {
    return rekurzivna(RootB(T), n, T);
}

int LabelB(node n, btree *T) {
    return (n->label);
}

void ChangeLabelB(int x, node n, btree *T) {
    n->label = x;
}

void DeleteB(node n, btree *T) {
    if (n->left != NULL) {
        DeleteB(n->left, T);
    }
    if (n->right != NULL) {
        DeleteB(n->right, T);
    }

    node Parent = ParentB(n, T);
    if (Parent->left == n) {
        Parent->left = NULL;
    }
    else {
        Parent->right = NULL;
    }   

    delete n;
}

bool CreateLeftB(int x, node n, btree *T) {
    if (n->left == NULL) {
        n->left = new element;
        n->left->left = NULL;
        n->left->right = NULL;
        n->left->label = x;
        return 1;
    }
    return 0;
}

bool CreateRightB(int x, node n, btree *T) {
    if (n->right == NULL) {
        n->right = new element;
        n->right->left = NULL;
        n->right->right = NULL;
        n->right->label = x;
        return 1;
    }
    return 0;
}

Initial URL

                                

Initial Description

                                

Initial Title
implementacija binarnog stabla pomocu  B.polja i C.pokazivaca

Initial Tags

                                

Initial Language
C++