Як рэалізаваць недвоичное дрэва

У мяне паўсталі праблемы рэалізацыі без бінарнага дрэва, дзе каранёвай вузел можа мець адвольную колькасць даччыных вузлоў. У прынцыпе, я хацеў бы некаторыя ідэі аб тым, куды ісці з гэтым, так як у мяне ёсць некаторы код, напісаны, але я затрымаўся ў гэты момант аб тым, што рабіць далей. Дарэчы, я не магу выкарыстоўваць любога з класаў калекцый на ўсіх. Я магу выкарыстоўваць толькі сістэму.

using System;

namespace alternate_solution
{
//           [root]
//      //     \    \
//   text  text  text  text

class Node//not of type TreeNode (since Node is different from TreeNode)
{
    public string data;
    public Node child;

    public Node(string data)
    {
        this.data = data;
        this.child = null;
    }

}

} enter image description here

6
Падобна на тое, вы маглі б шукаць B + Tree ...
дададзена аўтар Roger Lipscombe, крыніца
Я не магу выкарыстоўваць любога з класа Collections. Я магу выкарыстоўваць толькі сістэмы для рэалізацыі гэтага.
дададзена аўтар Karim O., крыніца
Выдаліць не патрабуецца, адзінае, што ён павінен быць у стане зрабіць гэта ўставіць ў адвольных пазіцыях.
дададзена аўтар Karim O., крыніца
Яе павінна быць практыка для падрыхтоўкі да іншага праекту. Ці магу я выкарыстаць звязаны спіс вузлоў?
дададзена аўтар Karim O., крыніца
@EricLippert 'Адвольнае дрэва мае дзве спасылкі на іншыя вузлы дрэва званых FirstChild і NextSibling. З майго невуцтва, што калі ў вас ёсць больш за два дзяцей?
дададзена аўтар Rami Shareef, крыніца
<�Код> Я не магу выкарыстоўваць любога з класа Collections чаму? Ці з'яўляецца гэта хатняе заданне або інтэрв'ю задача?
дададзена аўтар Ilya Ivanov, крыніца
<�Я> я магу выкарыстоўваць толькі Сістэма абмежаванне мае патрэбу ў тлумачэнні. Акрамя таго, якія аперацыі неабходныя? Ўставіць, Выдаліць ў адвольных пазіцыях?
дададзена аўтар Henk Holterman, крыніца
Падказка: Бінарнае дрэва мае дзве спасылкі на іншыя вузлы дрэва называецца левай і правай. Адвольнае дрэва мае дзве спасылкі на іншыя вузлы дрэва званых FirstChild і NextSibling. Aribitrary дрэвы <�я> з'яўляюцца бінарныя дрэвы; вы проста прысвоіць розныя значэнні для вузлоў.
дададзена аўтар Eric Lippert, крыніца
@RamiShareef: Тады першае дзіця мае брата, і брат мае роднасны, і гэтак далей, да таго часу, пакуль у вас ёсць дастатковую колькасць дзяцей. Вы можаце прачытаць мой адказ.
дададзена аўтар Eric Lippert, крыніца
Чаму не выкарыстоўваць List <> вузлоў дзяцей замест вузла дзіцяці?
дададзена аўтар Jerska, крыніца
Вядома, вы можаце выкарыстоўваць свой уласны дамарослы спіс спасылак на вузлы.
дададзена аўтар lurker, крыніца

6 адказы

Да гэтага часу рашэнне Jerska з'яўляецца лепшым, але гэта залішне складаным.

. Так як я мяркую, што гэта хатняе заданне практыкаванні дазвольце мне даць вам кірунак, вы павінны ўзначаліць ў структуры дадзеных вы хочаце:

class TreeNode
{
  public string Data { get; private set; }
  public TreeNode FirstChild { get; private set; }
  public TreeNode NextSibling { get; private set; }
  public TreeNode (string data, TreeNode firstChild, TreeNode nextSibling)
  {
    this.Data = data;
    this.FirstChild = firstChild;
    this.NextSibling = nextSibling;
  }
}

Давайце зараз перамалююць дыяграму - вертыкальныя лініі «першае дзіця» гарызантальныя лініі «наступны роднасны»

Root
 |
 p1 ----- p2 ----- p4 ----- p6  
 |        |         |       |
 c1       p3       c4       p7
          |                 |
          c2 - c3           c5

Сэнс?

Зараз, вы можаце напісаць код, які вырабляе гэта дрэва, выкарыстоўваючы гэтую структуру дадзеных? Пачаць з самымі правымі лісця і працаваць ваш шлях да кораня :

TreeNode c5 = new TreeNode("c5", null, null);
TreeNode p7 = new TreeNode("p7", c5, null);
TreeNode p6 = new TreeNode("p6", p6, null);
... you do the rest ...

Звярніце ўвагу на тое, што любое дрэва проста бінарнае дрэва «паварочваецца на 45 градусаў», дзе корань не мае "правільны" дзіця. Бінарныя дрэвы і адвольныя дрэвы <�моцны> тое ж самае ; вы проста прызначыць розныя значэнне для двух дзяцей.

