Struktura danych drzewa w C #

248

Szukałem struktury danych drzewa lub wykresu w języku C #, ale chyba nie ma takiej. Wyczerpujące badanie struktur danych za pomocą C # 2.0 wyjaśnia nieco dlaczego. Czy istnieje wygodna biblioteka, która jest powszechnie używana do zapewnienia tej funkcjonalności? Być może poprzez strategię rozwiązywania problemów przedstawionych w artykule.

Czuję się trochę głupio, wdrażając własne drzewo, podobnie jak implementuję własną ArrayList.

Chcę tylko ogólne drzewo, które może być niezrównoważone. Pomyśl o drzewie katalogów. C5 wygląda sprytnie, ale ich struktury drzew wydają się być zaimplementowane jako zrównoważone czerwono-czarne drzewa lepiej nadające się do wyszukiwania niż reprezentujące hierarchię węzłów.

stymuluje
źródło
2
Nieco bardziej ekstremalne drzewa: stackoverflow.com/questions/196294/… ;-)
Tuomas Hietanen
Czy jest jakiś powód, dla którego nie można włączyć TreeView do projektu i używać go? Nie ma powodu, aby pokazywać to użytkownikowi. Oczywiście istnieje kilka rodzajów projektów, gdy nie jest to możliwe. Zawsze można tworzyć nowe klasy, które dziedziczą z przykładowego TreeNode, jeśli potrzebna jest szczególna złożoność?
Po prostu G.
9
Uznałbym za zły pomysł importowania całej biblioteki interfejsu użytkownika dla bardzo prostego drzewa.
pobudza
1
Czy możesz motywować? To nie jest tak, że faktyczne zapotrzebowanie na miejsce na dysku twardym jest już problemem? Niezdarny? Jak wspomniałem wcześniej, rozumiem, że nie jest to rozwiązanie dla specjalistycznego oprogramowania lub czegoś bez istniejącego interfejsu użytkownika. Jestem leniwym programistą, jeśli mogę dostać strukturę za darmo, to wszystko dobrze. A istniejąca biblioteka ma wiele za darmo, można znaleźć wiele kodów od ludzi, którzy używali jej do wielu rzeczy.
Po prostu G.
Nie kłócę się, chcę tylko poznać twoje rozumowanie.
Po prostu G.

Odpowiedzi:

155

Moja najlepsza rada byłaby taka, że ​​nie ma standardowej struktury danych drzewa, ponieważ istnieje tak wiele sposobów jej implementacji, że niemożliwe byłoby objęcie wszystkich baz jednym rozwiązaniem. Im bardziej konkretne rozwiązanie, tym mniej prawdopodobne, że będzie ono miało zastosowanie do danego problemu. Denerwuje mnie nawet LinkedList - co jeśli chcę okrągłej listy łączy?

Podstawową strukturą, którą musisz zaimplementować, będzie kolekcja węzłów, a oto kilka opcji na dobry początek. Załóżmy, że węzeł klasy jest klasą bazową całego rozwiązania.

Jeśli potrzebujesz tylko nawigować w dół drzewa, klasa Node potrzebuje listy dzieci.

Jeśli potrzebujesz nawigować w górę drzewa, klasa Node potrzebuje łącza do swojego węzła nadrzędnego.

Zbuduj metodę AddChild, która zajmie się wszystkimi szczegółami tych dwóch punktów i wszelkimi innymi logikami biznesowymi, które muszą zostać zaimplementowane (limity potomne, sortowanie dzieci itp.)

David Boike
źródło
5
osobiście nie miałbym nic przeciwko dodaniu do biblioteki jakiegoś samobalansującego drzewa binarnego, ponieważ jest to dodatkowa praca niż tylko używanie listy sąsiadujących.
jk.
8
@jk Uważam, że SortedDictionary i SortedSet są zbudowane na czerwonych / czarnych drzewach, więc korzystanie z nich powinno działać.
jonp
Spójrz na wzór złożony ;-) Dokładnie to, czego szukasz
Nicolas Voron
119
delegate void TreeVisitor<T>(T nodeData);

class NTree<T>
{
    private T data;
    private LinkedList<NTree<T>> children;

