为什么我的BST根指针因某种未知原因而改变？
我试图在C中实现二进制搜索树数据结构，我遇到了一个bug。 我的指针值因我不明白的原因而改变。 （请参阅post底部的奇怪输出[删除function和主要function说明输出来自哪里]）我的测试function如下：
int main(void) { Bst *bst = ( Bst* ) calloc( 1, sizeof( Bst ) ); BstInsert( bst, 7 ); BstInsert( bst, 8 ); BstInsert( bst, 2 ); BstInsert( bst, 1 ); BstTraverse( bst ); BstRemove( bst, 7); printf("=========================\n"); printf("Root Key: %d\n", bst->key ); printf("Left Key: %d\n", bst->left->key ); printf("Right Key: %d\n", bst->right->key ); printf("Location: %p\n", &bst); BstTraverse( bst ); return 0; } 我的删除节点function如下：
void BstRemove( Bst *root, int key ){ //Seems like recursive algorithm would need doubly linked bst implementation Bst *temp_node = BstFind( root, key ); Bst *parent_node = BstGetParent( root, key ); Bst *replacement_node = ( Bst* ) calloc( 1, sizeof( Bst ) ); if ( temp_node->key == root->key ) { if (root->left) replacement_node = BstMax( root->left ); else if ( root->right ) replacement_node = BstMin( root->right ); else replacement_node = NULL; } else if ( temp_node->left ) { replacement_node = BstMax( temp_node ); Bst *parent_replacement_node = BstGetParent( root, replacement_node->key ); parent_replacement_node->right = NULL; } else if ( temp_node->right ) { replacement_node = BstMin( temp_node ); Bst *parent_replacement_node = BstGetParent( root, replacement_node->key ); parent_replacement_node->left = NULL; } else replacement_node = NULL; if ( parent_node && key key ) parent_node->left = replacement_node; else if ( parent_node ) parent_node->right = replacement_node; if ( replacement_node ) { if ( root->left->key != replacement_node->key ) replacement_node->left = temp_node->left; if ( root->right->key != replacement_node->key ) replacement_node->right = temp_node->right; } root = replacement_node; printf("Root Key: %d\n", root->key ); printf("Left Key: %d\n", root->left->key ); printf("Right Key: %d\n", root->right->key ); printf("Location: %p\n", &root); free(temp_node); }
输出如下：
1 2 7 8 Root Key: 2 Left Key: 1 Right Key: 8 Location: 0x7fffc5cf52e8 ========================= Root Key: 0 Left Key: 2 Right Key: 8 Location: 0x7fffc5cf5338 1 2 8 0 8
这让我很困惑的原因是因为我正在使用指针。 我认为root-> key值没有理由在delete函数中为2时进行更改，并且一旦处理完毕
root-> key变为0.我很感激任何能指出我的问题或帮助我朝正确方向前进的人。 如有必要，您可以在https://github.com/PuffNotes/C/blob/master/data_structures/binary_tree.c上查看我当前的BST实施。 我最近开始尝试每天编程以获得一些技能，并认为自己是C的初学者（供参考）。 谢谢。
您没有更改根节点指针。 它通过值传递给remove函数，因为它肯定是删除的可行目标，所以它应该通过地址传递，因为它可能会更改为不同的节点。 注意：如果我错过了某个地方的root我道歉，但你的编译应该抓住它）。
注意：我没有对此代码是否正确甚至是否有效进行validation; 但真正的提示是错误的是root =在底部，然后是打印输出，然后调用者（ main() ）执行相同的打印输出并显示不同的根指针值。
void BstRemove( Bst **root, int key ) { //Seems like recursive algorithm would need doubly linked bst implementation Bst *temp_node = BstFind( *root, key ); Bst *parent_node = BstGetParent( *root, key ); Bst *replacement_node = ( Bst* ) calloc( 1, sizeof( Bst ) ); if ( temp_node->key == (*root)->key ) { if ((*root)->left) replacement_node = BstMax( (*root)->left ); else if ( (*root)->right ) replacement_node = BstMin( (*root)->right ); else replacement_node = NULL; } else if ( temp_node->left ) { replacement_node = BstMax( temp_node ); Bst *parent_replacement_node = BstGetParent( (*root), replacement_node->key ); parent_replacement_node->right = NULL; } else if ( temp_node->right ) { replacement_node = BstMin( temp_node ); Bst *parent_replacement_node = BstGetParent( (*root), replacement_node->key ); parent_replacement_node->left = NULL; } else replacement_node = NULL; if ( parent_node && key < parent_node->key ) parent_node->left = replacement_node; else if ( parent_node ) parent_node->right = replacement_node; if ( replacement_node ) { if ( (*root)->left->key != replacement_node->key ) replacement_node->left = temp_node->left; if ( (*root)->right->key != replacement_node->key ) replacement_node->right = temp_node->right; } *root = replacement_node; printf("Root Key: %d\n", (*root)->key ); printf("Left Key: %d\n", (*root)->left->key ); printf("Right Key: %d\n", (*root)->right->key ); printf("Location: %p\n", root); free(temp_node); }
像这样调用它：
BstRemove( &bst, 7);
并习惯于通过地址传递root，因为当你开始编写平衡算法时，你会做很多事情。
@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; }
这意味着a）我不必输入烦人的if (NULL == thing)分配一直检查b）如果分配失败，程序将在打印消息后退出。 后者可能并不总是令人满意的（好吧，戒烟部分，至少，尽管如果你的内存耗尽，你没有很多选择），但在这种情况下绰绰有余。
设计问题
警告：这里使用的术语Design松散。
假设我们想要一个BST来存储一些整数。 您决定BST中的节点将存储一个整数和两个指针（到节点）。 那样就好。 但是，这意味着您无法明智地将密钥用作标记值来确定是否使用了节点。
幸运的是，我们不需要。 当树为空时，不要使用节点作为根，只需使用指向节点的指针。 没有节点时，指针为NULL 。 这与您使用remove方法遇到的问题有关。
BST是一棵树，由链接节点组成，对吧？ 或者是吗？ 您还可以将其视为一个树，其中每个节点实际上都是一个子树。 这使得它非常适合递归，所以让我们尽可能地使用递归来优雅地表达事物。
现在，我们有几个选择。
- 我们可以创建一个不可变的bst（所有修改调用看起来都像
b = bst_insert(b, 10)因为bst_insert等都会返回树的新修改副本而不改变旧的修改版本）。 - 我们可以在
void bst_insert(bst **b, int key)，称为bst_insert(&b, 10)，其中我们使用额外的间接级别来通过传入指针来修改我们的树到一个节点。 - 或者我们可以在前两个选项之间找到一些东西，其中我们有
bst *b(bst *b, int key)，它修改了*b（键和子指针）的含义，并分配了什么它不能。 这避免了额外的间接（这有点难看），但如果您使用分配函数返回值和函数副作用的组合来实现您的目标，则有点不一致。
我选择了第二选项。
调试
假设您在BST中插入1 。 也许你删除2 。 你怎么知道这有效？ 如果你能看到你的BST正在做什么，调试会不会更容易？
我建议（特别是在开始编写基本数据结构时，当像gdb这样的复杂调试环境可能是一种过度杀伤和b）信息过载时，你会编写很早就打印出数据结构状态的方法。
另外，如果你正在运行* nix， valgrind （发音为“Val grinned”）是你最好的朋友。 它是一个内存检查器，你可以使用它来确保你总是释放你分配的内存（当然，一旦你完成它），并寻找其他内存错误，如超出界限。 学会使用它（它实际上非常简单）。 如果你在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 ，并且稍微隐藏了只使用BST的任何人的struct bstnode类型的内容。
typedef struct bstnode bst;
extern说这些function基本上是在其他地方实现的。
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 #include #include "bst.h"
这是完整的struct bstnode 。 我们可以访问bst typedef，因为我们已经包含了bst.h
struct bstnode { int key; bst *left, *right; };
在此上下文中，static表示这些函数具有文件范围。
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 ，并将我们的main方法放在那里，但是为了紧凑，我没有。
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_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; } }
以Newick格式打印BST并读取值对我来说总是感觉有点像黑客（因为在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; }
请记住，这已基本上在我的咖啡rest时间组装，并没有经过严格的测试。 我希望这有帮助。