рассчитать внутреннюю длину пути BST только из предварительного или пост-заказа обхода - PullRequest
Новая
       19

рассчитать внутреннюю длину пути BST только из предварительного или пост-заказа обхода

3 голосов
/ 23 февраля 2011

Здравствуйте, сообщество StackOverflow!

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

Ну, любая мысль ценится и спасибо.

Ответы [ 3 ]

0 голосов
/ 23 февраля 2011

На странице http://geeksforgeeks.org/?p=6633 есть страница, на которой обсуждается построение дерева по его предварительному заказу и обходам по порядку.Здесь, поскольку ваше дерево является деревом поиска, вы имеете неявный обход по порядку (используя порядок сортировки ключей).Вы можете использовать рекурсивный алгоритм, такой как алгоритм на этом сайте, чтобы вычислить уровень каждого узла дерева (без необходимости строить дерево), а затем сложить уровни вместе, чтобы получить длину внутреннего пути.Этот алгоритм может быть не самым эффективным, поскольку он выполняет поиск по обходу, чтобы найти правильного дочернего элемента каждого узла, но он должен работать.Это мое лучшее предположение о том, как сделать однопроходный алгоритм (при условии, что все ключи различны): 

int internal_path_length(key_iter& cur_node, key_iter end, int level, key max_key) {
  if (cur_node == end) return 0;
  key cur_key = *cur_node;
  if (cur_key > max_key) return 0;
  ++cur_node;
  int len1 = internal_path_length(cur_node, end, level + 1, cur_key);
  int len2 = internal_path_length(cur_node, end, level + 1, max_key);
  return len1 + len2 + level;
}

Начать с: 

key_iter i = preorder.begin();
internal_path_length(i, preorder.end(), 0, mk);

, где mk больше, чеммаксимально возможный ключ в вашем дереве.

0 голосов
/ 23 февраля 2011

Поскольку это BST, мы неявно имеем обход дерева (отсортированный список элементов).

Мы можем создать уникальное дерево только из предварительного или пост-заказа обхода Pre будет [R, список элементов меньше R, список элементов больше R] Запись будет [список элементов меньше R, список элементов больше R, R]

Псевдокод будет выглядеть следующим образом. 

findIPLPreOrder(poArray,startIndex,endIndex, height) {
     if(startIndex==endIndex){
          retrn height;
     }
     m=findIndexOfEndofLeftSubTree(poArray,start,end);
     return findIPLPreOrder(poArray,start+1,m,height + 1) + findIPLPreOrder(poArray,m+1,end,height + 1);     
}

findIndexOfEndofLeftSubTree(poArray,start,end){
  R=poArray[start]
  for(i=start+1;i<=end;i++){
     if(R < poArray[i]){
         return i-1;
       }
  }
}
0 голосов
/ 23 февраля 2011

Если я понимаю вашу проблему, это может быть невозможно. Рассмотрим два дерева 

   A         A
  / \        |
 B   C       B
             |
             C

Они имеют одинаковый обход по предварительному заказу (ABC), но разную длину внутреннего пути (2 и 3).

...