Wie übergeordneten Knoten in einer Baumstruktur wie diese

Question

bekommen Wie wäre es möglich, ein Elternteil zu erhalten, wenn Baumstruktur ist wie folgt:

public class TreeModel 
{ 
    public int ID { get; set; } 
    public List<TreeModel> Children { get; set; } 
} 

Lasst uns sagen, dass wir ein übergeordnetes Element Element dazu nicht hinzufügen können, Klasse (public TreeModel Parent {get; set;}).

bearbeiten

Wie Element m22 (ID = 22) Eltern m2 (ID = 2) von der m1 bekommen? Ich dachte, wir könnten durch m1 iterieren und irgendwie Eltern zurückgeben, wenn die Bedingung richtig ist.

var m1 = new TreeModel() { ID = 1 }; 
var m2 = new TreeModel() { ID = 2 }; 
var m21 = new TreeModel() { ID = 21 }; 
var m22 = new TreeModel() { ID = 22 }; 
var m3 = new TreeModel() { ID = 3 }; 

m1.Children.Add(m2); 
m2.Children.Add(m21); 
m2.Children.Add(m22); 
m1.Children.Add(m3); 

var parent = m1.GetParent(p => p.ID == 22); //<-- How? 

Answer 1

public IEnumerable<TreeModel> GetAllDescendants(IEnumerable<TreeModel> rootNodes) 
{ 
    var children = rootNodes.SelectMany(_ => _.Children); 
    return rootNodes.Concat(children); 
} 


public static TreeModel GetParent(this TreeModel rootNode, Func<TreeModel, bool> childSelector) 
{ 
    var allNodes = GetAllDescendants(new [] { rootNode }); 
    var parentsOfSelectedChildren allNodes.Where(node => node.Children.Any(childSelector)); 

    return parentsOfSelectedChildren.Single(); 
} 

m1.GetParent(_ => _.ID == 22); 

1. Besorgen Sie sich eine einfache Liste aller Knoten
2. Diese Liste durchsuchen für den Knoten, dessen direkte Kinder enthält m22

Answer 2

Was:

public class SaneTreeModel: TreeModel 
{ 
    public SaneTreeModel Parent { get; set; } 
} 
} 

Answer 3

Absolut nicht, mit einem Kind, wie Knoten, dass man seine Eltern nicht bekommen kann. Einfach weil es keinen Bezug darauf gibt.

Um das übergeordnete Element des Knotens zu erhalten, müssen Sie entweder das übergeordnete Feld hinzufügen oder die Referenz an anderer Stelle speichern (durch eine Variable oder etwas).

EDIT

@Zulis Wenn Sie von dem Wurzelknoten zu suchen, können Sie auf jeden Fall den Knoten finden Sie wollen. Aber wie gesagt, mit dem Kind-Knoten kann man das nicht machen.

Aber ich denke, man sollte die Suche vermeiden, weil die

Answer 4

langsam sein würde ich dies, indem zunächst das erste Element nähern würde, die die Bedingung (ID == 22 in Ihrem Beispiel) erfüllt und dann die Eltern diesen Befund Element. Nicht die beste Lösung, aber vielleicht brauchen Sie sie separat für etwas anderes.

public TreeModel GetParent(Func<TreeModel, bool> function) 
{ 
    return GetParent(Where(function)); 
} 

private TreeModel GetParent(TreeModel treeModel) 
{ 
    if (Children == null) return null; 

    if (Children.Contains(treeModel)) return this; 

    foreach (TreeModel child in Children) 
    { 
     TreeModel result = child.GetParent(treeModel); 
     if (result != null) 
      return result; 
    } 
    return null; 
} 

private TreeModel Where(Func<TreeModel, bool> function) 
{ 
    if (Children == null) return null; 

    foreach (TreeModel child in Children) 
    { 
     if (function(child)) 
      return child; 

     TreeModel result = child.Where(function); 
     if (result != null) 
      return result; 
    } 

    return null; 
} 

Wenn Sie diesen Codeblock in Ihrer TreeModel Klasse setzen, können Sie das Beispiel zur Verfügung gestellt werden m2

Answer 5

Verwenden Sie dieses Codemuster zurück. Es vereinfacht den Code, da Sie Knoten nicht explizit zu den untergeordneten Elementen hinzufügen müssen und jeder Knoten weiß, wer sein übergeordnetes Element ist und wer seine untergeordneten Elemente sind. Auch es ist alles typsicher.

class Program 
{ 
    static void Main(string[] args) 
    { 
     var m1=new TreeModel() { ID=1 }; 
     var m2=new TreeModel(m1) { ID=2 }; 
     var m21=new TreeModel(m2) { ID=21 }; 
     var m22=new TreeModel(m2) { ID=22}; 
     var m3=new TreeModel(m1) { ID=3 }; 

     var item=m1.RecursiveFind((p) => p.ID==22); 
     var parent=item.Parent; 
     // parent.ID == 2 
     var root=item.Root; 
     // root.ID == 1; 
    } 
} 

public class TreeModel : Tree<TreeModel> 
{ 
    public int ID { get; set; } 
    public TreeModel() { } 
    public TreeModel(TreeModel parent) : base(parent) { } 
} 

public class Tree<T> where T : Tree<T> 
{ 
    protected Tree() : this(null) { } 
    protected Tree(T parent) 
    { 
     Parent=parent; 
     Children=new List<T>(); 
     if(parent!=null) 
     { 
      parent.Children.Add(this as T); 
     } 
    } 
    public T Parent { get; set; } 
    public List<T> Children { get; set; } 
    public bool IsRoot { get { return Parent==null; } } 
    public T Root { get { return IsRoot?this as T:Parent.Root; } } 
    public T RecursiveFind(Predicate<T> check) 
    { 
     if(check(this as T)) return this as T; 
     foreach(var item in Children) 
     { 
      var result=item.RecursiveFind(check); 
      if(result!=null) 
      { 
       return result; 
      } 
     } 
     return null; 
    } 
} 

Wenn Sie von Tree<T> ableiten, erstellen Sie benutzerdefinierte Baumstrukturen, die Sie entwerfen, was die Knotenklasse ist (TreeModel hier) und wie Eltern, Kinder und Geschwister zu handhaben, wenn nötig.