ツリーベースのコレクション
13824 ワード
Dictionary
public class BinaryTree<T> : IDisposable, IEnumerable<T>, IEnumerable where T :IBinaryTree, new()
{
public BinaryTree();
public BinaryTree(IEnumerable<T> list);//
public BinaryTree(T root); //
public int Count { get; }//
public T this[IBinaryTree iBinaryTree] { get; }//
public void Add(T t);//
public void Clear();//
public bool Contains(T iBinaryTree);//
public void Dispose();// ， using
public T Find(IBinaryTree iBinaryTree);//
public T Find(IBinaryTree iBinaryTree, TreeNode<T> node);//
public T FindMax();//
public T FindMin();//
public T FindMin(TreeNode<T> node);//
public IEnumerator<T> GetEnumerator();// ， foreach
public TreeNode<T> Remove(T t);//
public TreeNode<T> Remove(IBinaryTree iBinaryTree, TreeNode<T> node);//
public IEnumerable<T> Sort();// （ ）
public IEnumerable<T> ToList();//
}namespace Utils
{
/// <summary>
///
/// </summary>
public interface IBinaryTree
{
/// <summary>
///
/// </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)
{
this.Data = t;
}
public TreeNode()
: this(default(T))
{
}
}
/// <summary>
///
/// </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);
}
}
//
private TreeNode<T> root;
// （ ， private）
private void Add(T t, TreeNode<T> root)
{
if (t == null)
{
return;
}
if (t.CompareValue < root.Data.CompareValue)
{
if (root.Left == null)
{
root.Left = new TreeNode<T>(t);
++Count;
}
else
{
Add(t, root.Left);
}
}
else if (t.CompareValue > root.Data.CompareValue)
{
if (root.Right == null)
{
root.Right = new TreeNode<T>(t);
++Count;
}
else
{
Add(t, root.Right);
}
}
else
{
root.Data = t;
}
}
//
public void Add(T t)
{
if (t == null)
{
return;
}
if (this.root == null)
{
this.root = new TreeNode<T>(t);
++Count;
}
else
{
Add(t, this.root);
}
}
//
public T FindMin(TreeNode<T> node)
{
if (node == null)
{
return default(T);
}
if (node.Left == null)
{
return node.Data;
}
else
{
return FindMin(node.Left);
}
}
//
public T FindMin()
{
return FindMin(this.root);
}
//
private T FindMax(TreeNode<T> node)
{
if (node.Right == null)
{
return node.Data;
}
else
{
return FindMax(node.Right);
}
}
//
public T FindMax()
{
return FindMax(this.root);
}
//
public TreeNode<T> Remove(IBinaryTree iBinaryTree, TreeNode<T> node)
{
if (node == null)
{
return null;
}
if (iBinaryTree == null)
{
return node;
}
if (iBinaryTree.CompareValue < node.Data.CompareValue)
{
node.Left = Remove(iBinaryTree, node.Left);
}
else if (iBinaryTree.CompareValue > node.Data.CompareValue)
{
node.Right = Remove(iBinaryTree, node.Right);
}
else
{
if (node.Left != null && node.Right != null)
{
T tmpNode = FindMin(node.Right);//
node.Data.CompareValue = tmpNode.CompareValue;//
node.Right = Remove(tmpNode, node.Right);// ，
}
else
{
if (node.Left == null)
{
node = node.Right;
}
else if (node.Right == null)
{
node = node.Left;
}
else
{
node = null;
}
if (this.root.Data.CompareValue == iBinaryTree.CompareValue)//
{
this.root = node;
}
}
--Count;
}
return node;
}
//
public TreeNode<T> Remove(T t)
{
if (this.root == null || t==null)
{
return null;
}
return Remove(t, this.root);
}
//
public T Find(IBinaryTree iBinaryTree, TreeNode<T> node)
{
if (node == null || iBinaryTree == null)
{
return default(T);
}
if (iBinaryTree.CompareValue < node.Data.CompareValue)
{
return Find(iBinaryTree, node.Left);
}
else if (iBinaryTree.CompareValue > node.Data.CompareValue)
{
return Find(iBinaryTree, node.Right);
}
return node.Data;
}
//
public T Find(IBinaryTree iBinaryTree)
{
return Find(iBinaryTree, this.root);
}
//
private bool Contains(IBinaryTree iBinaryTree, TreeNode<T> node)
{
if (node == null || iBinaryTree == null)
{
return false; ;
}
if (iBinaryTree.CompareValue < node.Data.CompareValue)
{
return Contains(iBinaryTree, node.Left);
}
else if (iBinaryTree.CompareValue > node.Data.CompareValue)
{
return Contains(iBinaryTree, node.Right);
}
return iBinaryTree.Equals(node.Data);
}
//
public bool Contains(T iBinaryTree)
{
return Contains(iBinaryTree, this.root);
}
//
public void Clear()
{
while (this.Count > 0)
{
Remove(this.root.Data);
}
this.root = new TreeNode<T>();
}
//
public void Dispose()
{
while (this.Count > 0)
{
Remove(this.root.Data);
}
this.root = null;
}
//
public int Count
{
private set;
get;
}
//
public IEnumerable<T> ToList()
{
IList<T> list = new List<T>(Count);
LCR(this.root,list);
return list;
}
// ， ，
private void LCR(TreeNode<T> node, IList<T> list)
{
if (node == null)
{
return;
}
if (node.Left != null)
{
LCR(node.Left, list);
}
list.Add(node.Data);//
if (node.Right != null)
{
LCR(node.Right, list);
}
}
//
public IEnumerable<T> Sort()
{
return ToList();
}
//
public IEnumerator<T> GetEnumerator()
{
return this.ToList().GetEnumerator();
}
//
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
public T this[IBinaryTree iBinaryTree]
{
get {
return this.Find(iBinaryTree);
}
}
}
public class Node : IBinaryTree
{
/// <summary>
///
/// </summary>
public int CompareValue
{
get;
set;
}
public string Name
{
get;
set;
}
public override string ToString()
{
return string.Format("CompareValue:{0},Name:{1}", this.CompareValue, this.Name);
}
}
}