Почему мой корневой указатель BST изменяется по неизвестной причине?

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

Первые Шаги

Хорошо, во-первых, пара действительно важных вещей о вашем коде :

• Скобки. Во имя любви к Богу, используйте фигурные скобки на вашем синтаксисе if..else. Смотрите ваш BstInsert ниже.

  void BstInsert( Bst *root, int key )
  {
      if( !root->key )
          root->key = key;
      else if ( key <= root->key)
          if( root-> left )
              BstInsert( root->left, key );
          else
              root->left = NewNode( key );
      else
          if ( root -> right )
              BstInsert( root->right, key);
          else
              root->right = NewNode( key );
  }
  

• Когда вы пишете функции для обхода вашего BST на основе того, является ли один ключ меньше или больше другого, прежде всего вы должны быть последовательны. Использование A < B в одном месте и A <= B может быть катастрофическим. Это также помогает читабельности, если вы выбираете сторону, чтобы вставить целевой узел (тот, который вы ищете) и всегда делать сравнения таким же образом вокруг.

Технические Проблемы

Выделение памяти может завершиться ошибкой. Когда это происходит, различные методы распределения(malloc, calloc, и т.д.) вернутся NULL. Вы должны проверить это. Обратите внимание, что calloc инициализирует память до нуля (очищает ее), в то время как malloc этого не делает. Для такого рода ситуаций (написание базовой структуры данных в качестве практического упражнения) я хотел бы обернуть свои методы распределения следующим образом:

void *ecalloc(size_t n, size_t s) {
    void *o = calloc(n, s);
    if (NULL == o) {
    fprintf(stderr, "Memory allocation failed!\n");
    exit(EXIT_FAILURE);
    }
    return o;
}

Это означает, что а) мне не нужно печатать надоедливые if (NULL == thing) проверки распределения все время и Б) что программа завершит работу после печати сообщения, если распределение не удастся. Последнее не всегда может быть желательным (ну, по крайней мере, часть ухода, хотя у вас нет тонны вариантов если у вас закончилась память), но будет более чем достаточно в этом случае.

Проблемы Проектирования

Предупреждение: термин Design используется здесь свободно.

Предположим, мы хотим, чтобы BST хранил некоторые целые числа. Вы решаете, что узел в вашем BST будет хранить целое число и два указателя (на узлы). Это прекрасно. Однако это означает, что вы не можете разумно использовать ключ в качестве значения sentinel, чтобы определить, используется ли узел. К счастью, нам это не нужно. Вместо использования узел как корень когда дерево пусто, просто используйте указатель на узел. Если узла нет, то указатель равен NULL. Это связано с проблемой, которую вы столкнулись с вашим методом удаления. BST-это дерево, состоящее из связанных узлов, верно? Или так оно и есть? Вы также можете думать о нем как о дереве, где каждый узел на самом деле является поддеревом. Это делает его хорошо подходящим для рекурсии, поэтому давайте попробуем выразить вещи элегантно, используя рекурсию, когда мы можем.

Теперь у нас есть несколько опции.

1. мы могли бы сделать неизменяемую bst (все ваши модифицирующие вызовы будут выглядеть как b = bst_insert(b, 10), потому что bst_insert и так далее будут возвращать новую модифицированную копию дерева, не изменяя старую).
Мы могли бы пойти дальше по линии void bst_insert(bst **b, int key), называемой bst_insert(&b, 10), где мы используем дополнительный уровень косвенности для изменения нашего дерева, передавая указатель на указатель на узел.
2. или мы могли бы пойти на что-то среднее между двумя предыдущими вариантами, где мы have bst *b(bst *b, int key), который изменяет то, что он может из *b (ключ и дочерние указатели), и присваивает обратно то, что он не может. это позволяет избежать дополнительной косвенности (которая немного уродлива), но немного непоследовательна в этом, если вы используете комбинацию назначения возвращаемых значений функции и побочных эффектов функции для достижения своей цели.

Я выбрал для работы второй вариант.

Отладка

