[80]  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

