Как преобразовать список hierarchyid` в в бинарное дерево

Question

я работаю по маркетингу многоуровневого (бинарного), который выглядит следующим образом:.

(но бинарное дерево не требуются, чтобы быть совершенным Узел может иметь 0-2 ребенка)

Моя проблема заключается в том, что данные я выборки из базы данных плоский список.

Обратите внимание, что я использую hierarchyid (SQL Server 2014)

В основном TextNode колонна, как панель навигации.

всякая косая черта / представляет собой level.

Если у меня есть TextNode /1/ как root. Затем каждый узел, который начинается с /1/ принадлежит к тому корню, которые являются /1/, /1/1/ и /1/1/1/ (корневой узел включен, который будет уровень 0)

Я попытался accepted answer в этом вопросе, но его не работает.

Как преобразовать плоский список в двоичное дерево, чтобы я мог легко перемещаться и отображать его на экране?

Я использую C#, ASP MVC 5, SQL Server 2014, если это имеет значение.

Answer 1

Здесь очень простая реализация (при условии, что узлы находятся в правильном порядке), который может быть усилен несколькими способами

public interface IRow<out T> 
{ 
    string TextNode { get; } 
    T Value { get; } 
} 

public class TreeNode<T> 
{ 
    private struct NodeDescriptor 
    { 
     public int Level { get; } 
     public int ParentIndex { get; } 

     public NodeDescriptor(IRow<T> row) 
     { 
      var split = row.TextNode.Split(new [] {"/"}, StringSplitOptions.RemoveEmptyEntries); 
      Level = split.Length; 
      ParentIndex = split.Length > 1 ? int.Parse(split[split.Length - 2]) - 1 : 0; 
     } 
    } 

    public T Value { get; } 
    public List<TreeNode<T>> Descendants { get; } 

    private TreeNode(T value) 
    { 
     Value = value; 
     Descendants = new List<TreeNode<T>>(); 
    } 

    public static TreeNode<T> Parse(IReadOnlyList<IRow<T>> rows) 
    { 
     if (rows.Count == 0) 
      return null; 
     var result = new TreeNode<T>(rows[0].Value); 
     FillParents(new[] {result}, rows, 1, 1); 
     return result; 
    } 

    private static void FillParents(IList<TreeNode<T>> parents, IReadOnlyList<IRow<T>> rows, int index, int currentLevel) 
    { 
     var result = new List<TreeNode<T>>(); 
     for (int i = index; i < rows.Count; i++) 
     { 
      var descriptor = new NodeDescriptor(rows[i]); 
      if (descriptor.Level != currentLevel) 
      { 
       FillParents(result, rows, i, descriptor.Level); 
       return; 
      } 
      var treeNode = new TreeNode<T>(rows[i].Value); 
      parents[descriptor.ParentIndex].Descendants.Add(treeNode); 
      result.Add(treeNode); 
     } 
    } 
} 

Пример использования:

public class Row : IRow<string> 
{ 
    public string TextNode { get; } 
    public string Value { get; } 

    public Row(string textNode, string userName) 
    { 
     TextNode = textNode; 
     Value = userName; 
    } 
} 

class Program 
{ 

    static void Main(string[] args) 
    { 
     IRow<string>[] rows = 
     { 
      new Row("/", "Ahmed"), 
      new Row("/1/", "Saeed"), 
      new Row("/2/", "Amjid"), 
      new Row("/1/1/", "Noura"), 
      new Row("/2/1/", "Noura01"), 
      new Row("/2/2/", "Reem01"), 
      new Row("/1/1/1", "Under_noura") 
     }; 

     var tree = TreeNode<string>.Parse(rows); 
     PrintTree(tree); 
    } 

    private static void PrintTree<T>(TreeNode<T> tree, int level = 0) 
    { 
     string prefix = new string('-', level*2); 
     Console.WriteLine("{0}{1}", prefix, tree.Value); 
     foreach (var node in tree.Descendants) 
     { 
      PrintTree(node, level + 1); 
     } 
    } 
}