如何遍歷具有多個級別的樹來查找當前元素的上一個元素和下一個元素？

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。

我正在使用的真實例子是一個Category實體，它具有遞歸關聯，因爲它可以包含SubCategories。如果我處於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

我不太清楚我是否理解你的問題，所以提前道歉，如果是這種情況。

在我看來，你的索引在你的節點列表中，並且你知道它的級別，因此你只需要跳過視圖中具有更高級別的前一個節點或下一個節點（即它們是子節點），直到找到一個具有相同（因此也是兄弟）級別或更低級別或者耗盡節點的節點，在這種情況下，該級別沒有兄弟節點。