C＃存储二进制树节点链表

Question

我想开发一个二叉树结构，使得每一个节点存储密钥和链接列表。这种实现背后的原因是我想在二叉树（二叉搜索树）内用适当的键进行搜索，并且链表将用作存储结构，以便我可以随时检索任何信息。任何人都可以帮助我解决这个问题吗或者如果任何人都可以建议更好的方法，将不胜感激。

P.S：用二叉树是由于搜索算法为O（log n）和使用链表的性能是由于该结构必须是动态的，所以我不能使用数组，因为它的结构是静态的。

Answer 1

您应该使用排序Diccionary：与LinkedList类喜欢用它的“SortedDictionary（中TKEY的，TValue）泛型类是带O二叉搜索树（log n）的检索”，查看文档： SortedDiccionary

Answer 2

你应该考虑使用内置者之一，如SortedDictionary在这个其他的叠后描述：Looking for a .NET binary tree

Answer 3

NGenerics项目是数据结构和算法包括Binary Tree的真棒集合。

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

启动