代表树木的物体

C＃（或.net）中是否有任何对象表示二叉树（或好奇心）和n-ary树？

我不是在谈论表示树控件，而是作为模型对象。

如果没有，是否有任何良好的外部实现？

Answer 1

NGenerics项目是一个很棒的数据结构和算法集合，包括二叉树 。

public class BinaryTree : IVisitableCollection, ITree { // Methods public void Add(BinaryTree subtree); public virtual void breadthFirstTraversal(IVisitor visitor); public virtual void DepthFirstTraversal(OrderedVisitor orderedVisitor); public BinaryTree GetChild(int index); public bool Remove(BinaryTree 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 this[int i] { get; } public virtual BinaryTree Left { get; set; } public virtual BinaryTree Right { get; set; } // ... } 

Answer 2

我不知道框架中有一个，但这是一个实现。

Answer 3

我尝试了一个简单的（非平衡）二叉搜索树。

 public sealed class BinarySearchTree : IEnumerable { private readonly IComparer _comparer; public BinaryTreeNode Root { get; private set; } public BinarySearchTree() { } public BinarySearchTree(IEnumerable collection) : this(collection, Comparer.Default) { } public BinarySearchTree(IEnumerable collection, IComparer 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 root) { Root = root; } public void Add(T val) { var newNode = new BinaryTreeNode(val); if (Root == null) { Root = newNode; return; } Add(Root, newNode); } void Add(BinaryTreeNode root, BinaryTreeNode 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 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 GetEnumerator() { return new BinaryTreeEnumerator(Root); } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } } public sealed class BinaryTreeNode { public BinaryTreeNode Left {get; set;} public BinaryTreeNode Right {get; set;} public T Value {get; private set;} public BinaryTreeNode(T val) { Value = val; } } public sealed class BinaryTreeEnumerator : IEnumerator { private Stack> _stack = new Stack>(); public T Current { get; private set; } public BinaryTreeEnumerator(BinaryTreeNode root) { if (root == null) return; //empty root = Enumerable.Empty() 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 node) { while (node != null) { _stack.Push(node); node = node.Left; } } public void Reset() { _stack.Clear(); } object IEnumerator.Current { get { return Current; } } }