6-12 二叉搜索树的操作集sample 运行时错误VS2019提示未加载wntdll

你可以先检查一下是否出现了内存管理操作上的问题，比如再删除了一次一个已经被删除了的指针。它可能不是很明显，在一个不起眼的地方已经被删除了。总得来说，这就是问题的根源。

在DEV里调试没有出现问题，但是鉴于PTA上始终无法通过我只能不情愿地把代码拷到VS2019里看看。

这是最初寻找错误前的代码。

#include <stdio.h> #include <stdlib.h> typedef int ElementType; typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ElementType Data; BinTree Left; BinTree Right; }; void PreorderTraversal( BinTree BT ); /* 先序遍历，由裁判实现，细节不表 */ void InorderTraversal( BinTree BT ); /* 中序遍历，由裁判实现，细节不表 */ BinTree Insert( BinTree BST, ElementType X ); BinTree Delete( BinTree BST, ElementType X ); Position Find( BinTree BST, ElementType X ); Position FindMin( BinTree BST ); Position FindMax( BinTree BST ); int main() { BinTree BST, MinP, MaxP, Tmp; ElementType X; int N, i; BST = NULL; scanf("%d", &N); for ( i=0; i<N; i++ ) { scanf("%d", &X); BST = Insert(BST, X); } printf("Preorder:"); PreorderTraversal(BST); printf("\n"); MinP = FindMin(BST); MaxP = FindMax(BST); scanf("%d", &N); for( i=0; i<N; i++ ) { scanf("%d", &X); Tmp = Find(BST, X); if (Tmp == NULL) printf("%d is not found\n", X); else { printf("%d is found\n", Tmp->Data); if (Tmp==MinP) printf("%d is the smallest key\n", Tmp->Data); if (Tmp==MaxP) printf("%d is the largest key\n", Tmp->Data); } } scanf("%d", &N); for( i=0; i<N; i++ ) { scanf("%d", &X); BST = Delete(BST, X); } printf("Inorder:"); InorderTraversal(BST); printf("\n"); return 0; } BinTree Insert( BinTree BST, ElementType X ){ if(BST== NULL){ //新建结点 BST= (BinTree)(malloc(sizeof(struct TNode))); BST->Data= X; BST->Left= NULL; BST->Right= NULL; return BST; } if(X<BST->Data){ BST->Left= Insert(BST->Left, X); } else{ BST->Right= Insert(BST->Right, X); } return BST; } //寻找最小值 Position FindMin( BinTree BST ){ if(BST== NULL) return NULL; if(BST->Left==NULL){ return BST; } else return FindMin(BST->Left); } //寻找最大值 Position FindMax( BinTree BST ){ if(BST== NULL) return NULL; if(BST->Right==NULL){ return BST; } else return FindMax(BST->Right); } //寻找指定值 Position Find( BinTree BST, ElementType X ){ if(BST==NULL) return NULL;//没有找到 if(X== BST->Data) return BST; else if(X<BST->Data) return Find(BST->Left, X);//向左找 else return Find(BST->Right, X);//向右找 } //删除指定结点 BinTree Delete( BinTree BST, ElementType X ){ //搜索移动指针过程 //无法找到 if(BST== NULL) { printf("Not Found\n"); return NULL; } //中途过程 else if(X<BST->Data){ BST->Left= Delete(BST->Left, X); } else if(X>BST->Data){ BST->Right= Delete(BST->Right,X); } //找到 else{ BinTree temp; temp= BST; if(BST->Left==NULL){ temp= BST; BST= BST->Right; free(temp); } else if(BST->Right==NULL){ temp= BST; BST= BST->Left; free(temp); } else{ //左右双全 将结点的值替换 删除右子树最小的 BinTree rightMin= FindMin(BST->Right); BST->Data= rightMin->Data; BST->Right= Delete(BST->Right, rightMin->Data); free(rightMin); } } return BST; } //中序遍历 void InorderTraversal(BinTree BST){ if(BST==NULL){ return; //终止 } else { InorderTraversal(BST->Left); printf("%d",BST->Data); InorderTraversal(BST->Right); } } //前序遍历 void PreorderTraversal(BinTree BST){ if(BST==NULL){ return; //终止 } else { printf("%d",BST->Data); PreorderTraversal(BST->Left); PreorderTraversal(BST->Right); } }

在VS2019中触发了断点，提示

查阅相关的博客你会发现这大概是个和内存管理相关的问题，对于这段代码来说，加上我对自己C编程能力的估计，考虑到其他几个点都过了，问题十有八九出在Delete模块。

//删除指定结点 BinTree Delete(BinTree BST, ElementType X) { //搜索移动指针过程 //无法找到 if (BST == NULL) { printf("Not Found\n"); return NULL; } //中途过程 else if (X < BST->Data) { BST->Left = Delete(BST->Left, X); } else if (X > BST->Data) { BST->Right = Delete(BST->Right, X); } //找到 else { BinTree temp; temp = BST; if (BST->Left == NULL) { temp = BST; BST = BST->Right; free(temp); } else if (BST->Right == NULL) { temp = BST; BST = BST->Left; free(temp); } else { //左右双全 将结点的值替换 删除右子树最小的 BinTree rightMin = FindMin(BST->Right); BST->Data = rightMin->Data; BST->Right = Delete(BST->Right, rightMin->Data); free(rightMin); } } return BST; }

我试着把所有相关释放内存的操作都注释掉，因为PTA并不要求真正实现删除。在这种情况下，运行时错误的问题就被解决了。

仔细看了下代码，应当是这一段代码片的问题

else { //左右双全 将结点的值替换 删除右子树最小的 BinTree rightMin = FindMin(BST->Right); BST->Data = rightMin->Data; BST->Right = Delete(BST->Right, rightMin->Data); free(rightMin); }

因为rightMin一定是片叶子，rightMin的指针在free之前已经在Delete中被删除了，再进行一次free就导致了报错。