29
дададзена
Я шукаў падобнае рашэнне, і гэта вельмі акуратна, я вызначана буду выкарыстоўваць яго. У мяне ёсць адно турботы, хоць: у вашай рэалізацыі, вы дадаеце вузлы з знізу ўверх, і я не думаю, што ваш метад дазваляе дадаваць новы вузел, таму што TreeNodes ёсць асобны набор, так што вы не можаце змяніць існуючы вузел з-за межы класа для размяшчэння новага дзіцяці, брата ці сястры. Як вы маглі б прапанаваць дадаць новы вузел з дапамогай гэтай рэалізацыі?
дададзена аўтар Lou, крыніца
Робячы дрэва зменлівага, было б гэта проста азначае змяненне доступу да палях? Акрамя таго, што вы маеце на ўвазе пазваночнік ў гэтым кантэксце?
дададзена аўтар Lou, крыніца
Падобна на тое, я буду разглядаць гэты падыход. Так, здаецца, незлічонае мноства спосабаў прадставіць адвольнае дрэва, я лічу, што больш просты погляд на гэта мае сэнс. Дзякуй за дапамогу! Толькі адно пытанне, выпісваць усе вузлы ў дрэве, я павінен дадаць усе вузлы ў звязаным спісе, або гэта не абавязкова?
дададзена аўтар Karim O., крыніца
@leoking каментара не з'яўляецца добрым месцам для падручніка па нязменным структурам дадзеных. Паспрабуйце прачытаць нязменнасць тэг на маім блогу MSDN і ўбачыць, калі гэта дапамагае.
дададзена аўтар Eric Lippert, крыніца
@leoking вы можаце зрабіць дрэва змяняецца ці вы можаце перапісаць пазваночнік, каб вырабіць новае дрэва на ўстаўцы. Гэта працуе лепш з нармальным бінарнага дрэва, чым з адным з гэтых адвольных дрэў, але гэта даволі проста.
дададзена аўтар Eric Lippert, крыніца
@KarimOumghar: Гэта непатрэбнае; Вы можаце лёгка напісаць рэкурсіўны абыход гэтага дрэва, гэтак жа вы можаце напісаць рэкурсіўны абыход двайковага дрэва.
дададзена аўтар Eric Lippert, крыніца
@EricLippert: «Бінарныя дрэвы і адвольныя дрэвы адно і тое ж». Аднак, калі я хачу, каб перайсці ад кораня да Р6 я павінен прайсці P1, P2 і P4, у той час як у першапачатковым графіцы гэта была прамая спасылка. Мне здаецца, што характарыстыкі гэтых двух дрэў розныя.
дададзена аўтар Luca Cremonesi, крыніца

Так як вы не можаце выкарыстоўваць калекцыю, чаму б вам не стварыць свой уласны спіс?

class Child {
    Node node;
    Child next = null;

    public Child (Node node) {
        this.node = node;
    }

    public void addChild (Node node) {
        if (this.next == null)
            this.next = new Child (node);
        else
            this.next.addChild (node);
    }
}

class Node {
   public string data;
   public Child children = null;

   public Node (string data) {
       this.data = data;
   }

   public void addChild (Node node) {
       if (this.children == null)
           this.children = new Child (node);
       else
           this.children.addChild (node);
   }
}

І выкарыстоўваць яго як гэта:

Node root = new Node ("Hey");
root.addChild (new Node ("you"));
root.addChild (new Node ("me"));

Цяпер вы будзеце мець:

          Node ("Hey")
       /            \
   Node ("you")     Node ("me")

Тады вам неабходна будзе выконваць розныя функцыі (геттеры, пластыр, і г.д.). Але гэта ваша праца.

3
дададзена

Калі вы не можаце выкарыстаць якая-небудзь калекцыю, захоўваць спасылку на ўсе даччыныя элементы для бацькоў. Вы можаце змадэляваць свой графік з дапамогай наступнай структуры дадзеных:

class Node
{
    public string Data { get; set; }
    public Node Parent { get; set; }

    public Node(string data, Node parent)
    {
        Data = data;
        Parent = parent;
    }
}

Цяпер вы можаце мець столькі Чайлдс для кожнага вузла, як вам падабаецца:

var root = new Node("root", null);

var parent = new Node("parent", root);
var anotherParent = new Node("yetAnotherParent", root);