Предположим, что вы вставляете a 1 в свой BST. Возможно, вы удалите a 2. Как ты знаете, что это сработало? Не было бы проще отлаживать, если бы вы могли видеть, что делает ваш BST?

Я предлагаю (особенно когда вы начинаете писать базовые структуры данных, когда сложная среда отладки, такая как gdb, может быть а) избыточной и Б) информационной перегрузкой), чтобы вы кодировали способы вывода состояния вашей структуры данных очень рано.

Кроме того, если вы работаете с *nix, valgrind (произносится как "вал усмехнулся") - ваш лучший друг. Это проверка памяти, и вы можете используйте его, чтобы убедиться, что вы всегда освобождаете выделенную память (как только вы закончите с ней, конечно), и искать другие ошибки памяти, такие как выход за пределы. Научитесь им пользоваться (на самом деле это довольно просто). Если вы на Windows, есть Purify, хотя я не думаю, что это бесплатно... во всяком случае, я уверен, что кто-то более знакомый с этой средой может что-то порекомендовать.

Предупреждения компилятора-тоже замечательная вещь. Включите их и относитесь к ним как к ошибкам. При использовании gcc я склонен использовать -W -Wall -ansi -pedantic. В связи с этим, существует -g, чтобы генерировать информацию для использования GDB.

Написание BST

Я собирался просмотреть ваш код и препарировать его, но в итоге я сам написал похожий стиль BST, а затем перешел к моему коду, объясняя каждую часть. Я выбрал подход с двумя файлами. У нас есть bst.c и еще bst.h.

Bst.h

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

#ifndef BST_H_
#define BST_H_

Вот typedef, который позволяет нам избегать ввода struct bstnode все время и скрывает содержимое типа struct bstnode от любого, кто просто использует ваш BST.

typedef struct bstnode bst;

extern говорит, что эти функции реализованы где-то еще, в основном.

extern bst *bst_new(int k);
extern void bst_insert(bst **b, int k);
extern bst *bst_search(bst  *b, int k);
extern void bst_remove(bst **b, int k);
extern void bst_delete(bst **b);
extern void bst_newick(const bst  *b);

#endif /* BST_H_ */

Bst.c

#include <stdlib.h>
#include <stdio.h>
#include "bst.h"

Вот полный struct bstnode. У нас есть доступ к bst typedef, потому что мы включили bst.h.

struct bstnode {
    int key;
    bst *left, *right;
};

В этом контексте статика означает, что эти функции имеют область видимости файла.

static void bst_swap_keys(bst *a, bst *b);
static void bst_newick_rec(const bst *b);
static void *ecalloc(size_t n, size_t s); /* Here for compactness - normally I would put it in a utility file somewhere else. */

Теперь мы могли бы с таким же успехом включить bst.h в другой файл, main.c, и поместить туда наш основной метод, но для компактности я этого не сделал.

int main(void)
{
    bst* b = bst_new(5);

    bst_newick(b);
    bst_insert(&b, 7);

    bst_newick(b);
    bst_insert(&b, 3);

    bst_insert(&b, 8);
    bst_insert(&b, 2);
    bst_insert(&b, 1);
    bst_newick(b);

    bst_remove(&b, 7);
    bst_newick(b);

    bst_delete(&b);
    printf("%p\n", (void*) b);

    return EXIT_SUCCESS;
}

Недостатком этого способа является то, что вам нужен ключ, прежде чем вы сможете сделать ваш первый допустимый узел. Мы могли бы просто списать bst_new и сделать распределение в bst_insert вместо этого, но я хотел сохранить new/delete парадигма здесь.

bst *bst_new(int k) {
bst *b = ecalloc(1, sizeof *b);
b->key = k;
return b;

}

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

void bst_insert(bst **b, int k) {
    if (NULL == b) { /* I wanted to avoid additional levels of nesting so I did this instead of NULL != b */
    return;
    }

    if (NULL == *b) {
    *b = bst_new(k);
    } else if ((*b)->key > k) {
        bst_insert(&(*b)->left, k);
    } else if ((*b)->key < k) {
    bst_insert(&(*b)->right, k);
    }
}

