Вставка двоичного дерева сортировка по C

Question

Эй, может кто-нибудь объяснить, как сортировать двоичное дерево, используя сортировку вставки на языке C, где сложность времени является проблемой. Я просто учился кодировать. Спасибо вам, ребята!

Answer 1

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

• http://en.wikipedia.org/wiki/Tree_traversal

• http://en.wikipedia.org/wiki/Binary_tree

Также обратите внимание на: http://nova.umuc.edu/~jarc/idsv/lesson1.html

Answer 2

Стоит отметить, что есть определенная терминология, чтобы использовать здесь. A двоичное дерево - это структура данных, в которой каждый узел имеет не более двух детей. Для упорядочения узлов в двоичном дереве нет соглашений.

бинарного дерево поиска является бинарным деревом таким образом, что для данного узла N все узлы в левом поддереве N считаются «меньше чем» N и все узлы в правом поддереве N считается «больше «N. Вы также можете позволить узлам считаться« равными »N в дереве, если вы последовательно определяете их для размещения в левом поддереве или в правом поддереве.

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

Answer 3

#include <stdio.h> 
#include <malloc.h> 
#define FIN "algsort.in" 
#define FOUT "algsort.out" 

struct Node { 
    int val; 
    struct Node *left; 
    struct Node *right; 
}; 

typedef struct Node node; 

void insert(node **bt, node *Node) { 

if(!(*bt)) { 

    *bt = Node; 

} else { 

     if(Node->val < (*bt)->val) 

      insert(&((*bt)->left), Node); 

     else 

      insert(&((*bt)->right), Node); 
} 
} 

void printout(struct Node *node) { 

    if(node->left) printout(node->left); 

    printf("%d ", node->val); 

    if(node->right) printout(node->right); 
} 

void postorder(struct Node *node) { 

     if(node->left) printout(node->left); 

     if(node->right) printout(node->right); 

     printf("%d ", node->val); 
} 

int main() { 

    int i, n, elem;  

    node *curr; 

    freopen(FIN, "r", stdin); 

    freopen(FOUT, "w", stdout); 

    node *bt = NULL; 

    scanf("%d", &n); 

    for(i = 0; i < n; ++i) { 

     scanf("%d", &elem); 

     curr = malloc(sizeof(struct Node)); 

     curr->val = elem; 

     curr->left = NULL; 

     curr->right = NULL; 

     insert(&bt, curr); 

    } 

    printout(bt); 

    return(0); 
    } 

Допустим, что algsort.in содержит следующий массив целых чисел:

algsort.int -> 9,8,7,6,5,4,3,2,0,1, - 1;

algsort.out -> -1,0,1,2,3,4,5,6,7,8,9