    public NTree(T data)
    {
         this.data = data;
        children = new LinkedList<NTree<T>>();
    }

    public void AddChild(T data)
    {
        children.AddFirst(new NTree<T>(data));
    }

    public NTree<T> GetChild(int i)
    {
        foreach (NTree<T> n in children)
            if (--i == 0)
                return n;
        return null;
    }

    public void Traverse(NTree<T> node, TreeVisitor<T> visitor)
    {
        visitor(node.data);
        foreach (NTree<T> kid in node.children)
            Traverse(kid, visitor);
    }
}

Prosta rekurencyjna implementacja ... <40 linii kodu ... Musisz tylko zachować odniesienie do katalogu głównego drzewa poza klasą lub zawinąć w inną klasę, może zmienić nazwę na TreeNode?

Aaron Gage
źródło
22
W tym przypadku, w C # tak, można uniknąć pisania własnych delegata i użyć gotowego Action<T>delegata: public void traverse(NTree<T> node, Action<T> visitor). Akcja <> 's podpis jest: void Action<T>( T obj ). Istnieją również wersje od 0 do 4 różnych parametrów. Istnieje również analogiczny delegat dla wywoływanych funkcji Func<>.
Benny Jobigan
2
jak mam nazwać tego delegata?
Dziwnie
3
dobrym pomysłem byłoby zmienianie metody trawersowania na statyczne lub ewentualnie owijanie jej w celu ukrycia rekurencyjnej natury, ale przejście do niej jest proste: utwórz metodę z podpisem delegata, tj. dla drzewa ints: void my_visitor_impl (int datum) - ustaw go jako statyczny, jeśli potrzebujesz, utwórz instancję delgate: TreeVisitor <int> my_visitor = my_visitor_impl; a następnie wywołaj w węźle głównym lub klasie NTree, jeśli ustawisz go na statyczny: NTree <int> .traverse (my_tree, my_visitor)
Aaron Gage
10
Uczynienie addChild () zwracaniem dodanego NTree uprościłoby dodawanie danych do drzewa. (Chyba że brakuje mi sprytnego sposobu na zbudowanie drzewa za pomocą tego, bez polegania na szczegółach implementacji, które nowo dodane dziecko == getChild (1)?)
Rory
1
Myślę, że to stwierdzenie --i == 0zadziała tylko w jednym przypadku? Czy to prawda. To mnie pomieszało
Waseem Ahmad Naeem
57

Oto moja, bardzo podobna do Aarona Gage'a , moim zdaniem nieco bardziej konwencjonalna. Dla moich celów nie napotkałem żadnych problemów z wydajnością List<T>. W razie potrzeby przejście do LinkedList byłoby łatwe.


namespace Overby.Collections
{
    public class TreeNode<T>
    {
        private readonly T _value;
        private readonly List<TreeNode<T>> _children = new List<TreeNode<T>>();

        public TreeNode(T value)
        {
            _value = value;
        }

        public TreeNode<T> this[int i]
        {
            get { return _children[i]; }
        }

        public TreeNode<T> Parent { get; private set; }

        public T Value { get { return _value; } }

        public ReadOnlyCollection<TreeNode<T>> Children
        {
            get { return _children.AsReadOnly(); }
        }

        public TreeNode<T> AddChild(T value)
        {
            var node = new TreeNode<T>(value) {Parent = this};
            _children.Add(node);
            return node;
        }

        public TreeNode<T>[] AddChildren(params T[] values)
        {
            return values.Select(AddChild).ToArray();
        }

        public bool RemoveChild(TreeNode<T> node)
        {
            return _children.Remove(node);
        }

        public void Traverse(Action<T> action)
        {
            action(Value);
            foreach (var child in _children)
                child.Traverse(action);
        }

