バイナリツリーノードにリンクリストを格納するC＃

Question

すべての単一ノードがキーとリンクリストを格納するようなバイナリツリー構造を開発したいと考えています。そのような実装の背後にある理由は、適切なキーでバイナリツリー（バイナリ検索ツリー）内で検索​​を行い、リンクされたリストがいつでも簡単に任意の情報を取得できる格納構造として役立つということです。誰もこのアプローチで私を助けることができますか？誰かがより良いアプローチを提案できるかどうかは分かります。

P.S：バイナリツリーを使用するのは、アルゴリズムO（log n）の検索によるもので、リンクリストの使用は構造が動的でなければならないため、構造が静的であるため配列を使用できません。

Answer 1

あなたはソートDiccionaryを使用する必要がありますようLinkedListクラスでそれを使用します。 SortedDiccionary

Answer 2

あなたはSortedDictionaryは、この他のスタックのポストに記載されているような、組み込みのもののいずれかを使用して検討する必要があります。Looking for a .NET binary tree

Answer 3

NGenericsプロジェクトはBinary Treeを含むデータ構造とアルゴリズムの素晴らしいコレクションです。ドキュメントを確認し、「（n個のログを記録）検索SortedDictionaryジェネリッククラスはOで二分探索木である（TKEY、TValueのうち）」：

BinaryTree<LinkedList<T>> tree; 

Answer 4

他の回答で提供されている実装を使用できます。あなた自身でこれを書く方法を理解したいのであれば、私は私のハフマンコーディングプロジェクトから採択したサンプルです。それは完璧ではありませんが、あなたは一般的な考えを見ることができます。私は、使用

class Program 
{ 
    static void Main(string[] args) 
    { 
     string[] testData = new string[] { "aa", "bbb", "cccccc", "d", "ee", "ffffff", "ggggg" }; 
     var expected = new BinaryNode<string>("ffffff"); 
     IBinaryTree<string> tree = new BinaryTree<string>(); 
     tree.Build(testData); 

     var result = tree.Root.Traverse(expected, new List<IBinaryNode<string>>()); 
    } 
} 

バイナリノードのインタフェースと実装

public interface IBinaryNode<T> 
{ 
    int? ID { get; } 
    T Data { get; set; } 
    IBinaryNode<T> RightChild { get; set; } 
    IBinaryNode<T> LeftChild { get; set; } 
    IEnumerable<IBinaryNode<T>> Traverse(IBinaryNode<T> current, IEnumerable<IBinaryNode<T>> recursionData); 
} 

public class BinaryNode<T> : IBinaryNode<T> 
{ 
    public int? ID{get; private set;} 
    public T Data { get; set; } 
    public IBinaryNode<T> RightChild { get; set; } 
    public IBinaryNode<T> LeftChild { get; set; } 

    public BinaryNode():this(default(T)){} 
    public BinaryNode(T data):this(data, null){} 
    public BinaryNode(T data, int? id) 
    { 
     Data = data; 
     ID = id; 
    } 

    public IEnumerable<IBinaryNode<T>> Traverse(IBinaryNode<T> current, IEnumerable<IBinaryNode<T>> recursionData) 
    { 
     // no children found 
     if (RightChild == null && LeftChild == null) 
     { 
      //correct guess BinaryNode has the needed data 
      if (current.Data.Equals(Data)) 
      { 
       return recursionData; 
      } 

      //wrong value - try another leg 
      return null; 
     } 

     //there are children 
     IEnumerable<IBinaryNode<T>> left = null; //tmp left storage 
     IEnumerable<IBinaryNode<T>> right = null; //tmp right storage 

     //start with the left child 
     //and travers in depth by left leg 
     if (LeftChild != null) 
     { 
      //go in depth through the left child 
      var leftPath = new List<IBinaryNode<T>>(); 

      //add previously gathered recursionData 
      leftPath.AddRange(recursionData); 

      leftPath.Add(LeftChild); 

      //recursion call by rigth leg 
      left = LeftChild.Traverse(current, leftPath); 
     } 

     //no left children found 
     //travers by right leg in depth now 
     if (RightChild != null) 
     { 
      //go in depth through the right child 
      var rightPath = new List<IBinaryNode<T>>(); 

      //add previously gathered recursionData 
      rightPath.AddRange(recursionData); 

      //add current value 
      rightPath.Add(RightChild); 

      //recursion call by rigth leg 
      right = RightChild.Traverse(current, rightPath); 
     } 

     //return collected value of left or right 
     if (left != null) 
     { 
      return left; 
     } 

     return right; 
    } 
} 

バイナリツリーのインタフェースと実装

public interface IBinaryTree<T> 
{ 
    void Build(IEnumerable<T> source); 
    IBinaryNode<T> Root { get; set; } 
} 

public class BinaryTree<T> : IBinaryTree<T> 
{ 
    private readonly List<IBinaryNode<T>> nodes; 
    private int nodeId = 0; 

    public IBinaryNode<T> Root { get; set; } 

    public BinaryTree() 
    { 
     nodes = new List<IBinaryNode<T>>(); 
    } 

    public bool IsLeaf(IBinaryNode<T> binaryNode) 
    { 
     return (binaryNode.LeftChild == null && binaryNode.RightChild == null); 
    } 

    public void Build(IEnumerable<T> source) 
    { 
     foreach (var item in source) 
     { 
      var node = new BinaryNode<T>(item, nodeId); 
      nodeId++; 
      nodes.Add(node); 
     } 

     //construct a tree 
     while (nodes.Count > 1) //while more than one node in a list 
     { 
      var taken = nodes.Take(2).ToList(); 

      // Create a parent BinaryNode and sum probabilities 
      var parent = new BinaryNode<T>() 
      { 
       LeftChild = taken[0], 
       RightChild = taken[1] 
      }; 

      //this has been added so remove from the topmost list 
      nodes.Remove(taken[0]); 
      nodes.Remove(taken[1]); 
      nodes.Add(parent); 
     } 

     Root = nodes.FirstOrDefault(); 
    } 
} 

からスタートします