/ Published in: C++
Expand |
Embed | Plain Text
Copy this code and paste it in your HTML
#include <iostream> using namespace std; typedef int labeltype; struct cvor { labeltype label; bool used; }; struct bt { cvor elementi[10000]; }; typedef bt btree; typedef int node; void InitB(labeltype x, btree *T) { for (int i = 1; i < 10000; i++) { T->elementi[i].used = false; } T->elementi[1].used = true; T->elementi[1].label = x; } labeltype LabelB(node n, btree *T) { return T->elementi[n].label; } void ChangeLabelB(labeltype x, node n, btree *T) { T->elementi[n].label = x; } node RootB(btree *T) { return 1; } node LeftChildB(node n, btree *T) { if (T->elementi[n*2].used == true) return n*2; else return 0; } node RightChildB(node n, btree *T) { if (T->elementi[n*2+1].used == true) return n*2+1; else return 0; } node ParentB(node n, btree *T) { return n/2; } void CreateLeftB(labeltype x, node n, btree *T) { if (T->elementi[n*2].used == true) cout << "Taj cvor vec postoji!" << endl; else { T->elementi[n*2].used = true; T->elementi[n*2].label = x; } } void CreateRightB(labeltype x, node n, btree *T) { if (T->elementi[n*2+1].used == true) cout << "Taj cvor vec postoji!" << endl; else { T->elementi[n*2+1].used = true; T->elementi[n*2+1].label = x; } } void DeleteB(node n, btree *T) { T->elementi[n].used = false; if (T->elementi[n*2].used == true) DeleteB(n*2, T); if (T->elementi[n*2+1].used == true) DeleteB(n*2+1, T); } #include <iostream> #include <deque> using namespace std; typedef int labeltype; struct cvor { labeltype label; cvor *left, *right; // }; typedef cvor *node; typedef cvor btree; void InitB(labeltype x, btree *T) { T->label = x; T->left = T->right = NULL; } labeltype LabelB(node n, btree *T) { return n->label; } void ChangeLabelB(labeltype x, node n, btree *T) { n->label = x; } node RootB(btree *T) { return T; } node LeftChildB(node n, btree *T) { return n->left; } node RightChildB(node n, btree *T) { return n->right; } node ParentB(node n, btree *T) { // ako zelis parent od korijena, odmah gotovo if (n == T) return NULL; // ako ne, idemo traziti deque<node> red; red.push_back(RootB(T)); node temp; // Ovdje njime simuliramo red, dodajemo nepregledane // cvorove na kraj, a s pocetka pregledavamo i vadimo while (red.size()) { temp = red[0]; red.pop_front(); // je li temp roditelj nasemu n? if (temp->left == n || temp->right == n) return temp; // ako nije, gledaj dalje potomstvo... // na kraj reda dodajemo djecu temp-a da se njih pregleda if (temp->left) red.push_back(temp->left); if (temp->right) red.push_back(temp->right); } // ako nije nadjeno (nepostojeci cvor zadan) return NULL; } void CreateLeftB(labeltype x, node n, btree *T) { if (n->left != NULL) { cout << "LeftChild vec postoji" << endl; return; } else { node temp = new cvor; temp->label = x; temp->left = temp->right = NULL; n->left = temp; } } void CreateRightB(labeltype x, node n, btree *T) { if (n->right != NULL) { cout << "RightChild vec postoji" << endl; return; } else { node temp = new cvor; temp->label = x; temp->left = temp->right = NULL; n->right = temp; } } void DeleteB(node n, btree *T) { if (n->left) DeleteB(n->left, T); if (n->right) DeleteB(n->right, T); node r = ParentB(n, T); if (r->right == n) r->right = NULL; else r->left = NULL; delete n; } #include "c.h" //#include "b.h" int main() { cout << endl << "Testiranje b i c zadatka: binarno stablo." << endl; btree bin; cout << "*Inicijalizacija*" << endl; InitB(100, &bin); ChangeLabelB(200, RootB(&bin), &bin); cout << "Treba pisati 200: " << LabelB(RootB(&bin), &bin) << endl; cout << "*Dodavanje djece.*" << endl; CreateRightB(300, RootB(&bin), &bin); CreateLeftB(301, RootB(&bin), &bin); node bin_root_lchild = LeftChildB(RootB(&bin), &bin); node bin_root_rchild = RightChildB(RootB(&bin), &bin); CreateRightB(311, bin_root_lchild, &bin); CreateLeftB(321, bin_root_lchild, &bin); CreateRightB(310, bin_root_rchild, &bin); CreateLeftB(320, bin_root_rchild, &bin); cout << "Treba pisati 300: " << LabelB(bin_root_rchild, &bin) << endl; cout << "Treba pisati 301: " << LabelB(bin_root_lchild, &bin) << endl; cout << "*Brisanje*" << endl; cout << "Adresa lchilda korijena: " << LeftChildB(bin_root_lchild, &bin) << endl; DeleteB(bin_root_lchild, &bin); cout << "Adresa lchilda korijena (nakon brisanja): " << LeftChildB(bin_root_lchild, &bin) << endl; cout << "Ima li root sad lchild: "; if (LeftChildB(RootB(&bin), &bin)) { cout << "ima" << endl; } else { cout << "nema" << endl; } system ("pause"); return 0; }