Posted By

elvis_popovic on 01/19/15

Tagged

array
c++

Versions (?)

Last Edited at 01/19/15 08:50am

Statistics

Viewed 756 times

Favorited by 0 user(s)

Related snippets

ADT Binary tree - array implementation header

/ Published in: C++

An C++ header using templates.
Array implementation of binary tree.

Highlighted TextExpand

#ifndef __POLJE__
#define __POLJE__
#include <iostream>
#define N_ELEMENTS 10000

namespace stablo_polje{

template<typename labeltype>
struct element{
	element(){
		used=false;
	}
	labeltype label;
	bool used;
};

template<typename labeltype>
struct bt {
element <labeltype>elements[N_ELEMENTS];
};

template<typename labeltype>
int ParentB(int n,bt<labeltype>&T)
{
	if(n<2||!T.elements[n].used) return -1;
	if(!T.elements[n/2].used) return -1;
	else return(n/2);
}

template<typename labeltype>
int LeftChildB(int n, bt<labeltype>&T)
{
	if(n<1||n>=N_ELEMENTS/2||(!T.elements[n].used)) return -1;
	if(!T.elements[n*2].used) return -1;
	else return n*2;
}
template<typename labeltype>
int RightChildB(int n, bt<labeltype>&T)
{
	if(n<1||n>=N_ELEMENTS/2||(!T.elements[n].used)) return -1;
	if(!T.elements[n*2+1].used) return -1;
	else return n*2+1;
}
template<typename labeltype>
labeltype LabelB(int n, bt<labeltype>&T)
{
	if(n<1||n>=N_ELEMENTS) return -1;
	if(!T.elements[n].used) return -1;
	else return T.elements[n].label;
}
template<typename labeltype>
void ChangeLabelB(labeltype x, int n, bt<labeltype>&T)
{
	if(n<1||n>=N_ELEMENTS) return;
	if(T.elements[n].used)
		T.elements[n].label=x;
}
template<typename labeltype>
int RootB(bt<labeltype>&T)
{
	if(!T.elements[1].used) return -1;
	else return 1;
}
template<typename labeltype>
bool CreateLeftB(labeltype x, int n, bt<labeltype>&T)
{
	if(n<1||n>=N_ELEMENTS) return false;
	if(T.elements[n*2].used) return false;
	T.elements[n*2].used=true;
	T.elements[n*2].label=x;
	return true;
}
template<typename labeltype>
bool CreateRightB(labeltype x, int n, bt<labeltype>&T)
{
	if(n<1||n>=N_ELEMENTS) return false;
	if(T.elements[n*2+1].used) return false;
	T.elements[n*2+1].used=true;
	T.elements[n*2+1].label=x;
	return true;
}
template<typename labeltype>
void InitB(labeltype x, bt<labeltype>&T)
{
	int i;
	T.elements[1].used=true;
	T.elements[1].label=x;
	for(i=2; i<N_ELEMENTS; i++)
		T.elements[i].used=false;
}
template<typename labeltype>
void DeleteB(int n, bt<labeltype>&T)
{
	if(LeftChildB(n,T)>0) DeleteB(LeftChildB(n,T),T);
	if(RightChildB(n,T)>0) DeleteB(RightChildB(n,T),T);
	T.elements[n].used=false;
}

};
#endif

Report this snippet Tweet

Comments

Subscribe to comments

Comment:

You need to login to post a comment.