Рассчитать максимальный размер стека для обхода дерева

Question

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

• Создание пустого стека stack и pu sh root узла в стеке.
• Выполните следующие действия, пока stack не пусто.
  • Получите предмет из stack и распечатайте его. Необязательно: если искусственный конечный узел, продолжить
  • Необязательно: Pu sh искусственный узел node_end до stack
  • Pu sh все дочерние элементы справа налево до stack

Дополнительная часть предназначена для случая использования, когда я печатаю документ XML, который хранится в виде древовидной структуры. Посещение узла X печатает начальный тег, посещение искусственного узла X_end печатает соответствующий конечный тег.

Рисование здесь довольно грубое, поэтому я даю дерево в коде C ++.

struct Node {
    int id; // root is 0
    std::vector<int> children; // index in the vector
}

std::array<Node, 15> tree{};

// sets all the ids, in total we have 15 nodes
for (int i = 0; i < 15; ++i)
    tree[i].id = i;

// now all the children, hope one can see the tree structure
tree[0].children.push_back(1);
tree[0].children.push_back(6);
tree[1].children.push_back(2);
tree[1].children.push_back(3);
// 2 is a leaf
tree[3].children.push_back(4);
tree[3].children.push_back(5);
// 4 is a leaf
// 5 is a leaf
tree[6].children.push_back(7);
tree[6].children.push_back(9);
tree[6].children.push_back(12);
tree[7].children.push_back(8);
// 8 is a leaf
tree[9].children.push_back(10);
tree[9].children.push_back(11);
// 10 is a leaf
// 11 is a leaf
tree[12].children.push_back(13);
tree[12].children.push_back(13);
// 13 is a leaf
// 14 is a leaf

Теперь, выполнение алгоритма, описанного выше, дает следующие стеки (один с искусственными конечными узлами и один без):

current_node | stack (simple version)
---------------------------------
      -      | 0
      0      | 6,1
      1      | 6,3,2
      2      | 6,3
      3      | 6,5,4
      4      | 6,5
      5      | 6
      6      | 12,9,7
      7      | 12,9,8
      8      | 12,9
      9      | 12,11,10
      10     | 12,11
      11     | 12
      12     | 14,13
      13     | 14
      14     | -

И второй:

current_node | stack (with end nodes)
---------------------------------
      -      | 0
      0      | 0e,6,1
      1      | 0e,6,1e,3,2
      2      | 0e,6,1e,3,2e
      2      | 0e,6,1e,3
      3      | 0e,6,1e,3e,5,4
      4      | 0e,6,1e,3e,5,4e
      4      | 0e,6,1e,3e,5
      5      | 0e,6,1e,3e,5e
      5      | 0e,6,1e,3e
      3      | 0e,6,1e
      1      | 0e,6
      6      | 0e,6e,12,9,7
      7      | 0e,6e,12,9,7e,8
      8      | 0e,6e,12,9,7e,8e
      8      | 0e,6e,12,9,7e
      7      | 0e,6e,12,9
      9      | 0e,6e,12,9e,11,10
      10     | 0e,6e,12,9e,11,10e
      10     | 0e,6e,12,9e,11
      11     | 0e,6e,12,9e,11e
      11     | 0e,6e,12,9e
      9      | 0e,6e,12
      12     | 0e,6e,12e,14,13
      13     | 0e,6e,12e,14,13e
      13     | 0e,6e,12e,14
      14     | 0e,6e,12e,14e
      14     | 0e,6e,12e
      12     | 0e,6e
      6      | 0e
      0      | -

Я действительно Надеюсь, я не сделал опечатку. Если что-то выглядит не так, пожалуйста, дайте мне знать.

Теперь на мой вопрос: в целях оптимизации было бы неплохо заранее узнать максимальный размер стека. Я нашел следующие формулы для расчета необходимого размера для одного узла.

Простая версия:

int getRequiredStackSize(Node node)
{
    int sum = 0;
    sum += node.children.size();
    sum += getNumOfRightSiblings(node);
    for (Node parent = getParent(Node); parent != NULL; parent = getParent(parent))
        sum += getNumOfRightSiblings(parent);
    return sum;
}

Общий максимальный размер стека является максимальным для всех узлов. Может быть, это можно сделать с меньшим количеством вычислений?

А для второго случая:

int getRequiredStackSize(Node node)
{
    int sum = 1; // the node's own artifical end node
    sum += node.children.size();
    sum += getNumOfRightSiblings(node);
    for (Node parent = getParent(Node); parent != NULL; parent = getParent(parent))
        sum += (1 + getNumOfRightSiblings(parent)); // the parents artifical end node as well
    return sum;
}

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

Первый вопрос: можно ли как-то оптимизировать эти формулы?

Второй вопрос: Как мне эффективно рассчитать максимум? Примечание. Я сам создаю дерево, поэтому могу хранить счетчики и т. Д. c.