        public IEnumerable<T> Flatten()
        {
            return new[] {Value}.Concat(_children.SelectMany(x => x.Flatten()));
        }
    }
}
Ronnie Overby
źródło
dlaczego twoja właściwość Value jest widoczna, gdy ustawiasz ją w konstruktorze? która pozostawia otwartą na manipulację PO ustawieniu go już za pomocą konstruktora, prawda? Czy powinien być prywatny?
PositiveGuy
Jasne, dlaczego nie uczynić go niezmiennym? Edytowane.
Ronnie Overby
Dzięki! Bardzo podobało mi się to, że nie musiałem pisać własnego. (Nadal nie mogę uwierzyć, że nie jest to coś, co istnieje natywnie. Zawsze myślałem, że .net, a przynajmniej .net 4.0, mam wszystko .)
neminem
3
Podobało mi się to rozwiązanie. Stwierdziłem również, że muszę wstawić, dodałem następującą metodę, aby to zrobić. public TreeNode<T> InsertChild(TreeNode<T> parent, T value) { var node = new TreeNode<T>(value) { Parent = parent }; parent._children.Add(node); return node; } var five = myTree.AddChild(5); myTree.InsertChild(five, 55);
JabberwockyDecompiler
48

Jeszcze inna struktura drzewa:

public class TreeNode<T> : IEnumerable<TreeNode<T>>
{

    public T Data { get; set; }
    public TreeNode<T> Parent { get; set; }
    public ICollection<TreeNode<T>> Children { get; set; }

    public TreeNode(T data)
    {
        this.Data = data;
        this.Children = new LinkedList<TreeNode<T>>();
    }

    public TreeNode<T> AddChild(T child)
    {
        TreeNode<T> childNode = new TreeNode<T>(child) { Parent = this };
        this.Children.Add(childNode);
        return childNode;
    }

    ... // for iterator details see below link
}

Przykładowe użycie:

TreeNode<string> root = new TreeNode<string>("root");
{
    TreeNode<string> node0 = root.AddChild("node0");
    TreeNode<string> node1 = root.AddChild("node1");
    TreeNode<string> node2 = root.AddChild("node2");
    {
        TreeNode<string> node20 = node2.AddChild(null);
        TreeNode<string> node21 = node2.AddChild("node21");
        {
            TreeNode<string> node210 = node21.AddChild("node210");
            TreeNode<string> node211 = node21.AddChild("node211");
        }
    }
    TreeNode<string> node3 = root.AddChild("node3");
    {
        TreeNode<string> node30 = node3.AddChild("node30");
    }
}

BONUS
Zobacz pełne drzewo z:

  • iterator
  • badawczy
  • Java / C #

https://github.com/gt4dev/yet-another-tree-structure

Grzegorz Dev
źródło
Jak korzystać z wyszukiwania w twoim przykładzie kodu? Skąd nodepochodzi? Czy to oznacza, że ​​muszę iterować po drzewie, aby użyć kodu wyszukiwania?
BadmintonCat
@GrzegorzDev Może -1, ponieważ nie implementuje wszystkich IEnumerable<>członków, więc się nie kompiluje.
Uwe Keim
1
@UweKeim Dobra robota, następnym razem spróbuj użyć kodu z rzeczywistymi zastosowaniami.
szab.kel,
Jedynym problemem, jaki widzę, jest to, że nie będzie poprawnie serializowany przy użyciu podstawowego JsonConvert, ponieważ implementuje IEnumerable <>
Rakiah
22

Ogólnie doskonała ogólna biblioteka kolekcji C5 ma kilka różnych struktur danych opartych na drzewach, w tym zestawy, torby i słowniki. Kod źródłowy jest dostępny, jeśli chcesz przestudiować szczegóły jego implementacji. (Użyłem kolekcji C5 w kodzie produkcyjnym z dobrymi wynikami, chociaż nie użyłem żadnej konkretnej struktury drzewa).

McKenzieG1
źródło
7
Nie wiem, czy może coś się zmieniło, ale w tej chwili książka jest dostępna do pobrania w formacie PDF ze strony C5.
Oskar
4
Brak dokumentacji nie stanowi już problemu, ponieważ biblioteka uzupełnia bibliotekę o długości 272 stron ... Nie mogę komentować jakości kodu, ale sądząc po jakości dokumentów, naprawdę nie mogę się doczekać dzisiejszej nocy!
Florian Doyon
2
Z tego, co rozumiem, ta biblioteka C5 w ogóle nie ma drzew, ale tylko niektóre struktury danych pochodzące z drzew.
roim
10

