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: }
RSS Feed
Twitter Feed