表示樹的對象

Question

C＃（或.net）中是否有表示二叉樹（或好奇心）和n元樹的對象？

我不是在談論表示樹控件，而是作爲模型對象。

如果沒有，是否有任何良好的外部實現？

Answer 1

NGenerics項目是一個很棒的數據結構和算法集合，包括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

我不知道在框架中的一個，但here是一個實現。

Answer 3

我試圖在一個簡單的（非平衡）二叉搜索樹。

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; } 
    } 
}