Помогите вставить список значений в двоичное дерево ..?

Question

Ну, я был на это некоторое время ... пытаясь найти алгоритм для вставки моего списка случайных чисел в двоичное дерево.

Это то, что я получил до сих пор:

NodePtr и дерево являются указателями на узел

NodePtr CreateTree(FILE * fpData) 
{ 
    int in; 

    fscanf(fpData, "%i", &in); 
    Tree T = (NodePtr)malloc(sizeof(Node)); 
    T->Left = NULL; 
    T->Right = NULL; 
    T->value = in; 

    while((fscanf(fpData, "%i", &in)) != EOF) 
    { 
     InsertInTree(in, T); 
     printf("\n %p", T); 
    } 

    return T; 

} 


void InsertInTree(int value,Tree T) 
{ 
    if(T == NULL) 
    { 
     T->Left = (NodePtr)malloc(sizeof(Node)); 
     T->Left->Left = NULL; 
     T->Left->Right = NULL; 
     T->Left->value = value; 
     printf("\n %i ", value); 
     return; 
    } 
    if(T->Left == NULL) 
    { 
     InsertInNull(value, T->Left); 
    } 
    else if(T->Right == NULL) 
    { 
     InsertInNull(value, T->Right); 
    } 
    else 
    { 
     if(T->Left->Left == NULL || T->Left->Right == NULL) InsertInTree(value, T->Left); 
     else InsertInTree(value, T->Right); 
    } 
} 

Я потерял от того, что делать, если оба потомка конкретного узла не являются ноль. То, что я сделал здесь, работает для небольшого количества чисел (1,2,3,5,6), но если список больше, он становится неуравновешенным и неправильным.

Answer 1

Простая вставка в двоичное дерево и сохранение сбалансированного двоичного дерева - это разные проблемы. Я предлагаю вам начать с первой проблемы и просто сосредоточиться на сохранении свойств заказа в дереве. Это недалеко.

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

Answer 2

Должен ли он быть поисковым деревом? Я не вижу никаких условий if (value < T->Value).

И у вас есть InsertNull (не показан). Это не должно быть необходимым, 1 функции должно быть достаточно.

Для решения вашей основной проблемы, используйте параметр указатель на указатель или, более элегантный, всегда возвращает новое дерево:

//untested, no balancing 
Tree InsertValue(Tree t, int value) 
{ 
    if (t == null) 
     t = // create and return new node 
    else 
    { 
     if (value < t->Value) 
     t->Left = InsertValue(t->Left, value); 
     else 
     t->Right = InsertValue(t->Left, value);  
    } 
    return t; 
} 

И в CreateTree:

Tree t = InsertValue(null, in); 

Answer 3

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

0 
    1 2 
3 4 5 6 

Вот статья, которая объясняет далее:

http://www.cs.bu.edu/teaching/c/tree/breadth-first/