Вычислить Предзаказ обхода дерева Из DataTable структуры

Question

У меня есть DataTable, который имеет следующую структуру:

Root | Level 1 | Level 2 | Level 3 | Tree L | Tree R 
Food         1  18 
     Fruit       2  11 
       Red     3  6 
          Cherry 4  5 
       Yellow    7  10 
          Banana 8  9 
     Meat       12  17 
       Beef    13  14 
       Pork    15  16 

Использование C#, мне нужно пересечь эту структуру и вычислить правильное дерево L и значение Дерева R для каждого узла. Это всего лишь пример, у реальной структуры есть несколько сотен узлов, которые выходят, по крайней мере, на уровень 7, но, возможно, больше.

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

Answer 1

Итак, вы хотите отслеживать порядок посещения дерева, но у вас есть порядок, разделенный на L и R. Они соответствуют «входу» и «выходу» функции Visit для структуры Node. Предполагая Node класс с методом Node.Visit(), вы можете:

private static List<Tuple<char,Node>> VisitOrder = new List<Tuple<char,Node>>(); 

public void Visit() 
{ 
    VisitOrder.Add(Tuple.Create('L', this)); 
    // whatever visit logic you use here 
    VisitOrder.Add(Tuple.Create('R', this)); 
} 

Когда вы закончите, все, что вам нужно сделать, это сделать, это посмотреть на VisitOrder значений. Они сохраняются в List в порядке возрастания, где индекс соответствует его позиции в последовательности посещений. Таким образом, каждый элемент в List является Tuple, описывающим, какое значение он соответствует, и который он посетил. Node.

Edit:

Чтобы получить окончательный выходной формат, вы могли бы сделать что-то вроде:

var LTree = VisitOrder 
    .Where(t => t.First == 'L') 
    .Select((t, i) => String.Format("{0}) {1}", i + 1, t.Second.Name)); 
var RTree = VisitOrder 
    .Where(t => t.First == 'R') 
    .Select((t, i) => String.Format("{0}) {1}", i + 1, t.Second.Name)); 

Answer 2

Вот как я понял это:

private class FolderRow 
    { 
     public int Indent 
     { 
      get { return this.Row.GetValue("Indent", 0); } 
      set { this.Row["Indent"] = value; } 
     } 
     public int Left 
     { 
      get { return this.Row.GetValue("Tree L", 0); } 
      set { this.Row["Tree L"] = value; } 
     } 
     public int Right 
     { 
      get { return this.Row.GetValue("Tree R", 0); } 
      set { this.Row["Tree R"] = value; } 
     } 
     public Guid Id 
     { 
      get { return this.Row.GetValue("FolderID", Guid.Empty); } 

     } 
     public DataRow Row { get; private set; } 

     public int RowNum { get; set; } 

     public bool RowComplete { get { return this.Left > 0 && this.Right > 0; } } 

     public FolderRow(DataRow row, int rowNum) 
     { 
      this.Row = row; 
      this.RowNum = rowNum; 
     } 
    }  

[TestMethod] 
public void ImportFolderStructure() 
{ 
    var inputTable = FileUtil.GetDataSetFromExcelFile(new FileInfo(@"c:\SampleTree.xlsx")).Tables[0]; 

    var currentLevel = 0; 
    var nodeCount = 1; 
    var currentRow = 0; 

    inputTable.Columns.Add("Indent", typeof (int)); 
    inputTable.Columns.Add("Path", typeof (string)); 

    var rightStack = new List<FolderRow>(); 

    foreach (DataRow row in inputTable.Rows) 
     row["Indent"] = GetLevelPopulated(row); 

    foreach (DataRow row in inputTable.Rows) 
    { 
     if (row.GetValue("Indent", 0) == 0) 
      row["Tree L"] = 1;     

    } 

    while (true) 
    { 
     var row = GetRow(inputTable, currentRow); 
     if (row.Indent == 0) 
     { 
      currentRow++; 
      rightStack.Add(row); 
      continue; 
     } 

     // if the indent of this row is greater than the previous row ... 
     if (row.Indent > currentLevel) 
     { 
      currentLevel++; 
      nodeCount++; 
      row.Left = nodeCount; 
      // ... check the next row to see if it is further indented 
      currentRow = HandleNextRow(row, currentRow, rightStack, inputTable, ref currentLevel, ref nodeCount); 
     } else if (row.Indent == currentLevel) 
     { 
      nodeCount++; 
      row.Left = nodeCount; 
      currentRow = HandleNextRow(row, currentRow, rightStack, inputTable, ref currentLevel, ref nodeCount); 
     } else if (row.Indent < currentLevel) 
     { 
      currentLevel--; 
      nodeCount++; 
      row.Left = nodeCount; 
      currentRow = HandleNextRow(row, currentRow, rightStack, inputTable, ref currentLevel, ref nodeCount); 
     } 

     if (inputTable.Rows.Cast<DataRow>().Select(r => new FolderRow(r, -1)).All(r => r.RowComplete)) 
      break; 

    } 

} 

private int HandleNextRow(FolderRow row, int currentRow, List<FolderRow> rightStack, DataTable inputTable, ref int currentLevel, 
          ref int nodeCount) 
{ 
    var nextRow = GetRow(inputTable, currentRow + 1); 
    if (nextRow != null) 
    { 
     if (nextRow.Indent > row.Indent) 
     { 
      // ok the current row has a child so we will need to set the tree right of that, add to stack 
      rightStack.Add(row); 
     } 
     else if (nextRow.Indent == row.Indent) 
     { 
      nodeCount++; 
      row.Right = nodeCount; 
     } 
     else if (nextRow.Indent < row.Indent) 
     { 
      nodeCount++; 
      row.Right = nodeCount; 
      nodeCount++; 
      // here we need to get the most recently added row to rightStack, set the Right to the current nodeCount 
      var stackLast = rightStack.LastOrDefault(); 
      if (stackLast != null) 
      { 
       stackLast.Right = nodeCount; 
       rightStack.Remove(stackLast); 
      } 

      currentLevel--; 
     } 

     currentRow++; 

     if (rightStack.Count > 1) 
     { 
      // before we move on to the next row, we need to check if there is more than one row still in right stack and 
      // the new current row's ident is less than the current branch (not current leaf) 
      var newCurrentRow = GetRow(inputTable, currentRow); 
      var stackLast = rightStack.LastOrDefault(); 
      if (newCurrentRow.Indent == stackLast.Indent) 
      { 
       nodeCount++; 
       stackLast.Right = nodeCount; 
       rightStack.Remove(stackLast); 

      } 
     } 


    } 
    else 
    { 
     // reached the bottom 
     nodeCount++; 
     row.Right = nodeCount; 

     // loop through the remaining items in rightStack and set their right values 
     var stackLast = rightStack.LastOrDefault(); 
     while (stackLast != null) 
     { 
      nodeCount++; 
      stackLast.Right = nodeCount; 
      rightStack.Remove(stackLast); 
      stackLast = rightStack.LastOrDefault(); 
     } 
    } 
    return currentRow; 
} 

private FolderRow GetRow(DataTable inputTable, int rowCount) 
{ 
    if (rowCount >= inputTable.Rows.Count) 
     return null; 

    return rowCount < 0 ? null : new FolderRow(inputTable.Rows[rowCount],rowCount); 
} 

private int GetLevelPopulated(DataRow row) 
{ 
    var level = 0; 

    while (level < 14) 
    { 
     if (level == 0 && row["Root"] != DBNull.Value) 
      return level; 

     level++; 

     if (row["Level " + level] != DBNull.Value) 
      return level; 
    } 

    return -1; 
}