crossbow25 0 Newbie Poster
#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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.