C#将链表存储在二叉树节点中

Question

我想开发一个二叉树结构，使每个节点都存储一个键和一个链表。这种实现背后的原因是，我想用合适的关键字在二进制树（二进制搜索树）中进行搜索，链表将作为存储结构，我可以随时轻松地检索任何信息。有人能在这个方法上帮我吗？或者如果有人能提出更好的方法，我们将不胜感激。

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

Answer 1

您应该考虑使用其中一个内置的，例如另一篇堆栈文章中描述的SortedDictionary：查找.NET二进制树

Answer 2

您应该使用SortedDiccionary："SortedDictionary（Of TKey，TValue）泛型类是一个具有O（logn）检索的二进制搜索树"，请查看文档：SortedDicionary

Answer 3

NGenerics项目是一个很棒的数据结构和算法集合，包括一个二进制树。将其与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();
    }
}