Подсчет правых потомков узла в двоичном дереве представления упорядоченного дерева
Мне нужна помощь с этой проблемой.
Пример дерева:
A
/
B-C-D
/
E-F-G
У меня есть двоичное дерево, которое представляет упорядоченное дерево, и мне нужно подсчитать количество дочерних элементов для каждого узла и поместить это число в соответствующий узел.
Есть три ребенка (B, C, D) для A и три (E, F, G) для D. Ноль детей для B, C, E, F, G.
Каждый узел может иметь только двоих детей в физическом (двоичном) представлении. Если у узла есть левый дочерний элемент, то каждый правый дочерний элемент этого узла также считается дочерним. В моем примере левым ребенком является B. B имеет одного правого ребенка C. C имеет одного правого ребенка D. Таким образом, B, C и D являются детьми для A в этом задании.
В конце программы данные в узлах должны быть A (3), B (0), C (0), D (3), E (0), F (0), G (0).
Решение
То, что вы описываете, выглядит как дерево произвольной арности, представленное в шаблоне правого брата левого ребенка. Каждый узел содержит указатель на самого левого дочернего элемента, а также на его правого родного брата.
Найти количество детей в данном узле не должно быть слишком сложно. Просто возьмите самого левого ребенка, а затем посчитайте, сколько раз вы можете перейти к его правому брату. В псевдокоде это будет выглядеть примерно так:
def Node {
Node* left_child
Node* right_sibling
}
numChildren(Node n) {
num = 0
next = n.left_child
while (next exists)
num = num + 1
next = next.right_sibling
return num
}
Другие решения
Других решений пока нет …