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

Question

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

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

Answer 1

Вы должны рассмотреть возможность использования одного из встроенных, таких как SortedDictionary, описанный в этом другом сообщении стека: Поиск двоичного дерева .NET

Answer 2

Вы можете использовать реализации, представленные в других ответах.Если вы хотите понять, как написать это самостоятельно, вот пример, который я взял из своего проекта кодирования Хаффмана.Это не идеально, но вы можете увидеть общую идею.

Я начну с использования

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

Answer 3

Вы должны использовать Sorted Diccionary: «Универсальный класс SortedDictionary (Of TKey, TValue) является двоичным деревом поиска с O (log n) извлечением», проверьте документацию: SortedDiccionary

Answer 4

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

BinaryTree<LinkedList<T>> tree;