Что такое псевдокод для этого двоичного дерева

Question

В принципе, я должен предоставить псевдокод для этого. В настоящее время у меня есть

dictionary = {} если node.left == нет и node.right == нет Визит (узел) словарь [узел] = 1

Это только конечные узлы. Как получить размер для каждого узла (родительского и root)?

Answer 1

Вы можете сделать обход после заказа , чтобы найти размер каждого узла.

Идея состоит в том, чтобы сначала обрабатывать как левое, так и правое деревья. Затем, после того как они обработаны - вы можете использовать эти данные для обработки текущего узла.

Это должно выглядеть примерно так:

count = 0
if (node.left != none)
  count += visit(node.left)
if (node.right != none)
  count += visit(node.right)
// self is included.
count += 1 
// update the node
node.size = count
return count

Словарь для посещенных узлов не нужен, так как это дерево , оно гарантирует конец.

---

В качестве примечания: атрибут size каждого узла является важным. Он в основном обновляет ваше дерево до Дерево статистики заказов

Answer 2

хорошо, концепция заключается в том, что каждый узел будет знать свой размер поддерева, сначала зная размер поддерева всего своего дочернего элемента, который здесь максимум два дочерних, так как это двоичное дерево, поэтому, как только он узнает размер поддерева всех дочерних элементов, он может затем сложите их все и, по крайней мере, добавьте 1 к его результату, и затем его родительский узел сделает то же самое и так далее до узла root. если мы думаем о листовом узле, у него нет дочернего узла, поэтому размер поддерева результата будет только 1, в который он будет включен.

Если эта идея ясна, легко написать код, который при обходе мы сначала знать размер поддерева дочерних узлов текущего узла, затем добавить 1 в него, в случае конечного узла он будет иметь размер поддерева только 1, ниже псевдокод функции перемещения, который находит размер поддерева каждого узла и сохраняет их в словаре sizeDictionary и посещаемый словарь / массив, имеющий большую область видимости, использовались для отслеживания посещенных узлов.

traverse(Tree curNode, dictionary subTreeSizeDictionary)
   visited[curNode] = true
   subtreeSizeDictionary[curNode] = 0
   for child of curNode
       if(notVisited[child])
           traverse(child , sizeDictionary)
           subtreeSizeDictionary[curNode] += subtreeSizeDictionary[child]
   subtreeSizeDictionary[curNode] += 1;

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