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

Question

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

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

NodePtr и Tree - указатели на узел

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

Это должно быть дерево поиска?Я не вижу условий 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 2

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

   0
  1 2
3 4 5 6

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

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

Answer 3

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

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