Zobacz http://quickgraph.codeplex.com/

QuickGraph zapewnia ogólne struktury danych i algorytmy ukierunkowanych / niekierowanych grafów dla .Net 2.0 i wyższych. QuickGraph jest wyposażony w algorytmy, takie jak głębokość pierwszego wyszukiwania, pierwsze wyszukiwanie oddechu, wyszukiwanie A *, najkrótsza ścieżka, k-najkrótsza ścieżka, maksymalny przepływ, minimalne drzewo opinające, najmniej powszechni przodkowie itp. QuickGraph obsługuje MSAGL, GLEE i Graphviz do renderuj wykresy, serializację do GraphML itp.

nietras
źródło
8

Jeśli chcesz napisać własny, możesz zacząć od tego sześcioczęściowego dokumentu szczegółowo opisującego efektywne wykorzystanie struktur danych C # 2.0 i jak zacząć analizować implementację struktur danych w C #. Każdy artykuł zawiera przykłady i instalatora z przykładami, które możesz śledzić.

„Wszechstronne badanie struktur danych za pomocą C # 2.0” Scott Mitchell

użytkownik7116
źródło
7

Mam małe rozszerzenie do rozwiązań.

Korzystając z rekurencyjnej deklaracji ogólnej i pochodnej podklasy, możesz lepiej skoncentrować się na rzeczywistym celu.

Zauważ, że różni się od implementacji innej niż ogólna, nie musisz rzutować „node” w „NodeWorker”.

Oto mój przykład:

public class GenericTree<T> where T : GenericTree<T> // recursive constraint  
{
  // no specific data declaration  

  protected List<T> children;

  public GenericTree()
  {
    this.children = new List<T>();
  }

  public virtual void AddChild(T newChild)
  {
    this.children.Add(newChild);
  }

  public void Traverse(Action<int, T> visitor)
  {
    this.traverse(0, visitor);
  }

  protected virtual void traverse(int depth, Action<int, T> visitor)
  {
    visitor(depth, (T)this);
    foreach (T child in this.children)
      child.traverse(depth + 1, visitor);
  }
}

public class GenericTreeNext : GenericTree<GenericTreeNext> // concrete derivation
{
  public string Name {get; set;} // user-data example

  public GenericTreeNext(string name)
  {
    this.Name = name;
  }
}

static void Main(string[] args)  
{  
  GenericTreeNext tree = new GenericTreeNext("Main-Harry");  
  tree.AddChild(new GenericTreeNext("Main-Sub-Willy"));  
  GenericTreeNext inter = new GenericTreeNext("Main-Inter-Willy");  
  inter.AddChild(new GenericTreeNext("Inter-Sub-Tom"));  
  inter.AddChild(new GenericTreeNext("Inter-Sub-Magda"));  
  tree.AddChild(inter);  
  tree.AddChild(new GenericTreeNext("Main-Sub-Chantal"));  
  tree.Traverse(NodeWorker);  
}  

static void NodeWorker(int depth, GenericTreeNext node)  
{                                // a little one-line string-concatenation (n-times)
  Console.WriteLine("{0}{1}: {2}", String.Join("   ", new string[depth + 1]), depth, node.Name);  
}  
Erik Nagel
źródło
czym jest głębokość i skąd i jak ją zdobyć?
PositiveGuy
@ WeDoTDD.com patrząc na swoją klasę widzisz, że Traverse deklaruje jako 0, aby rozpocząć od węzła głównego, a następnie używa metody traverse, dodając do tego int każdą iterację.
Edward
Jak przeszukasz całe drzewo w poszukiwaniu określonego węzła?
mattpm
6

Oto moje własne:

class Program
{
    static void Main(string[] args)
    {
        var tree = new Tree<string>()
            .Begin("Fastfood")
                .Begin("Pizza")
                    .Add("Margherita")
                    .Add("Marinara")
                .End()
                .Begin("Burger")
                    .Add("Cheese burger")
                    .Add("Chili burger")
                    .Add("Rice burger")
                .End()
            .End();

        tree.Nodes.ForEach(p => PrintNode(p, 0));
        Console.ReadKey();
    }