var child = new Node("Child", parent);
var anotherchild = new Node("anotherchild", parent);
2
дададзена
@Jerska зрабіць вам гэта трэба? Гэта відавочнае патрабаванне? Чаму вы не згадалі пошук у шырыню?
дададзена аўтар Ilya Ivanov, крыніца
@Jerska Вы проста не можаце. Вы ўсё яшчэ павінны захоўваць спасылкі на ўсе даччыныя элементы і рэгуляваць гэты від дрэва вельмі cubersome. Але ўсё-ткі, я лічу патрабаванне «і эй, я не магу выкарыстоўваць любы з гэтай калекцыі рэчы» вельмі неразумна.
дададзена аўтар Ilya Ivanov, крыніца
Але тады, як вы можаце зрабіць з глыбінёй першага пошуку?
дададзена аўтар Jerska, крыніца
Я не аўтар паста, мне было цікава, калі гэта будзе магчыма. І тым не менш, я на самой справе маю такое ж цуд з пошукам ў шырыні.
дададзена аўтар Jerska, крыніца
class Node
{
    public string data;
    public Node parent;
    public IEnumerable children;

    public Node(string data, Node parent, IEnumerable children)
    {
        this.data = data;
        this.parent = parent;
        this.children = children;
    }

}
1
дададзена

Вы можаце прадстаўляць многоходовой дрэва, выкарыстоўваючы тып вузла, які мае толькі наступны паказальнік і паказальнік на дзіця.

Вузла наступны паказальнік выкарыстоўваецца, каб паказаць на наступны роднасны дзіцяці, рэалізаваны ў выглядзе простага звязанага спісу.

Вузла дзіця паказальнік выкарыстоўваецца, каб паказаць на першы даччыны вузел.

Вось некаторыя прыклады кода, які дэманструе, як змясціць гэта разам. Ён не ўтрымлівае якіх-небудзь апрацоўкі памылак і яно не прызначана, каб быць поўным рашэннем, але вы павінны быць у стане сабраць яго і - пры неабходнасці - запусціць яго пад адладчыкам, каб цалкам зразумець, як гэта працуе.

Я таксама дадаў прыклад перечислимого, каб паказаць, як вы маглі б прайсці па вузлах дрэва. Вы, верагодна, хочаце, каб гуляць з гэтым для атрымання вынікаў у розных парадках. Пры выкарыстанні перечислимого занадта складана для таго, што вам трэба, вам трэба будзе напісаць свой уласны просты метад зваротнага сталы наведаць усе вузлы.

Звярніце ўвагу, што тып вузла з'яўляецца агульным ў гэтым прыкладзе, і я толькі выкарыстаць яго для захоўвання радковых дадзеных. Можна проста замяніць T з тыпам вы хочаце, калі вы не патрэбен агульны тып.

using System;
using System.Collections;
using System.Collections.Generic;

namespace Demo
{
    sealed class Node
    {
        public T Data; //Payload.

        public Node Next; //This will point to the next sibling node (if any), forming a linked-list.
        public Node Child;//This will point to the first child node (if any).
    }

    sealed class Tree: IEnumerable
    {
        public Node Root;

        public Node AddChild(Node parent, T data)
        {
            parent.Child = new Node
            {
                Data = data,
                Next = parent.Child//Prepare to place the new node at the head of the linked-list of children.
            };

            return parent.Child;
        }

        public IEnumerator GetEnumerator()
        {
            return enumerate(Root).GetEnumerator();
        }

        private IEnumerable enumerate(Node root)
        {
            for (var node = root; node != null; node = node.Next)
            {
                yield return node.Data;

                foreach (var data in enumerate(node.Child))
                    yield return data;
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }

    class Program
    {
        void run()
        {
            var tree = new Tree();

            tree.Root = new Node{Data = "Root"};

            var l1n3 = tree.AddChild(tree.Root, "L1 N3");
            var l1n2 = tree.AddChild(tree.Root, "L1 N2");
            var l1n1 = tree.AddChild(tree.Root, "L1 N1");

            tree.AddChild(l1n1, "L2 N1 C3");
            tree.AddChild(l1n1, "L2 N1 C2");
            var l2n1 = tree.AddChild(l1n1, "L2 N1 C1");

            tree.AddChild(l1n2, "L2 N2 C3");
            tree.AddChild(l1n2, "L2 N2 C2");
            tree.AddChild(l1n2, "L2 N2 C1");

            tree.AddChild(l1n3, "L2 N3 C3");
            tree.AddChild(l1n3, "L2 N3 C2");
            tree.AddChild(l1n3, "L2 N3 C1");

            tree.AddChild(l2n1, "L3 N1 C3");
            tree.AddChild(l2n1, "L3 N1 C2");
            tree.AddChild(l2n1, "L3 N1 C1");

            tree.Print();
        }

        static void Main()
        {
            new Program().run();
        }
    }

    static class DemoUtil
    {
        public static void Print(this object self)
        {
            Console.WriteLine(self);
        }

        public static void Print(this string self)
        {
            Console.WriteLine(self);
        }

        public static void Print(this IEnumerable self)
        {
            foreach (var item in self)
                Console.WriteLine(item);
        }
    }
}

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

1
дададзена

Некаторыя выпадковыя ідэі:

  • A node will need some sort of list of the child nodes, consider using a concurrency-proof implementation, most likely IEnumerable will fit the bill
  • You might or might not want a backpointer to the parent - conisder one for speedy (read: not too lame) traversal
  • I recommend you create a NodeType to make life easier when consuming the tree
0
дададзена