Problem
I’ve written a binary-tree using .NET Core 3.0. What can I do to improve my coding style?
using System;
using System.IO;
using System.Runtime.Serialization;
using System.Runtime.Serialization.Formatters.Binary;
namespace BinaryTree
{
/// <summary>
/// Represents a binary tree <seealso href="https://en.wikipedia.org/wiki/Binary_tree"/>.
/// </summary>
/// <typeparam name="T">The type which this tree should contain.</typeparam>
[Serializable]
[DataContract]
public class BinaryTree<T> where T : IComparable, new()
{
#if DEBUG
/// <summary>
/// Determines whether or not to log actions in the console.
/// </summary>
public static bool Log = true;
#endif
[DataMember]
private Node<T> _parentNode;
public BinaryTree()
{
#if DEBUG
if (Log)
Console.WriteLine("Initializing binary-tree..");
#endif
_parentNode = new Node<T>();
}
/// <summary>
/// Adds the specific item inside the binary-tree using binary-tree logic.
/// </summary>
/// <param name="item">The item that will be added.</param>
public void Add(T item)
{
#if DEBUG
if (Log)
Console.WriteLine("Initializing binary-tree..");
#endif
_parentNode.Add(item);
}
/// <summary>
/// Removes the specific item inside the binary-tree using binary-tree logic. The root node cannot be removed.
/// </summary>
/// <param name="item">The item that will be removed.</param>
public void Remove(T item)
{
_parentNode.Remove(item);
}
/// <summary>
/// Searches for a specific item inside this binary-tree using binary-tree logic.
/// </summary>
/// <param name="item"></param>
/// <returns>Returns the count of said item if existing - 0 if otherwise.</returns>
public int Contains(T item)
{
return _parentNode.Contains(item);
}
/// <summary>
/// Clears everything out of this binary-tree.
/// </summary>
public void Clear()
{
_parentNode = new Node<T>();
}
public override bool Equals(object obj)
{
return obj is BinaryTree<T> tree && tree._parentNode.Equals(_parentNode);
}
public void Serialize(string file)
{
using (var writer = new StreamWriter(file))
{
var bf = new BinaryFormatter();
bf.Serialize(writer.BaseStream, this);
}
}
public static BinaryTree<T> Deserialize(string file)
{
using (var reader = new StreamReader(file))
{
var bf = new BinaryFormatter();
return (BinaryTree<T>)bf.Deserialize(reader.BaseStream);
}
}
/// <summary>
/// Represents a node of a binary-tree. This may be either a simple node, a parent, or a leaf.
/// </summary>
/// <typeparam name="T">The type which this node should contain.</typeparam>
[Serializable]
[DataContract]
private class Node<T> where T : IComparable, new()
{
/// <summary>
/// Right "lower" arm of current node - this is where everything bigger than this node is getting redirect towards.
/// </summary>
[DataMember]
private Node<T> _bigger;
/// <summary>
/// Saved data and count of data - inside this specific node.
/// </summary>
[DataMember]
private (T data, int count) _item;
/// <summary>
/// Root node, if existing.
/// </summary>
[DataMember]
private Node<T> _parent;
/// <summary>
/// Left "lower" arm of current node - this is where everything smaller than this node is getting redirect towards.
/// </summary>
[DataMember]
private Node<T> _smaller;
private Node(T item)
{
_item = (item, 1);
}
public Node()
{
}
public override bool Equals(object obj)
{
return obj is Node<T> node &&
(node._bigger?.Equals(_bigger) ?? _bigger == null) &&
(node._item.data?.Equals(_item.data) ?? _item.data == null) &&
(node._item.count.Equals(_item.count)) &&
(node._parent?.Equals(_parent) ?? _parent==null) &&
(node._smaller?.Equals(_smaller) ?? _smaller == null);
}
private void Set(T data)
{
if (_item.data.Equals(default(T)))
{
_item = (data, 1);
return;
}
if (data.Equals(_item.data))
_item.count++;
else
Add(data);
}
public void Remove(T data)
{
if (data.Equals(_item.data))
{
if (_item.count > 1)
{
_item.count--;
}
else
{
if (_parent == null) return;
var replacement = new Node<T>(data)
{
_smaller = _smaller,
_bigger = _bigger,
_parent = _parent
};
if (_parent._item.data.CompareTo(_item.data) == 1)
_parent._smaller = replacement;
else
_parent._bigger = replacement;
}
}
else
{
if (data.CompareTo(_item.data) == 1)
{
_bigger?.Remove(data);
if (_bigger != null) _bigger._parent = this;
}
else
{
_smaller?.Remove(data);
if (_smaller != null) _smaller._parent = this;
}
}
}
public void Add(T item)
{
if (_item.data.Equals(default(T)))
{
Set(item);
return;
}
if (item.CompareTo(_item.data) == 1)
{
#if DEBUG
if (Log)
Console.WriteLine($"{item} > {_item.data} → move to right lower node..");
#endif
(_bigger = CreateOrReturnNode(_bigger)).Set(item);
}
else
{
#if DEBUG
if (Log)
Console.WriteLine($"{item} < {_item.data} → move to left lower node..");
#endif
(_smaller = CreateOrReturnNode(_smaller)).Set(item);
}
}
public int Contains(T value)
{
if (_item.data.Equals(value))
{
#if DEBUG
if (Log)
Console.WriteLine("Item was found!");
#endif
return _item.count;
}
if (value.CompareTo(_item.data).Equals(1))
{
#if DEBUG
if (Log)
Console.WriteLine($"{value} > {_item.data} → search in right lower node..");
#endif
return _bigger?.Contains(value) ?? 0;
}
#if DEBUG
if (Log)
Console.WriteLine($"{value} < {_item.data} → search in left lower node..");
#endif
return _smaller?.Contains(value) ?? 0;
}
/// <summary>
/// Either creates a new node, or returns the existing one.
/// </summary>
/// <param name="node">The node which is getting checked whether it is set or not.</param>
/// <returns>Either a new node, or the already existing one.</returns>
private static Node<T> CreateOrReturnNode(Node<T> node = null)
{
return node ?? new Node<T>();
}
}
}
}
Updated Version: https://github.com/TheRealVira/binary-tree/blob/master/BinaryTree/BinaryTree.cs
Solution
public class BinaryTree<T> where T : IComparable, new()
I suspect that you are unaware of the possibility of writing
public class BinaryTree<T> where T : IComparable<T>, new()
If you did deliberately choose IComparable over IComparable<T>, it would be helpful to add a comment explaining why.
Why where T : new()? The code doesn’t call new T() anywhere.
The class would be a lot more powerful if you also implemented IEnumerable<T>, and ideally you would implement ICollection<T>.
private Node<T> _parentNode;
Node is an inner class, so it doesn’t need the type parameter. You can remove it, and T from the outer class will be in scope. If you’ve come to C# from Java then note that this is one of the bigger differences in their type systems.
#if DEBUG
if (Log)
Console.WriteLine("Initializing binary-tree..");
#endif
If you use System.Diagnostics.Debug.WriteLine then (a) you can skip all the #if DEBUG; (b) when running in Visual Studio the log will be available in the Output pane even after the process has finished.
Alternatively you could take it up a level and use a proper runtime-configurable logging library like Serilog, log4net, …
public void Add(T item)
{
#if DEBUG
if (Log)
Console.WriteLine("Initializing binary-tree..");
#endif
_parentNode.Add(item);
}
That log message looks suspicious…
Also, I see you’ve made a design decision to push the majority of the logic into the nodes. Since you appear to be doing this as a learning exercise, I suggest that for comparison you separately implement a version which leaves the nodes as pure data objects and puts all the logic in the methods of BinaryTree. That lets you use tail optimisation (turn recursion into a while loop).
public override bool Equals(object obj)
{
return obj is BinaryTree<T> tree && tree._parentNode.Equals(_parentNode);
}
Visual Studio gives me a warning about this: when you override Equals you should override GetHashcode because otherwise you will spend ages debugging if you ever put an instance of this class in a HashSet<> or as the key in a Dictionary.
The same applies to Node.
/// <summary>
/// Right "lower" arm of current node - this is where everything bigger than this node is getting redirect towards.
/// </summary>
[DataMember]
private Node<T> _bigger;
I managed to understand the code ok, but it would be more conventional to call this _right. (Or maybe right, but I don’t want to be pedantic about that kind of naming convention).
private (T data, int count) _item;
That count is unusual. In effect you’re implementing an IDictionary<T, int>: perhaps it would make sense to generalise to IDictionary<TKey, TValue> and have a separate wrapper class which turns any IDictionary<TKey, TValue> into a counter.
public override bool Equals(object obj)
{
return obj is Node<T> node &&
(node._bigger?.Equals(_bigger) ?? _bigger == null) &&
(node._item.data?.Equals(_item.data) ?? _item.data == null) &&
(node._item.count.Equals(_item.count)) &&
(node._parent?.Equals(_parent) ?? _parent==null) &&
(node._smaller?.Equals(_smaller) ?? _smaller == null);
}
ValueStruct overrides ==, so you could simplify this a bit. Unless you want to be paranoid and assume that T might not have Equals consistent with CompareTo, in which case you should use CompareTo here to compare _item.data.
public void Remove(T data)
{
if (data.Equals(_item.data))
{
if (_item.count > 1)
{
_item.count--;
}
else
{
if (_parent == null) return;
The only place that _parent is touched is in Remove, so if I add one item to the tree and then call Remove with that same item, it won’t be removed.
public int Contains(T value)
{
if (_item.data.Equals(value))
I got a NullReferenceException here when I called Contains on an empty tree.
public void Add(T item)
{
if (_item.data.Equals(default(T)))
I got a NullReferenceException here when the tree was empty: did you test this code at all?
if (_parent._item.data.CompareTo(_item.data) == 1)
if (data.CompareTo(_item.data) == 1)
if (item.CompareTo(_item.data) == 1)
if (value.CompareTo(_item.data).Equals(1))
The contract of IComparable does not say that the value returned will always be -1, 0, or 1. I’m not sure why lots of people seem to think that it does. You should always compare the return value against 0.
Well, I would prefer not to have a private Node class inside the BinaryTree class.
I think that the logic for adding/removing nodes in the tree should be done at the Tree class and not at the Node class level.
Maybe move the Node class into its own file, rename it to BinaryNodeTree and move the add/remove logic to the tree itself, which can use a utility class for searching the node to add the value too.