    static void PrintNode<T>(TreeNode<T> node, int level)
    {
        Console.WriteLine("{0}{1}", new string(' ', level * 3), node.Value);
        level++;
        node.Children.ForEach(p => PrintNode(p, level));
    }
}

public class Tree<T>
{
    private Stack<TreeNode<T>> m_Stack = new Stack<TreeNode<T>>();

    public List<TreeNode<T>> Nodes { get; } = new List<TreeNode<T>>();

    public Tree<T> Begin(T val)
    {
        if (m_Stack.Count == 0)
        {
            var node = new TreeNode<T>(val, null);
            Nodes.Add(node);
            m_Stack.Push(node);
        }
        else
        {
            var node = m_Stack.Peek().Add(val);
            m_Stack.Push(node);
        }

        return this;
    }

    public Tree<T> Add(T val)
    {
        m_Stack.Peek().Add(val);
        return this;
    }

    public Tree<T> End()
    {
        m_Stack.Pop();
        return this;
    }
}

public class TreeNode<T>
{
    public T Value { get; }
    public TreeNode<T> Parent { get; }
    public List<TreeNode<T>> Children { get; }

    public TreeNode(T val, TreeNode<T> parent)
    {
        Value = val;
        Parent = parent;
        Children = new List<TreeNode<T>>();
    }

    public TreeNode<T> Add(T val)
    {
        var node = new TreeNode<T>(val, this);
        Children.Add(node);
        return node;
    }
}

Wynik:

Fastfood
   Pizza
      Margherita
      Marinara
   Burger
      Cheese burger
      Chili burger
      Rice burger
moien
źródło
4

Wypróbuj tę prostą próbkę.

public class TreeNode<TValue>
{
    #region Properties
    public TValue Value { get; set; }
    public List<TreeNode<TValue>> Children { get; private set; }
    public bool HasChild { get { return Children.Any(); } }
    #endregion
    #region Constructor
    public TreeNode()
    {
        this.Children = new List<TreeNode<TValue>>();
    }
    public TreeNode(TValue value)
        : this()
    {
        this.Value = value;
    }
    #endregion
    #region Methods
    public void AddChild(TreeNode<TValue> treeNode)
    {
        Children.Add(treeNode);
    }
    public void AddChild(TValue value)
    {
        var treeNode = new TreeNode<TValue>(value);
        AddChild(treeNode);
    }
    #endregion
}
Bereż
źródło
2

Tworzę klasę Node, która może być pomocna dla innych osób. Klasa ma właściwości takie jak:

  • Dzieci
  • Przodkowie
  • Potomków
  • Rodzeństwo
  • Poziom węzła
  • Rodzic
  • Korzeń
  • Itp.

Istnieje również możliwość przekonwertowania płaskiej listy elementów o Id i ParentId na drzewo. Węzły zawierają odniesienie zarówno do dzieci, jak i rodzica, dzięki czemu iteracja węzłów jest dość szybka.

Alex Siepman
źródło
2

Ponieważ nie wspomniano o tym, chciałbym zwrócić uwagę na uwolnioną teraz bazę kodu .net: w szczególności kod dla SortedSetimplementacji Red-Black-Tree:

https://github.com/Microsoft/referencesource/blob/master/System/compmod/system/collections/generic/sortedset.cs

Jest to jednak zrównoważona struktura drzewa. Więc moja odpowiedź jest bardziej odniesieniem do tego, co uważam za jedyną natywną strukturę drzewa w bibliotece rdzenia .net.

Meirion Hughes
źródło
2

