C# сохранение связанного списка в двоичных деревьях узлов

Question

Я хотел бы разработать двоичную древовидную структуру, чтобы каждый отдельный узел хранил ключ и связанный список. причиной такой реализации является то, что я хотел бы выполнить поиск в двоичном дереве (двоичном дереве поиска) с соответствующим ключом, а связанный список будет служить структурой хранения, которую я мог бы легко получить любую информацию в любое время. Может ли кто-нибудь помочь мне в этом подходе? или если кто-то может предложить лучший подход, будет оценен.

P.S: Использование двоичного дерева обусловлено выполнением алгоритма поиска O (log n) и использованием связанного списка из-за того, что структура должна быть динамической, поэтому я не могу использовать массивы, поскольку ее структура статична.

Answer 1

Вы должны использовать отсортированный Diccionary: "The SortedDictionary (Of TKey, TValue) общий класс представляет собой бинарное дерево поиска с O (журнал N) поиск", проверьте документацию: SortedDiccionary

Answer 2

Вы должны рассмотреть возможность использования одного из встроенных в них, таких как SortedDictionary, описанном в этом другом посте стеки: Looking for a .NET binary tree

Answer 3

NGenerics проект является удивительной совокупностью структур данных и алгоритмов, включая Binary Tree. Используйте его с LinkedList класса, как:

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