1  /********************************************************************** <BR>


2  This file is part of Crack dot Com's free source code release of


3  Golgotha. <a href="http://www.crack.com/golgotha_release"> <BR> for


4  information about compiling & licensing issues visit this URL</a>


5  <PRE> If that doesn't help, contact Jonathan Clark at


6  golgotha_source@usa.net (Subject should have "GOLG" in it)


7  ***********************************************************************/


8 


9  #ifndef I4_BINARY_TREE_HH


10  #define I4_BINARY_TREE_HH


11 


12  /*


13  pretty simple, uses linear_allocator for quick allocation


14  two methods, ::insert & ::find so far, you need to define the > & <


15  operators for the type if they don't exsist.


16 


17  example ussage:


18  


19 


20  i4_binary_tree<int> tree;


21  tree.insert(6);


22  tree.insert(10);


23  if (tree.find(12)) x=5;


24 


25  or for user defined structs :


26 


27  struct complex


28  {


29  float a;


30  float b;


31 


32  i4_bool operator>(const command_matchup c) const { return (i4_bool)(a>c.b); }


33  i4_bool operator<(const command_matchup b) const { return (i4_bool)(a<c.b); }


34  };


35 


36  i4_binary_tree<complex> tree2;


37  tree2.insert(complex(3.1, 4.5));


38  tree2.find(complex(3.1,0));


39  */


40 


41  #include "memory/lalloc.hh"


42 


43  template <class T>


44  class i4_binary_tree


45  {


46  void recursive_delete(T * node)


47  {


48  if (node>right)


49  recursive_delete(node>right);


50  if (node>left)


51  recursive_delete(node>left);


52  delete node;


53  }


54 


55  public:


56  T *root;


57 


58  i4_binary_tree() { root=0; }


59 


60 


61  // insert return a previous instance if already in tree


62  T *insert(T *x)


63  {


64  x>left=x>right=0;


65 


66  if (!root)


67  root=x;


68  else


69  {


70  T *p=root;


71 


72  while (1)


73  {


74  int cmp=x>compare(p);


75  if (cmp<0)


76  {


77  if (!p>left)


78  {


79  p>left=x;


80  return x;


81  }


82  else p=p>left;


83  }


84  else if (cmp>0)


85  {


86  if (!p>right)


87  {


88  p>right=x;


89  return x;


90  }


91  else p=p>right;


92  }


93  else return p;


94  }


95  }


96 


97  return x;


98  }


99 


100  T *find(const T *x)


101  {


102  T *p=root;


103  while (1)


104  {


105  if (!p) return 0;


106 


107  int cmp=x>compare(p);


108  if (cmp<0)


109  p=p>left;


110  else if (cmp>0)


111  p=p>right;


112  else return p;


113  }


114  }


115 


116  void delete_tree()


117  {


118  if (root)


119  recursive_delete(root);


120  }


121 


122  };


123 


124  #endif