Ukończyłem kod udostępniony przez @Berezh.

  public class TreeNode<T> : IEnumerable<TreeNode<T>>
    {

        public T Data { get; set; }
        public TreeNode<T> Parent { get; set; }
        public ICollection<TreeNode<T>> Children { get; set; }

        public TreeNode(T data)
        {
            this.Data = data;
            this.Children = new LinkedList<TreeNode<T>>();
        }

        public TreeNode<T> AddChild(T child)
        {
            TreeNode<T> childNode = new TreeNode<T>(child) { Parent = this };
            this.Children.Add(childNode);
            return childNode;
        }

        public IEnumerator<TreeNode<T>> GetEnumerator()
        {
            throw new NotImplementedException();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return (IEnumerator)GetEnumerator();
        }
    }
    public class TreeNodeEnum<T> : IEnumerator<TreeNode<T>>
    {

        int position = -1;
        public List<TreeNode<T>> Nodes { get; set; }

        public TreeNode<T> Current
        {
            get
            {
                try
                {
                    return Nodes[position];
                }
                catch (IndexOutOfRangeException)
                {
                    throw new InvalidOperationException();
                }
            }
        }


        object IEnumerator.Current
        {
            get
            {
                return Current;
            }
        }


        public TreeNodeEnum(List<TreeNode<T>> nodes)
        {
            Nodes = nodes;
        }

        public void Dispose()
        {
        }

        public bool MoveNext()
        {
            position++;
            return (position < Nodes.Count);
        }

        public void Reset()
        {
            position = -1;
        }
    }
Ashkan Sirous
źródło
Dobry projekt. Jednak nie jestem pewien, czy węzeł „jest” sekwencją swojego węzła potomnego. Rozważę następujące: węzeł „ma” zero lub więcej węzłów potomnych, więc węzeł nie pochodzi z sekwencji węzłów potomnych, ale jest agregacją (składem?) Jego węzłów potomnych
Harald Coppoolse,
2

Oto drzewo

public class Tree<T> : List<Tree<T>>
{
    public  T Data { get; private set; }

    public Tree(T data)
    {
        this.Data = data;
    }

    public Tree<T> Add(T data)
    {
        var node = new Tree<T>(data);
        this.Add(node);
        return node;
    }
}

Możesz nawet użyć inicjatorów:

    var tree = new Tree<string>("root")
    {
        new Tree<string>("sample")
        {
            "console1"
        }
    };
Visar
źródło
1

Większość drzew składa się z przetwarzanych danych.

Powiedzmy, że masz personklasę, która zawiera szczegóły czyjejś osoby parents, czy wolałbyś raczej mieć strukturę drzewa jako część „klasy domeny”, czy użyć osobnej klasy drzewa, która zawierała linki do obiektów twojej osoby? Pomyśl o prostej operacji jak dostaję cały grandchildrentematyce person, powinno to być kod w person klasie, czy też użytkownik personklasie muszą wiedzieć o osobnej klasy drzewa?

Innym przykładem jest parsowanie drzewa w kompilatorze…

Oba te przykłady pokazują, że koncepcja drzewa jest częścią domeny danych, a użycie osobnego drzewa ogólnego przeznaczenia co najmniej podwaja liczbę tworzonych obiektów, a także utrudnia programowanie interfejsu API.

Chcemy sposobu ponownego wykorzystania standardowych operacji na drzewach, bez konieczności ich ponownego wdrażania dla wszystkich drzew, przy jednoczesnym braku konieczności używania standardowej klasy drzewa. Boost próbował rozwiązać ten problem w C ++, ale jeszcze nie widziałem żadnego efektu dla .NET.

Ian Ringrose
źródło
@Puchacz, przepraszam, że brakuje mi 15 lat danych na temat C ++, spójrz na Wzmocnienie i Szablony, po kilku słabych badaniach możesz je zrozumieć. Moc ma wysokie koszty nauki !!
Ian Ringrose,
1

Dodałem kompletne rozwiązanie i przykład, używając klasy NTree powyżej, dodałem również metodę „AddChild” ...

    public class NTree<T>
    {
        public T data;
        public LinkedList<NTree<T>> children;

        public NTree(T data)
        {
            this.data = data;
            children = new LinkedList<NTree<T>>();
        }

        public void AddChild(T data)
        {
            var node = new NTree<T>(data) { Parent = this };
            children.AddFirst(node);
        }

        public NTree<T> Parent { get; private set; }

        public NTree<T> GetChild(int i)
        {
            foreach (NTree<T> n in children)
                if (--i == 0)
                    return n;
            return null;
        }

        public void Traverse(NTree<T> node, TreeVisitor<T> visitor, string t, ref NTree<T> r)
        {
            visitor(node.data, node, t, ref r);
            foreach (NTree<T> kid in node.children)
                Traverse(kid, visitor, t, ref r);
        }
    }
    public static void DelegateMethod(KeyValuePair<string, string> data, NTree<KeyValuePair<string, string>> node, string t, ref NTree<KeyValuePair<string, string>> r)
    {
        string a = string.Empty;
        if (node.data.Key == t)
        {
            r = node;
            return;
        }
    }

