現在の要素の前後の要素を見つけるために、多くのレベルのツリーをトラバースする方法はありますか？

Question

サブリストを持つツリー内の任意の要素の前と次の要素を見つけるにはどうすればよいですか？

例

1. 
   1.1 AA
   1.1.1 AAA
   1.1.2 BBB
   1.1.3 CCC

1.2 DD

1.1.3 CCCの前と次のIDはどうやって取得できますか？私は与えられた瞬間にCCCのIDしか知りません。

私が実際に使っている例は、サブカテゴリを含むことができるため、それ自体に再帰的な関連付けを持つカテゴリエンティティです。私がレベル3のサブカテゴリであれば、前と次のカテゴリのIDを知りたいと思います。

私のビュー（ウェブページ）には、すべてのカテゴリのリストがあります。私がカテゴリをクリックすると、私はそれが自分のIDだと知っているだけですが、前と次のIDを取得したいと思います。

私は、次の方法を使用しましたが、彼らはいけない仕事するときがあり、より多くのレベル：

private void GetNextCategoryID(PagedData<ShowQuestionViewModel> questionsPaged) 
    { 

     List<Category> categories = db.Category.Where(y => y.parrent_id == null).ToList(); 

     categories.Sort(new CompareCategory()); 

     List<ShowCategoriesViewModel> scvm = Mapper.Map<List<Category>, List<ShowCategoriesViewModel>>(categories); 

     for (int i = 0; i < scvm.Count; i++) 
     { 
      if (scvm[i].category_id == questionsPaged.CategoryID) 
      { 
       if (scvm[i].SubCategories != null && scvm[i].SubCategories.Count > 0) 
       {       
         questionsPaged.NextCategory_ID = scvm[i].SubCategories.First().category_id; 
         break;     
       } 

       try 
       { 
        questionsPaged.NextCategory_ID = scvm[i + 1].category_id; 
        break; 
       } 
       catch (ArgumentOutOfRangeException ex) 
       { 
        questionsPaged.NextCategory_ID = 0; 
        break; 
       } 

      } 
      else if (scvm[i].SubCategories != null) 
      { 
       for (int q = 0; q < scvm[i].SubCategories.Count; q++) 
       { 
        if (scvm[i].SubCategories[q].category_id == questionsPaged.CategoryID) 
        { 
         try 
         { 
          questionsPaged.NextCategory_ID = scvm[i].SubCategories[q + 1].category_id; 
          break; 
         } 
         catch (ArgumentOutOfRangeException ex) 
         { 
          // Betyder at vi er kommet til den sidste kategori i rækken 
          // og at den endnu ikke har fundet en match 

          try 
          { 
           questionsPaged.NextCategory_ID = scvm[i + 1].category_id; 
           break; 

          } 
          catch (ArgumentOutOfRangeException eq) 
          { 
           // Dette betyder at den valgte underkategori kategori er den sidste i spørgeskemaet 
           questionsPaged.NextCategory_ID = 0; 
           break; 
          } 

         } 
        } 
       } 
      } 

     } 
    } 

と

private void GetPreviousCategoryID(PagedData<ShowQuestionViewModel> questionsPaged) 
    { 
     List<Category> categories = db.Category.Where(y => y.parrent_id == null).ToList(); 
     categories.Sort(new CompareCategory()); 
     List<ShowCategoriesViewModel> scvm = Mapper.Map<List<Category>, List<ShowCategoriesViewModel>>(categories); 

     for (int i = scvm.Count - 1; i >= 0; i--) 
     { 
      if (scvm[i].category_id == questionsPaged.CategoryID) 
      { 
       try 
       { 
        if (scvm[i - 1].SubCategories != null) 
        { 
         int subcount = scvm[i - 1].SubCategories.Count; 
         questionsPaged.PreviousCategory_ID = scvm[i - 1].SubCategories[subcount - 1].category_id; 
         break; 
        } 
        else 
        { 
         questionsPaged.PreviousCategory_ID = scvm[i - 1].category_id; 
        } 

       } 
       catch (ArgumentOutOfRangeException ex) 
       { 
        questionsPaged.CategoryID = scvm[i].category_id; 
        break; 
       } 
      } 

      else if (scvm[i].SubCategories != null) 
      { 
       for (int x = 0; x < scvm[i].SubCategories.Count; x++) 
       { 
        try 
        { 
         if (scvm[i].SubCategories[x].category_id == questionsPaged.CategoryID) 
         { 

          questionsPaged.PreviousCategory_ID = scvm[i].SubCategories[x - 1].category_id; 
          break; 
         } 
        } 
        catch (ArgumentOutOfRangeException qx) 
        { 
         questionsPaged.PreviousCategory_ID = scvm[i].category_id; 
        } 
       } 
      } 
     } 
    } 

ありがとう！

Answer 1

理論上は、現在のカテゴリのIDを使用して、そのIDを持つノードを見つけるまでツリーを走査します。ここでは後継者を見つけるために（私は後継者が右にあると仮定しています）、ツリーの上に戻る必要があります。親が正しい子を持っている場合は、その子をルートとするサブツリーの一番左側のノードを見つけます。この推論は親の親に再帰的に推論されます。

前任者を見つけるには、上記の手順を実行しますが、親に左の子があるかどうかを確認し、そのサブツリーの最も近いノードを見つけるか、親の親に再帰的に適用します。

// finds the successor of node 
procedure successor(node) 
{ 
    // assuming you have the node for the id that you know. 
    // also I'm assuming you have some way to find its position 
    // in the child list 

    // if the parent has a child to the right 
    if(parent(node).children[position(node) + 1] != null) 
    { 
     return findLeftmost(parent(node).children[position(node) + 1]); 
     // find the leftmost node in the subtree rooted 
     // at the next sibling to the right 
    } 
    else 
    { 
     return successor(parent(node)); 
     // move up the tree 
    } 
} 


// finds the leftmost leaf node of the (sub)tree rooted at node 
procedure findLeftmost(node) 
{ 
    if(node.children.length == 0) // leaf node 
    { 
     return node; 
    } 
    else 
    { 
     return findLeftmost(node.children[0]); 
     // here I'm assuming the children are in the list from left to right, 
     // such that children[0] is the leftmost child. 
    } 
} 

Answer 2

この場合、私はあなたの質問をあらかじめご理解いただいております。

ノードのリスト内にインデックスがあり、そのレベルを知っているので、より大きなレベルのビューの前または次のノードをスキップするだけです（つまり、子ノード）を使用して、同等の（したがって兄弟の）レベル、またはより低いレベルのノードを見つけたり、ノードを使い果たしたりします。その場合、そのレベルには兄弟はありません。