Упорядоченная вставка бинарного дерева

Question

У меня есть проблемы в этом коде ниже, это часть программы для упорядоченных двоичных деревьев. Проблема в том, что когда я вводю числа на входе, некоторые элементы просто теряются, и это происходит постоянно. Я посмотрел на код и не могу понять, почему это происходит. Вы можете помочь мне с этим? Спасибо.

void insert_ord(int number, struct treenode *currentNode){
   if(currentNode->flag == 0){
      currentNode->number = number;
      currentNode->flag = 1;                  
   }
   else{
      if(number <= currentNode->number){
         if(currentNode->left != NULL) insert_ord(number, currentNode->left);
         else {
            struct treenode *store = (struct treenode *)malloc(sizeof(struct treenode));
            currentNode->left = store;
            store->number = number;
            store->left = store->right = NULL;
            store->prev = currentNode;
         }
      }
      if(number > currentNode->number){
         if(currentNode->right != NULL) insert_ord(number, currentNode->right);
         else {
            struct treenode *store = (struct treenode *)malloc(sizeof(struct treenode));
            currentNode->right = store;
            store->number = number;
            store->left = store->right = NULL;
            store->prev = currentNode;
         }
      }
   }
}

Answer 1

Вы не устанавливаете store->flag для вновь вставленных узлов.Предположительно, он должен быть установлен на 1.

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

struct treenode *new_node(struct treenode *parent, int number)
{
    struct treenode *store = malloc(sizeof(struct treenode));

    if (store) {
        store->number = number;
        store->left = store->right = NULL;
        store->prev = parent;
        store->flag = 1;
    }

    return store;
}

Тогда ваш код вставки просто становится:

if (currentNode->left)
    insert_ord(number, currentNode->left);
else
    currentNode->left = new_node(currentNode, number);

(и аналогично для правого узла).

Answer 2

malloc возвращает неинициализированную память, и вы не инициализируете поле флага ваших неправильно расположенных структур.