#ifndef VECTORBINARYTREE_H
#define VECTORBINARYTREE_H
template<typename Object>
class ArrayVector{
private:
int capacity;
int sz;
Object* a;
protected:
void overflow()
{
capacity*=2;
Object* b=new Object[capacity];
for(int i=0;i<sz;i++) b[i]=a[i];
delete []a;
a=b;
}
public:
ArrayVector(int initCap=16){
capacity = initCap; sz=0;
a = new Object[capacity];
}
int size() const {return sz;}
bool isEmpty() const {return size()==0;}
Object elemAtRank(int r) {return a[r];}
void replaceAtRank(int r, const Object& e) {a[r]=e;}
void removeAtRank(int r)
{
for(int i=r;i<sz-1;i++) a[i]=a[i+1];
sz--;
}
void insertAtRank(int r, const Object &e)
{
if(sz==capacity) overflow();
for(int i=sz-1;i>=r;i--) a[i+1]=a[i];
a[r]=e;
sz++;
}
};
template <typename Object>
class VectorBinaryTree{
protected:
struct Node{
Object element;
int rank;
Node() : element(Object())
{rank = 0;}
Node *sibling() const
{
if(rank%2==0) return av.elemAtRank(rank+1);
else return av.elemAtRank(rank-1);
}
};
typedef Node *NodePtr;
public:
class Position{
private:
int rank;
public:
Position(NodePtr n=NULL){ av.replaceAtRank(rank,n); }
Object & element() const{ return (av.elemAtRank(rank)).element; }
bool isNull() const { return (av.elemAtRank(rank))==NULL; }
friend VectorBinaryTree;
};
private:
ArrayVector <NodePtr> av;
int sz;
public:
VectorBinaryTree() { av.replaceAtRank(1,new Node); sz=1; }
Position root() { return Position(av.elemAtRank(1)); }
Position leftChild(const Position &v) { return Position(av.elemAtRank((v.rank)*2));}
Position rightChild(const Position &v) { return Position(av.elemAtRank((v.rank)*2+1));}
Position parent(const Position &v) { return Position(av.elemAtRank((v.rank)/2)); }
Position sibling(const Position &v)
{
if((v.rank)%2==0) return Position(av.elemAtRank((v.rank)+1));
else return Position(av.elemAtRank((v.rank)-1));
}
bool isRoot(const Position &v) const { return (v.rank)==1; }
bool isInternal(const Position &v) const { return (leftChild(v)!=NULL || rightChild(v)!=NULL);}
bool isExternal(const Position &v) const { return !(isInternal(v));}
void replaceElement(const Position &v, const Object &o) { v.element() = o; }
void swapElement(const Position &v, const Position &w)
{
Object temp = w.element();
w.element() = v.element();
v.element() = temp;
}
void expandExternal(const Position &v)
{
leftChild(v) = new Node;
rightChild(v) = new Node;
sz += 2;
}
Position removeAboveExternal(const Position &v)
{
NodePtr p = parent(v);
NodePtr s = sibling(v);
NodePtr g = parent(p);
if(isRoot(p))
{ av.elemAtRank(1) = s; }
else
{
if(p==leftChild(g)) leftChild(g)=s;
else rightChild(g)=s;
parent(s) =g;
}
delete v;
delete p;
sz-=2;
return Position(s);
}
};
#endif
VectorBinaryTree.h
#include <iostream>
using namespace std;
#include "VectorBinaryTree.h"
int main(void)
{
typedef VectorBinaryTree<char> charBT;
typedef charBT::Position charPosition;
charBT A;
charPosition lPosition, rPosition;
A.replaceElement(A.root(), '+');
A.expandExternal(A.root());
lPosition = A.leftChild(A.root());
A.replaceElement(A.root(), '*');
A.expandExternal(A.root());
rPosition = A.rightChild(A.root());
A.replaceElement(rPosition, '/');
A.expandExternal(lPosition);
A.replaceElement(A.leftChild(lPosition), '1');
A.expandExternal(lPosition);
A.replaceElement(A.rightChild(lPosition), '2');
A.expandExternal(rPosition);
A.replaceElement(A.leftChild(rPosition), '3');
A.expandExternal(rPosition);
A.replaceElement(A.rightChild(rPosition), '4');
return 0;
}
main.cpp
This program is binaryTree using Vector class.
main.cpp is right. i have to make VectorBinaryTree.h
i try to fill out these blank in header file.
but this program doesn't working. it's so difficult.
i don't know how i access this problem.
please tell me what you know about this.
i'm korean. so i don't know english very well.
i hope you understand language problem.
thanks.