الكائنات التي تمثل الأشجار
-
05-07-2019 - |
سؤال
هل هناك أي الكائنات في C # (أو في صافي) الذي يمثل شجرة ثنائية (أو الفضول) ون آرى الشجرة؟
وأنا لا أتحدث عن الضوابط شجرة العرض، ولكن ككائنات نموذج.
إذا لم يكن كذلك، هل هناك أي تطبيقات خارجية جيدة؟
المحلول
NGenerics المشروع هو عبارة عن مجموعة رهيبة من هياكل البيانات والخوارزميات بما في ذلك <أ href ل = "http://code.google.com/p/ngenerics/wiki/BinaryTree" يختلط = "noreferrer"> ثنائي شجرة .
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; }
// ...
}
نصائح أخرى
وأنا لست على علم واحد في هذا الإطار، ولكن هنا هو تطبيق واحد.
ومحاولة مني في بسيطة (غير موازنة) شجرة البحث الثنائية.
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; }
}
}
وأنا في وقت متأخر للحزب ولكن هذه المقالة ويقول ان SortedList أ > ويعمل الاثنان SortedDictionary على الأشجار.
لا تنتمي إلى StackOverflow