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

Question

Как мне найти предыдущий и следующий элемент любого данного элемента в дереве, которое имеет подсписки?

Пример

1. A
   1,1 АА
   1.1.1 ААА
   1.1.2 ВВВ
   1.1.3 CCC

1,2 ДД

Как мне получить предыдущий и следующий идентификаторы 1.1.3 CCC? Я знаю только идентификатор CCC в данный момент.

Реальным примером, с которым я работаю, является объект Category, который имеет рекурсивную ассоциацию с самим собой, поскольку он может содержать подкатегории. Если я нахожусь в подкатегории уровня 3, я хотел бы знать идентификатор предыдущей и следующей категории.

В моем представлении (веб-странице) у меня есть список всех категорий. Когда я нажимаю на категорию, я знаю только ее собственный идентификатор, но хотел бы также получить предыдущий и следующий идентификатор.

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

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

Я не совсем уверен, что понял ваш вопрос, поэтому заранее извиняюсь, если это так.

Мне кажется, что у вас есть индекс в вашем списке узла, и вы знаете его уровень, и поэтому вам просто нужно пропустить предыдущие или следующие узлы в представлении, которые имеют более высокий уровень (то есть они дочерние узлы), пока вы не найдете один с равным (и, следовательно, одноуровневым) уровнем, или с более низким уровнем, или у вас закончатся узлы, и в этом случае на этом уровне нет родного брата.

Answer 2

Теоретически, то, что вы должны сделать, это: с идентификатором текущей категории, перемещаться по дереву, пока не найдете узел с этим идентификатором. Оказавшись здесь, чтобы найти преемника (я предполагаю, что преемник находится справа), вы должны вернуться вверх по дереву: если у родителя есть правый дочерний элемент, найдите крайний левый узел поддерева с корнем в этом дочернем элементе, в противном случае примените это рассуждение рекурсивно для родителя родителя и т. д.

Чтобы найти предшественника, просто выполните описанные выше шаги, но проверьте, есть ли у родителя левый потомок и найдите самый правый узел этого поддерева, или рекурсивно примените к родителю родителя.

// 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.
    }
}