Двоичное дерево, в котором значение каждого узла содержит сумму дочерних узлов

Question

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

Answer 1

Дайте каждому узлу прикрепленное значение.Когда вы создаете дерево, значение листа устанавливается;создайте внутренние узлы так, чтобы они имели значение leaf1.value + leaf2.value.

. Если вы можете изменить значения конечных узлов, то операция должна пойти «назад» по дереву, обновляя значения сумм.

Это будет намного проще, если вы включите обратные ссылки в узлы или внедрите дерево в виде " потокового дерева ".

Answer 2

Как заметил Чарли, вы можете просто хранить сумму соответствующих размеров поддерева в каждом внутреннем узле и иметь листы, предоставляющие постоянные значения при построении (или всегда неявно использовать 1, если вас интересует только количество листьев в дереве).

Это обычно называется расширенным деревом поиска.

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

1. тип данных М; в вашем примере целые числа
2. бинарная операция «op» для объединения элементов, с M op M -> M; в вашем примере общий оператор «плюс»

Таким образом, помимо размеров поддерева, вы также можете выразить такие вещи, как:

• приоритетов (с помощью операторов "min" или "max"), для эффективных запросов по приоритетам min / max;
• крайние правые элементы в поддереве (т. Е. Оператор "op", который просто возвращает свой второй аргумент), при условии, что элементы, которые вы храните в дереве, упорядочены каким-либо образом. Обратите внимание, что это позволяет нам просматривать даже обычные деревья поиска (иначе словари - «сохранить это, получить этот ключ») как дополненные деревья с соответствующим моноидом.

(Эта концепция скорее напоминает кучи, или, более точно, трэпы, которые хранят случайные приоритеты с внутренними узлами для вероятностной балансировки. Она также довольно часто описывается в контексте Finger Trees, хотя это не одно и то же.)

Если вы также предоставляете нейтральный элемент для своего моноида, вы можете затем пройти по такому дереву поиска, дополненному моноидами, чтобы получить определенные элементы (например, «найдите меня 5-й лист» для вашего примера размера; «дайте мне лист» с наивысшим приоритетом ").

Хм, в любом случае. Возможно, там немного увлеклись ... Мне просто показалось, что эта тема довольно интересная. :)

Answer 3

Вот решение, которое может вам помочь: (ссылка объясняет это древовидными диаграммами)

Преобразование произвольного двоичного дерева в дерево, которое содержит свойство Children Sum

/* This function changes a tree to to hold children sum
   property */
void convertTree(struct node* node)
{
  int left_data = 0,  right_data = 0, diff;

  /* If tree is empty or it's a leaf node then
     return true */
  if(node == NULL ||
     (node->left == NULL && node->right == NULL))
    return;
  else
  {
    /* convert left and right subtrees  */
    convertTree(node->left);
    convertTree(node->right);

    /* If left child is not present ten 0 is used
       as data of left child */
    if(node->left != NULL)
      left_data = node->left->data;

    /* If right child is not present ten 0 is used
      as data of right child */
    if(node->right != NULL)
      right_data = node->right->data;

    /* get the diff of node's data and children sum */
    diff = left_data + right_data - node->data;

    /* If node's data is smaller then increment node's data
       by diff */
    if(diff > 0)
       node->data = node->data + diff;

    /* THIS IS TRICKY --> If node's data is greater then increment left
      subtree  by diff */
    if(diff < 0)
      increment(node->left, -diff);
  }
}

См. Ссылку , чтобы увидеть полное решение и объяснение!

Answer 4

Вот код для задачи суммы. Это работает, я проверил это.

int sum_of_left_n_right_nodes_4m_root(tree* local_tree){

   int left_sum = 0;
   int right_sum = 0;
   if(NULL ==local_tree){
       return 0;
   }   
   if((NULL == local_tree->left)&&(NULL == local_tree->right)){
       return 0;
   }   
   sum_of_left_n_right_nodes(local_tree->left);
   sum_of_left_n_right_nodes(local_tree->right);
   if(NULL != local_tree->left)
       left_sum = local_tree->left->data + 
                  local_tree->left->sum;

   if(NULL != local_tree->right)
       right_sum = local_tree->right->data + \ 
                   local_tree->right->sum;

       local_tree->sum= right_sum + left_sum;


}

Answer 5

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