Найдите узел, если это возможно. Я мог бы сделать b const, чтобы показать, что мы не изменяем его, но тогда мне пришлось бы также изменить тип возвращаемого значения, а затем отбросить его, чтобы изменить все, что я искал, что немного непослушно.

bst *bst_search(bst *b, int k) {
    if (NULL == b) {
    return NULL;
    } else if (b->key == k) {
    return b;
    } else if (b->key > k) {
    return bst_search(b->left, k);
    } else {
    return bst_search(b->right, k);
    }
}

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

bst *bst_min(bst *b) {
    if (NULL != b && NULL != b->left) {
    return bst_min(b->left);
    } else {
    return b;
    }
}

Обратите внимание, что мы меняем местами ключи целевого узла (удаляемого) и тот, который должен заменить его, а не менять местами сами узлы, а затем рекурсивно удалить целевое значение снова. Если бы ключи были строками или чем-то еще, выделенным в куче, вам также нужно было бы освободить ключ непосредственно перед освобождением узла.

void bst_remove(bst **b, int k) {
    bst *temp;
    if (NULL == b || NULL == *b) { /* Doing it like this avoids extra indentation, which is harder to read*/
    return;
    }
    temp = *b;

    if ((*b)->key > k) {
    bst_remove(&(*b)->left, k);
    } else if ((*b)->key < k) {
    bst_remove(&(*b)->right, k);
    } else {
    if (NULL != (*b)->left && NULL != (*b)->right)
    {
        temp = bst_min((*b)->right);
        bst_swap_keys((*b), temp);
        bst_remove(&(*b)->right, k);
    }
    else if (NULL != (*b)->left)
    {
        *b = (*b)->left;
    }
    else if (NULL != (*b)->right)
    {
        *b = (*b)->right;
    }
    else
    {
        (*b) = NULL;
    }
    free(temp);
    }
}

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

void bst_delete(bst **b) {
    if (NULL == b) {
    return;
    }
    if (NULL != *b) {
    bst_delete(&(*b)->left);
    bst_delete(&(*b)->right);
    free(*b);
        *b = NULL;
    }
}

Печать BST в форматеNewick и считывание значений всегда кажется мне чем-то вроде взлома (потому что в Newick нет различия между L->R и R - >L...), но у меня есть слабое место для него, я также привык читать его и нашел его удобным для отладки в прошлом. И ваш метод, делающий печать, должен быть последовательным в своем заказе в любом случае, если только ты сошел с ума. Это также демонстрирует обертывание рекурсивной задачи путем разделения рекурсивной работы на отдельный метод, который затем вызывается из общедоступного метода. Последний обрабатывает другие задачи, которые не так хорошо подходят для рекурсии (например, печать точки с запятой и новой строки только один раз и на верхнем уровне.)

void bst_newick(const bst *b)
{
    if (NULL != b)
    {
    bst_newick_rec(b);
    printf(";\n");
    }
    else
    {
    printf("NULL!\n");
    }
}

static void bst_newick_rec(const bst *b)
{
    if (NULL == b) {
    return;
    }

    if (NULL != b->left || NULL != b->right) {
    printf("(");
    if (NULL != b->left && NULL != b->right) {
        bst_newick_rec(b->left);
        printf(",");
        bst_newick_rec(b->right);
    } else if (NULL != b->left) {
        bst_newick_rec(b->left);
    } else {
        bst_newick_rec(b->right);
    }
    printf(")");
    }
    printf("%d", b->key);
}

Создание метода замены ключей на самом деле является лишь незначительным удобством.

static void bst_swap_keys(bst *a, bst *b)
{
    int temp;
    if (NULL != a && NULL != b && a != b)
    {
    temp = a->key;
    a->key = b->key;
    b->key = temp;
    }
}

static void *ecalloc(size_t n, size_t s) {
    void *o = calloc(n, s);
    if (NULL == o) {
    fprintf(stderr, "Memory allocation failed!\n");
    exit(EXIT_FAILURE);
    }
    return o;
}

Пожалуйста, имейте в виду, что это в основном было собрано в моем перерыве на кофе, и не был тщательно протестирован. Надеюсь, это поможет.