slacky.eu

Codice: Seleziona tutto

template <class T>
class Tree
{
 protected:
  typedef struct node
  {
    T item;
    long key;
    node* left;
    node* right;
    node* daddy;
  
    node()
    {
      key = 0;
      left = right = daddy = &NIL;
    }

    node(T i, long k)
    {
      key = k;
      item = i;
      left = right = daddy = &NIL;
    }
};

 private:
  node* root;
  static node NIL;

... ecc ...

};
template <class T>
Tree<T>::node Tree<T>::NIL; 

Codice: Seleziona tutto

nico@nicoLaptop:~$ make ./Documents/C++/Tree/main
g++     Documents/C++/Tree/main.cpp   -o Documents/C++/Tree/main
In file included from Documents/C++/Tree/main.cpp:1:
Documents/C++/Tree/BinaryTree.h:240: error: expected constructor, destructor, or type conversion before 'Tree'
make: *** [Documents/C++/Tree/main] Error 1

Codice: Seleziona tutto

#ifndef _BinaryTree_h
#define _BinaryTree_h 1

#include <iostream>

template <class T>
class Tree
{
 protected:
  typedef struct node
  {
    T item;
    long key;
    node* left;
    node* right;
    node* daddy;
  
    node()
    {
      key = 0;
      left = right = daddy = &NIL;
    }

    node(T i, long k)
    {
      key = k;
      item = i;
      left = right = daddy = &NIL;
    }

    node(const node& rhs)
    {
      key = 0;
      left = right = daddy = &NIL;

      key = rhs.key;
      left = rhs.left;
      right = rhs.right;
      daddy = rhs.daddy;
    }

    node& operator=(const node& n)
    {
      if (this == &n)
	return *this;
      
      key = n.key;
      left = n.left;
      right = n.right;
      daddy = n.daddy;

      return *this;
    }

      T& Get_key() 
    {
      return key;
    }
  };

 private:
  node* root;
  static node NIL;

 void Clean(node* r)
  {
    if(r != &NIL);
      {
	Clean(r->left);
	Clean(r->right);
	delete r;
      }
  }

 public:
 Tree()
    {
      root = new node;
      NIL.daddy = root;
      root = &NIL;
    }

   ~Tree()
   {
     Clean(root);
   }

   void insert(T obj, long k)
  {
    node* x = root;
    node* y = &NIL;
    node* z = new node(obj, k);
    //z->daddy = z->left = z->right = NIL;

    while(x != &NIL)
      {
	y = x;
	if(z->key <= x->key)
	  x = x->left;
	else
	  x = x->right;
      }

    z->daddy = y;
    if(y == &NIL)
      root = z; 
    else 
      if(z->key <= y->key)
	y->left = z;
      else
	y->right = z;
  }

  node* minimum(node* x)
    {
      while(x->left != &NIL)
	x = x->left;

      return x;
    }

  node* maximum(node* x)
    {
      while(x->right != &NIL)
	x = x->right;

      return x;
    }

  node* search(T k)
    {
      node* tmp = new node;
      tmp =  root;      

      while(tmp != &NIL && k != tmp->key)
	{
	  if(tmp->key > k)
	    tmp = tmp->left;
	  else
	    tmp = tmp->right;
	}
      
      return tmp;
    }


  node* successor(node* x)
    {
      if(x->right != &NIL)
	return minimum(x->right);

      node* y = x->daddy;

      while(y != &NIL && x == y->right)
	{
	  x = y;
	  y = y->daddy;
	}

      return y;
    }

  node* predecessor(node* x)
    {
      if(x->left != &NIL)
	return maximum(x->left);
     
      node* y = x->daddy;

      while(y != &NIL && x == y->left)
	{
	  x = y;
	  y = y->daddy;
	}

      return y;
    }
     
  node* remove(const T& k)
    {
      node* z = search(k);

      node* x = new node;
      node* y = new node;

      if(z->left == &NIL || z->right == &NIL)
	y = z;

      else
	y = successor(z);
	 
      if(y->left != &NIL) 
	x = y->left;

      else 
	x = y->right;
	
      x->daddy = y->daddy;

      if(y->daddy == &NIL)
	root = x;

      else
	{
	  if(y == y->daddy->left)
	    y->daddy->left = x;

	  else
	    y->daddy->right = x;
	}

      if(y != z)
	z->key = y->key;

      return y;
    }

  node* Get_pappy(const node& s)
    {
	return s.daddy;
    }

  node* Get_root() const
    {
      return root;
    }

  void print(const node* r)
  {
    if(r != &NIL)
      {
	print(r->left);
	std::cout << r->key << " ";
	print(r->right);
      }
  }
};

template <class T>
Tree<T>::node Tree<T>::NIL;

#endif