Objetos que representan árboles

Question

¿Hay algún objeto en C# (o en .net) que represente un árbol binario (o por curiosidad) y un árbol n-ary?

No estoy hablando de controles de árbol de presentación, sino como objetos de modelo.

Si no, ¿hay alguna buena implementación externa?

Answer 1

El proyecto NGenerics es una impresionante colección de estructuras de datos y algoritmos que incluye un Binary Tree.

public class BinaryTree<T> : IVisitableCollection<T>, ITree<T> 
{ 
    // Methods 
    public void Add(BinaryTree<T> subtree); 
    public virtual void breadthFirstTraversal(IVisitor<T> visitor); 
    public virtual void 
     DepthFirstTraversal(OrderedVisitor<T> orderedVisitor); 
    public BinaryTree<T> GetChild(int index); 
    public bool Remove(BinaryTree<T> child); 
    public virtual void RemoveLeft(); 
    public virtual void RemoveRight(); 

    // ... 

    // Properties 
    public virtual T Data { get; set; } 
    public int Degree { get; } 
    public virtual int Height { get; } 
    public virtual bool IsLeafNode { get; } 
    public BinaryTree<T> this[int i] { get; } 
    public virtual BinaryTree<T> Left { get; set; } 
    public virtual BinaryTree<T> Right { get; set; } 

    // ... 
} 

Answer 2

No conozco ninguno en el marco, pero here es una implementación.

Answer 3

Mi intento en un árbol de búsqueda binario simple (no equilibrado).

public sealed class BinarySearchTree<T> : IEnumerable<T> 
{ 
    private readonly IComparer<T> _comparer; 
    public BinaryTreeNode<T> Root { get; private set; } 

    public BinarySearchTree() 
    {  
    } 

    public BinarySearchTree(IEnumerable<T> collection) : 
     this(collection, Comparer<T>.Default) 
    { 
    } 

    public BinarySearchTree(IEnumerable<T> collection, IComparer<T> comparer) 
    { 
     if (collection == null) throw new ArgumentNullException("collection"); 
     if (comparer == null) throw new ArgumentNullException("comparer"); 

     _comparer = comparer; 
     foreach (var item in collection) 
      Add(item); 
    } 

    public BinarySearchTree(BinaryTreeNode<T> root) 
    { 
     Root = root; 
    } 

    public void Add(T val) 
    {  
     var newNode = new BinaryTreeNode<T>(val); 
     if (Root == null) 
     { 
      Root = newNode; 
      return; 
     } 

     Add(Root, newNode); 
    } 

    void Add(BinaryTreeNode<T> root, BinaryTreeNode<T> node) 
    { 
     if (_comparer.Compare(node.Value, root.Value) <= 0) 
     { 
      if (root.Left == null) 
       root.Left = node; 
      else 
       Add(root.Left, node); 
     } 
     else //node.Value > root.Value 
     { 
      if (root.Right == null) 
       root.Right = node; 
      else 
       Add(root.Right, node); 
     } 
    } 

    public bool Contains(T val) 
    { 
     return Contains(Root, val); 
    } 

    bool Contains(BinaryTreeNode<T> node, T val) 
    { 
     if (node == null) 
      return false; 

     var comparison = _comparer.Compare(val, node.Value); 
     if (comparison == 0) //val = node.value 
      return true; 
     else if (comparison < 0) //val < node.Value 
      return Contains(node.Left, val); 
     else //val > node.Value 
      return Contains(node.Right, val); 
    } 

    public T GetMinimum() 
    { 
     if (Root == null) 
      return default(T); 

     var node = Root; 
     while (node.Left != null) 
      node = node.Left; 

     return node.Value;  
    } 

    public T GetMaximum() 
    { 
     if (Root == null) 
      return default(T); 

     var node = Root; 
     while (node.Right != null) 
      node = node.Right; 

     return node.Value;  
    } 

    public IEnumerator<T> GetEnumerator() 
    { 
     return new BinaryTreeEnumerator<T>(Root); 
    } 

    IEnumerator IEnumerable.GetEnumerator() 
    { 
     return GetEnumerator(); 
    } 
} 

public sealed class BinaryTreeNode<T> 
{ 
    public BinaryTreeNode<T> Left {get; set;} 
    public BinaryTreeNode<T> Right {get; set;}  
    public T Value {get; private set;} 

    public BinaryTreeNode(T val) 
    { 
     Value = val; 
    } 
} 

public sealed class BinaryTreeEnumerator<T> : IEnumerator<T> 
{ 
    private Stack<BinaryTreeNode<T>> _stack = new Stack<BinaryTreeNode<T>>(); 
    public T Current { get; private set; } 

    public BinaryTreeEnumerator(BinaryTreeNode<T> root) 
    { 
     if (root == null) 
      return; //empty root = Enumerable.Empty<T>() 

     PushLeftBranch(root); 
    } 

    public void Dispose() 
    { 
     _stack = null; //help GC 
    } 

    public bool MoveNext() 
    { 
     if (_stack.Count == 0) 
      return false; 

     var node = _stack.Pop(); 
     Current = node.Value; 

     if (node.Right != null) 
      PushLeftBranch(node.Right); 

     return true; 
    } 

    private void PushLeftBranch(BinaryTreeNode<T> node) 
    { 
     while (node != null) 
     { 
      _stack.Push(node); 
      node = node.Left; 
     } 
    } 

    public void Reset() 
    { 
     _stack.Clear(); 
    } 

    object IEnumerator.Current 
    { 
     get { return Current; } 
    } 
}