Other Posts in Data Types

  1. Replacing List
  2. Factory Pattern using Generics in C#
  3. Vector Class and Events in .Net
  4. Binary Trees in C# using Generics
  5. Priority Queue in C#
  6. Cheap Trick for Fluent Interfaces
  7. Building an DI Container

Binary Trees in C# using Generics

9/1/2009

One of the many data types that's missing in .Net is any sort of tree class. I create a lot of searching functions/apps and generally speaking I use binary trees to make these functions faster. I'm not going to go into much depth as to why I chose them because if you've been programming for any length of time, you most likely know my reasons already. But for those of you that don't have much experience with B-trees, just know that it can usually accomplish a search faster than most other structures. Anyway, I was bored this morning and figured I'd create a generic binary tree class:

   1: namespace Utilities.DataTypes
   2: {
   3:     /// <summary>
   4:     /// Binary tree
   5:     /// </summary>
   6:     /// <typeparam name="T">The type held by the nodes</typeparam>
   7:     public class BTree<T> : ICollection<T>,IEnumerable<T> where T : IComparable<T>
   8:     {
   9:         #region Constructor
  10:  
  11:         /// <summary>
  12:         /// Constructor
  13:         /// </summary>
  14:         public BTree()
  15:         {
  16:             NumberOfNodes = 0;
  17:         }
  18:  
  19:         public BTree(BNode<T> Root)
  20:         {
  21:             this.Root = Root;
  22:             NumberOfNodes = 0;
  23:         }
  24:  
  25:         #endregion
  26:  
  27:         #region Properties
  28:         /// <summary>
  29:         /// The root value
  30:         /// </summary>
  31:         public BNode<T> Root { get; set; }
  32:  
  33:         /// <summary>
  34:         /// The number of nodes in the tree
  35:         /// </summary>
  36:         private int NumberOfNodes { get; set; }
  37:  
  38:         /// <summary>
  39:         /// Is the tree empty
  40:         /// </summary>
  41:         public bool IsEmpty { get { return Root == null; } }
  42:  
  43:         /// <summary>
  44:         /// Gets the minimum value of the tree
  45:         /// </summary>
  46:         public T MinValue
  47:         {
  48:             get
  49:             {
  50:                 if (IsEmpty)
  51:                     throw new Exception("The tree is empty");
  52:                 BNode<T> TempNode = Root;
  53:                 while (TempNode.Left != null)
  54:                     TempNode = TempNode.Left;
  55:                 return TempNode.Value;
  56:             }
  57:         }
  58:  
  59:         /// <summary>
  60:         /// Gets the maximum value of the tree
  61:         /// </summary>
  62:         public T MaxValue
  63:         {
  64:             get
  65:             {
  66:                 if (IsEmpty)
  67:                     throw new Exception("The tree is empty");
  68:                 BNode<T> TempNode = Root;
  69:                 while (TempNode.Right != null)
  70:                     TempNode = TempNode.Right;
  71:                 return TempNode.Value;
  72:             }
  73:         }
  74:  
  75:         #endregion
  76:  
  77:         #region IEnumerable<T> Members
  78:  
  79:         public IEnumerator<T> GetEnumerator()
  80:         {
  81:             foreach (BNode<T> TempNode in Traversal(Root)) 
  82:             { 
  83:                 yield return TempNode.Value; 
  84:             }
  85:         }
  86:  
  87:         #endregion
  88:  
  89:         #region IEnumerable Members
  90:  
  91:         System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
  92:         {
  93:             foreach (BNode<T> TempNode in Traversal(Root)) 
  94:             {
  95:                 yield return TempNode.Value; 
  96:             }
  97:         }
  98:  
  99:         #endregion
 100:  
 101:         #region ICollection<T> Members
 102:  
 103:         public void Add(T item)
 104:         {
 105:             if (Root == null)
 106:             {
 107:                 Root = new BNode<T>(item);
 108:                 ++NumberOfNodes;
 109:             }
 110:             else
 111:             {
 112:                 Insert(item);
 113:             }
 114:         }
 115:  
 116:         public void Clear()
 117:         {
 118:             Root = null;
 119:         }
 120:  
 121:         public bool Contains(T item)
 122:         {
 123:             if(IsEmpty)
 124:                 return false;
 125:  
 126:             BNode<T> TempNode=Root;
 127:             while (TempNode != null)
 128:             {
 129:                 int ComparedValue = TempNode.Value.CompareTo(item);
 130:                 if (ComparedValue == 0)
 131:                     return true;
 132:                 else if (ComparedValue < 0)
 133:                     TempNode = TempNode.Left;
 134:                 else
 135:                     TempNode = TempNode.Right;
 136:             }
 137:             return false;
 138:         }
 139:  
 140:         public void CopyTo(T[] array, int arrayIndex)
 141:         {
 142:             T[] TempArray = new T[NumberOfNodes];
 143:             int Counter = 0;
 144:             foreach (T Value in this)
 145:             {
 146:                 TempArray[Counter] = Value;
 147:                 ++Counter;
 148:             }
 149:             Array.Copy(TempArray, 0, array, arrayIndex, this.NumberOfNodes);
 150:         }
 151:  
 152:         public int Count
 153:         {
 154:             get { return NumberOfNodes; }
 155:         }
 156:  
 157:         public bool IsReadOnly
 158:         {
 159:             get { return false; }
 160:         }
 161:  
 162:         public bool Remove(T item)
 163:         {
 164:             BNode<T> Item = Find(item);
 165:             if (Item == null)
 166:                 return false;
 167:             List<T> Values = new List<T>();
 168:             foreach (BNode<T> TempNode in Traversal(Item.Left))
 169:             {
 170:                 Values.Add(TempNode.Value);
 171:             }
 172:             foreach (BNode<T> TempNode in Traversal(Item.Right))
 173:             {
 174:                 Values.Add(TempNode.Value);
 175:             }
 176:             if (Item.Parent.Left == Item)
 177:             {
 178:                 Item.Parent.Left = null;
 179:             }
 180:             else
 181:             {
 182:                 Item.Parent.Right = null;
 183:             }
 184:             Item.Parent = null;
 185:             foreach (T Value in Values)
 186:             {
 187:                 this.Add(Value);
 188:             }
 189:             return true;
 190:         }
 191:  
 192:         #endregion
 193:  
 194:         #region Private Functions
 195:  
 196:         /// <summary>
 197:         /// Finds a specific object
 198:         /// </summary>
 199:         /// <param name="item">The item to find</param>
 200:         /// <returns>The node if it is found</returns>
 201:         private BNode<T> Find(T item)
 202:         {
 203:             foreach (BNode<T> Item in Traversal(Root))
 204:                 if (Item.Value.Equals(item))
 205:                     return Item;
 206:             return null;
 207:         }
 208:         
 209:         /// <summary>
 210:         /// Traverses the list
 211:         /// </summary>
 212:         /// <param name="Node">The node to start the search from</param>
 213:         /// <returns>The individual items from the tree</returns>
 214:         private IEnumerable<BNode<T>> Traversal(BNode<T> Node)
 215:         {
 216:             if (Node.Left != null)
 217:             {
 218:                 foreach (BNode<T> LeftNode in Traversal(Node.Left))
 219:                     yield return LeftNode;
 220:             }
 221:             yield return Node;
 222:             if (Node.Right != null)
 223:             {
 224:                 foreach (BNode<T> RightNode in Traversal(Node.Right))
 225:                     yield return RightNode;
 226:             }
 227:         }
 228:  
 229:         /// <summary>
 230:         /// Inserts a value
 231:         /// </summary>
 232:         /// <param name="item">item to insert</param>
 233:         private void Insert(T item)
 234:         {
 235:             BNode<T> TempNode = Root;
 236:             bool Found=false;
 237:             while (!Found)
 238:             {
 239:                 int ComparedValue = TempNode.Value.CompareTo(item);
 240:                 if(ComparedValue<0)
 241:                 {
 242:                     if(TempNode.Left==null)
 243:                     {
 244:                         TempNode.Left=new BNode<T>(item,TempNode);
 245:                         ++NumberOfNodes;
 246:                         return;
 247:                     }
 248:                     else
 249:                     {
 250:                         TempNode=TempNode.Left;
 251:                     }
 252:                 }
 253:                 else if(ComparedValue>0)
 254:                 {
 255:                     if(TempNode.Right==null)
 256:                     {
 257:                         TempNode.Right=new BNode<T>(item,TempNode);
 258:                         ++NumberOfNodes;
 259:                         return;
 260:                     }
 261:                     else
 262:                     {
 263:                         TempNode=TempNode.Right;
 264:                     }
 265:                 }
 266:                 else
 267:                 {
 268:                     TempNode=TempNode.Right;
 269:                 }
 270:             }
 271:         }
 272:  
 273:         #endregion
 274:     }
 275:  
 276:     /// <summary>
 277:     /// Node class for the Binary tree
 278:     /// </summary>
 279:     /// <typeparam name="T">The value type</typeparam>
 280:     public class BNode<T>
 281:     {
 282:         #region Constructors
 283:  
 284:         /// <summary>
 285:         /// Constructor
 286:         /// </summary>
 287:         public BNode()
 288:         {
 289:         }
 290:  
 291:         /// <summary>
 292:         /// Constructor
 293:         /// </summary>
 294:         /// <param name="Value">Value of the node</param>
 295:         public BNode(T Value)
 296:         {
 297:             this.Value = Value;
 298:         }
 299:  
 300:         /// <summary>
 301:         /// Constructor
 302:         /// </summary>
 303:         /// <param name="Value">Value of the node</param>
 304:         /// <param name="Parent">Parent node</param>
 305:         public BNode(T Value, BNode<T> Parent)
 306:         {
 307:             this.Value = Value;
 308:             this.Parent = Parent;
 309:         }
 310:  
 311:         /// <summary>
 312:         /// Constructor
 313:         /// </summary>
 314:         /// <param name="Value">Value of the node</param>
 315:         /// <param name="Parent">Parent node</param>
 316:         /// <param name="Left">Left node</param>
 317:         /// <param name="Right">Right node</param>
 318:         public BNode(T Value, BNode<T> Parent, BNode<T> Left, BNode<T> Right)
 319:         {
 320:             this.Value = Value;
 321:             this.Right = Right;
 322:             this.Left = Left;
 323:             this.Parent = Parent;
 324:         }
 325:  
 326:         #endregion
 327:  
 328:         #region Properties
 329:         
 330:         /// <summary>
 331:         /// Value of the node
 332:         /// </summary>
 333:         public T Value { get; set; }
 334:  
 335:         /// <summary>
 336:         /// Parent node
 337:         /// </summary>
 338:         public BNode<T> Parent { get; set; }
 339:  
 340:         /// <summary>
 341:         /// Left node
 342:         /// </summary>
 343:         public BNode<T> Left { get; set; }
 344:  
 345:         /// <summary>
 346:         /// Right node
 347:         /// </summary>
 348:         public BNode<T> Right { get; set; }
 349:  
 350:         /// <summary>
 351:         /// Is this the root
 352:         /// </summary>
 353:         public bool IsRoot { get { return Parent == null; } }
 354:  
 355:         /// <summary>
 356:         /// Is this a leaf
 357:         /// </summary>
 358:         public bool IsLeaf { get { return Left == null && Right == null; } }
 359:  
 360:         internal bool Visited { get; set; }
 361:  
 362:         #endregion
 363:  
 364:         #region Public Overridden Functions
 365:  
 366:         public override string ToString()
 367:         {
 368:             return Value.ToString();
 369:         }
 370:  
 371:         #endregion
 372:     }
 373: }

The code above has two classes, the first being the actual BTree class and the second being a BNode class (Node for the BTree). This implementation is dumb and doesn't rebalance itself as needed. Instead it just inserts/deletes in a pretty dumb fashion... But hey, it's more here to give someone out there the basics, from which they could create a red black tree or something else that's a bit more interesting. Anyway, I hope this helps you out. Give it a try, leave feedback, and happy coding.



Comments