Печать в порядке возрастания (сортировка) из деревьев AVL - PullRequest
Новая
       5

Печать в порядке возрастания (сортировка) из деревьев AVL

3 голосов
/ 04 марта 2012

Мне нужно определить основную функцию, которая читает целые числа и печатает их обратно в порядке возрастания. 

    For example, if the input contains

       12
       4
       19
       6

   the program should output

       4
       6
       12
       19

Однако мне нужно использовать деревья для этого.В моем распоряжении две функции insertavl и deleteavl.Их определения таковы ... http://ideone.com/8dwlU в основном, когда вызывается deleteavl, он удаляет узел и соответствующим образом перебалансирует дерево ... Если интересующие их структуры находятся в: http://ideone.com/QjlGe.

I 'мы уже получили это: 

int main (void) {
   int number;
   struct node *t = NULL;
   while (1 == scanf("%d",&number)) {     
          t = insertavl(t, number);              
   }
   while (t != NULL){
      printf("%d\n",t->data);
      t = deleteavl(t, t->data);    
   }    
}

Но это не печатает их в порядке возрастания.Любые предложения будут полезны?заранее спасибо!

1 Ответ

3 голосов
/ 04 марта 2012

Подсказка: обход в порядке на BST равен итерации элементов в порядке возрастания.

Поскольку дерево AVL является конкретной реализацией BST, оно также применимо и здесь.

РЕДАКТИРОВАТЬ: Пояснение - почему это свойство обхода в порядке по BST является правильным?

В trvaersal по порядку вы получаете доступ к [print] каждому узлу после доступа ко всем узлам в левом поддереве. Поскольку в BST корень больше, чем все узлы в левом поддереве, это то, что мы хотели.

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

(*) Примечание: это не формальное доказательство, а интуитивное объяснение, почему оно верно.

...