za pomocą

 NTree<KeyValuePair<string, string>> ret = null;
 tree.Traverse(tree, DelegateMethod, node["categoryId"].InnerText, ref ret);
Dmitry
źródło
Czy trawersowanie powinno być metodą statyczną? Wydaje się to bardzo niewygodne jako metoda instancji, która sama się
przenika
0

Oto moja implementacja BST

class BST
{
    public class Node
    {
        public Node Left { get; set; }
        public object Data { get; set; }
        public Node Right { get; set; }

        public Node()
        {
            Data = null;
        }

        public Node(int Data)
        {
            this.Data = (object)Data;
        }

        public void Insert(int Data)
        {
            if (this.Data == null)
            {
                this.Data = (object)Data;
                return;
            }
            if (Data > (int)this.Data)
            {
                if (this.Right == null)
                {
                    this.Right = new Node(Data);
                }
                else
                {
                    this.Right.Insert(Data);
                }
            }
            if (Data <= (int)this.Data)
            {
                if (this.Left == null)
                {
                    this.Left = new Node(Data);
                }
                else
                {
                    this.Left.Insert(Data);
                }
            }
        }

        public void TraverseInOrder()
        {
            if(this.Left != null)
                this.Left.TraverseInOrder();
            Console.Write("{0} ", this.Data);
            if (this.Right != null)
                this.Right.TraverseInOrder();
        }
    }

    public Node Root { get; set; }
    public BST()
    {
        Root = new Node();
    }
}

źródło
0

Jeśli zamierzasz wyświetlić to drzewo w GUI, możesz użyć TreeView i TreeNode . (Podejrzewam, że technicznie można utworzyć TreeNode bez nakładania go na GUI, ale ma on większy narzut niż prosta implementacja TreeNode u siebie).

Denise Skidmore
źródło
-4

Jeśli potrzebujesz implementacji struktury danych zrootowanych drzew, która zużywa mniej pamięci, możesz napisać klasę Node w następujący sposób (implementacja C ++):

class Node {
       Node* parent;
       int item; // depending on your needs

       Node* firstChild; //pointer to left most child of node
       Node* nextSibling; //pointer to the sibling to the right
}
Jake
źródło
12
Publikowanie kodu C ++ w pytaniu specjalnie dla C # nie jest najlepszym pomysłem, Jake. Zwłaszcza taki, który zawiera wskaźniki. Wiesz, że wskaźniki są ścigane bezlitośnie w C #, prawda? : p
ThunderGr
2
@ThunderGr to niesprawiedliwe. Odpowiedź w języku C # byłaby lepsza, ale te wskaźniki C ++ mogą być rozumiane przez C #-mówców jako odniesienia (są mniej bezpieczne, ok). Po tym, jak David Boike, Aaron Gage, Ronnie Overby, Grzegorz Dev, Berezh i Erik Nagel zasugerowali zasadniczo tę samą strukturę danych z niewielkimi różnicami tylko w wyrażeniu, Jake zasugerował rozbicie połączonej listy, uzyskując prostsze struktury z tylko jednym rodzajem węzła i żeglowność rodzeństwa. Nie wyrażaj niechęci do C ++, głosując w dół konstruktywną odpowiedzią.
migle
3
@migle Nie głosowałem za odpowiedzią (nie głosowałem też za). I nie lubię C ++. Zobaczyłem, że odpowiedź została odrzucona, a nikt nie sugerował Jake'owi niczego, dlaczego i jak poprawi swoją odpowiedź. Nie chodzi o „bycie lepszym”. Pytanie jest oznaczone tylko dla C #. Publikowanie odpowiedzi w innym języku niż tag nie jest zalecane, a niektóre osoby będą głosować negatywnie.
ThunderGr