Source code
namespace Utils
{
/// <summary>
/// Binary Tree Interface
/// </summary>
public interface IBinaryTree
{
/// <summary>
/// Values used for comparison
/// </summary>
int CompareValue
{
get;
set;
}
}
public class TreeNode<T> where T : IBinaryTree, new()
{
public TreeNode<T> Left
{
get;
set;
}
public TreeNode<T> Right
{
set;
get;
}
public T Data
{
get;
set;
}
public TreeNode(T t)
{
= t;
}
public TreeNode()
: this(default(T))
{
}
}
/// <summary>
/// Two plugs to find the tree
/// </summary>
public class BinaryTree<T> : IDisposable,IEnumerable<T> where T : IBinaryTree, new()
{
public BinaryTree()
{
}
public BinaryTree(T root)
{
if (root == null)
{
throw new NullReferenceException("Parameter is null");
}
Add(root);
}
public BinaryTree(IEnumerable<T> list)
{
if (list == null)
{
throw new NullReferenceException("Parameter is null");
}
foreach (var item in list)
{
Add(item);
}
}
//Root node
private TreeNode<T> root;
//Add node (no check whether the root node is empty, so set to private)
private void Add(T t, TreeNode<T> root)
{
if (t == null)
{
return;
}
if ( < )
{
if ( == null)
{
= new TreeNode<T>(t);
++Count;
}
else
{
Add(t, );
}
}
else if ( > )
{
if ( == null)
{
= new TreeNode<T>(t);
++Count;
}
else
{
Add(t, );
}
}
else
{
= t;
}
}
//Add nodes
public void Add(T t)
{
if (t == null)
{
return;
}
if ( == null)
{
= new TreeNode<T>(t);
++Count;
}
else
{
Add(t, );
}
}
//Find the minimum node under the specified node
public T FindMin(TreeNode<T> node)
{
if (node == null)
{
return default(T);
}
if ( == null)
{
return ;
}
else
{
return FindMin();
}
}
//Find the smallest node
public T FindMin()
{
return FindMin();
}
//Find the largest node
private T FindMax(TreeNode<T> node)
{
if ( == null)
{
return ;
}
else
{
return FindMax();
}
}
//Find the largest node
public T FindMax()
{
return FindMax();
}
//Delete the node under the specified node
public TreeNode<T> Remove(IBinaryTree iBinaryTree, TreeNode<T> node)
{
if (node == null)
{
return null;
}
if (iBinaryTree == null)
{
return node;
}
if ( < )
{
= Remove(iBinaryTree, );
}
else if ( > )
{
= Remove(iBinaryTree, );
}
else
{
if ( != null && != null)
{
T tmpNode = FindMin();//Find the smallest node with a subtree on the current node
= ;//Replace the smallest node of the right subtree instead of the currently deleted node
= Remove(tmpNode, );//This is the highlight, delete the smallest node of the right subtree of the current node
}
else
{
if ( == null)
{
node = ;
}
else if ( == null)
{
node = ;
}
else
{
node = null;
}
if ( == )//handle root node
{
= node;
}
}
--Count;
}
return node;
}
//Delete node
public TreeNode<T> Remove(T t)
{
if ( == null || t==null)
{
return null;
}
return Remove(t, );
}
//Find nodes
public T Find(IBinaryTree iBinaryTree, TreeNode<T> node)
{
if (node == null || iBinaryTree == null)
{
return default(T);
}
if ( < )
{
return Find(iBinaryTree, );
}
else if ( > )
{
return Find(iBinaryTree, );
}
return ;
}
//Find nodes
public T Find(IBinaryTree iBinaryTree)
{
return Find(iBinaryTree, );
}
// Whether to include the specified element
private bool Contains(IBinaryTree iBinaryTree, TreeNode<T> node)
{
if (node == null || iBinaryTree == null)
{
return false; ;
}
if ( < )
{
return Contains(iBinaryTree, );
}
else if ( > )
{
return Contains(iBinaryTree, );
}
return ();
}
// Whether to include the specified element
public bool Contains(T iBinaryTree)
{
return Contains(iBinaryTree, );
}
//Clear all nodes
public void Clear()
{
while ( > 0)
{
Remove();
}
= new TreeNode<T>();
}
//Release resources
public void Dispose()
{
while ( > 0)
{
Remove();
}
= null;
}
//Number of nodes
public int Count
{
private set;
get;
}
//Convert to collection
public IEnumerable<T> ToList()
{
IList<T> list = new List<T>(Count);
LCR(,list);
return list;
}
//The nodes are added to the collection through previous order traversal and implemented in recursive manner. If there are many elements, stack overflow may occur.
private void LCR(TreeNode<T> node, IList<T> list)
{
if (node == null)
{
return;
}
if ( != null)
{
LCR(, list);
}
();//Add elements
if ( != null)
{
LCR(, list);
}
}
//Sorting
public IEnumerable<T> Sort()
{
return ToList();
}
//Returns the enumeration number of a looping collection
public IEnumerator<T> GetEnumerator()
{
return ().GetEnumerator();
}
//Returns the enumeration number of a looping collection
IEnumerator ()
{
return ();
}
public T this[IBinaryTree iBinaryTree]
{
get {
return (iBinaryTree);
}
}
}
public class Node : IBinaryTree
{
/// <summary>
/// Values used for comparison
/// </summary>
public int CompareValue
{
get;
set;
}
public string Name
{
get;
set;
}
public override string ToString()
{
return ("CompareValue:{0},Name:{1}", , );
}
}
}