学习删除二叉排序树时遇到的问题，在删除结点时遇到问题，如下，注释的是我自己的想法，原本的内容是看小甲鱼的视频弄的，但感觉不太对，找了不少博客还是没解决问题
运行结果及报错内容
问题
每种情况的free（p），都会报错，没搞明白。
到底为啥？
bool Delete(BiTree* t)//传输的是指针域的地址,直接修改lchild or rchild
{
BiTree q, s;
if ((*t)->lchild == NULL)//左子树为空，连接右子树
{
q = *t;
(*t) = (*t)->lchild;
//q = (*t)->rchild;//连接右子树，直接改变指针
//(*t)->data = q->data;
//(*t)->rchild = q->rchild;
free(q);//删除结点所占空间
}
源程序如下：
#include<iostream>
#include<stack>
using namespace std;
//顺序查找
int Sq_Sear(int* a, int n, int key)
{
int i = n;
for (i = 0; i <= n; i++)//cpu要做两次判断，可做优化
{
if (a[i] == key)
{
return i;
}
}
return 0;
//改进,增加一个哨兵来减少循环次数，会污染数组
//int i = n;
//a[0] = key;
//while (a[i] != key)
//{
// i--;
//}
//return i;
}
//插值查找(按比例查找)
int bia_search(int str[], int n, int key)
{
int low = 0, high = n-1;
int mid = 0;
while (low <= high)
{
//折半与按比例的优劣，数的值跨度不是很大按比例更好，
mid = low + (key - str[low]) / (str[high] - str[low]) * (high - low);
if (str[mid] == key)
return mid;
if (str[mid] > key)
high = mid - 1;
if (str[mid] < key)
low = mid + 1;
}
return -1;
}
//斐波那契查找
//1.首先创建斐波那契数组
//2。找到有序表最大元素
//3.补齐有序表最大值到最接近斐波那契数组的一个元素
//4.根据斐波那契的规则对比查找
void produceFib(int* fib, int size)
{
int i;
fib[0] = 0;
fib[1] = 1;
for (i = 2; i < size; i++)
{
fib[i] = fib[i - 1] + fib[i - 2];
}
}
int FibonacciSearch(int* data, int length, int searchValue)
{
int low = 0, high = length - 1;
int i = 0,mid = 0;
int fib[10];
produceFib(fib, length);
int k = 0;//最接近斐波那契的数
while (high > fib[k] - 1)
{
k++;
}
//补齐有序表
int* temp;
temp = (int*)new int[fib[k] - 1];
memcpy(temp, data, length * sizeof(int));
for (i = length; i < fib[k] - 1; i++)
{
data[i] = data[high];
}
while (low <= high)
{
if (k > 0)
mid = low + fib[k - 1] - 1;
else
mid = low;
if (temp[mid] == searchValue)
{
if (mid <= length - 1)
return mid;
else
return length - 1;
}
if (temp[mid] > searchValue)
{
high = mid - 1;
k = k - 1;
}
if (temp[mid] < searchValue)
{
low = mid + 1;
k = k - 2;
}
}
delete[] temp;
return -1;
}
typedef struct BiNode
{
int data;
struct BiNode* lchild;
struct BiNode* rchild;
BiNode(int x) :
data(x), lchild(NULL), rchild(NULL) {};
}BiNode,*BiTree;
//二叉查找树
//T为搜索的树，f为记录父节点的指针，p作为临时指针保存输出
bool SearchBST(BiTree T, int key, BiTree f, BiTree* p)
{
if (!T)
{
*p = f;
return false;
}
else if(key==T->data)
{
*p = T;
return true;
}
else if(key < T->data)
{
return SearchBST(T->lchild,key,T,p);
}
else if(key > T->data)
{
return SearchBST(T->rchild,key,T,p);
}
else
return false;
}
bool SearchBST(BiTree T, int key)
{
BiTree f(0);
BiTree* p(0);
f = (BiTree)new BiTree; p = new BiTree;
if (!T)
{
*p = f;
return false;
}
else if (key == T->data)
{
*p = T;
return true;
}
else if (key < T->data)
{
return SearchBST(T->lchild, key);
}
else if (key > T->data)
{
return SearchBST(T->rchild, key);
}
else
return false;
}
//删除
//*p搜索位置结点
//定义两个临时指针
//三种情况
bool Delete(BiTree* t)//传输的是指针域的地址,直接修改lchild or rchild
{
BiTree q, s;
if ((*t)->lchild == NULL)//左子树为空，连接右子树
{
q = *t;
(*t) = (*t)->lchild;
//q = (*t)->rchild;//连接右子树，直接改变指针
//(*t)->data = q->data;
//(*t)->rchild = q->rchild;
free(q);//删除结点所占空间
}
else if ((*t)->rchild == NULL)//右子树为空，连接左子树
{
q = *t;
(*t) = (*t)->lchild;//连接左子树，直接改变指针
//free(q);//删除结点所占空间
}
else//有两个孩子
{
q = (*t);//找到中序遍历时的前驱结点，即孩子结点的右子树最右边的叶子结点
s = (*t)->lchild;
while (s->rchild != NULL)
{
q = s;//记录当前结点值
s = s->rchild;//找到右子树最右边的叶子结点
}
(*t)->data = s->data;
if (q == *t)//孩子结点为目标结点
{
q->lchild = s->lchild;//链接
}
else//存在右子树
{
q->rchild = s->lchild;//目标结点的父亲结点链接孩子结点
}
free(s);
}
return true;
}
//删除二叉排序树的结点
//1.判断是否为空树
//2.搜索判断是否存在
//3.执行删除函数
int DelectBST(BiTree T, int key)
{
if (T == NULL)
{
return false;
}
else if (key == T->data)
{
return Delete(&T);
}
else if(key < T->data)
{
return DelectBST(T->lchild, key);
}
else
{
return DelectBST(T->rchild,key);
}
}
//插入
int InsertBST(BiTree* T, int key)
{
BiTree p ,s;
//传入临时结点指针p，通过搜索函数返回当前最接近该插入值的一个节点位置
if (!SearchBST(*T, key, NULL, &p))
{
s = (BiTree)new BiTree;
s->data = key;
s->lchild = NULL;
s->rchild = NULL;
if (!p)
{
*T = s;//此处为插入根节点
}
else if (key < p->data)
{
p->lchild = s;
}
else
{
p->rchild = s;
}
return true;
}
else {
cout << "已存在相同数据！" << endl;
return false;
}
}
//遍历
//遍历迭代
void depthFirstSearch(BiNode* root)
{
stack<BiNode*>sta;
sta.push(root);
BiNode* p;
while (!sta.empty())
{
p = sta.top();
if (p != NULL)
cout << p->data<<' ';
sta.pop();
if (p->rchild != NULL)
sta.push(p->rchild);
if (p->lchild= NULL)
sta.push(p->lchild);
}
cout << endl;
}
int main(void)
{
//int data[] = { 1,2,3,4,5,6,7,8,9,10 };
//int len = sizeof(data) / sizeof(data[0]);
//int index = FibonacciSearch(data,len,5);
//cout << index;
BiTree T = BiTree(0);
InsertBST(&T, 1);
InsertBST(&T, 2);
InsertBST(&T, 3);
InsertBST(&T, 5);
InsertBST(&T, 7);
InsertBST(&T, 8);
InsertBST(&T, 12);
InsertBST(&T, 11);
InsertBST(&T, 21);
InsertBST(&T, 31);
InsertBST(&T, 51);
InsertBST(&T, 17);
InsertBST(&T, 18);
InsertBST(&T, 121);
depthFirstSearch(T);
cout << SearchBST(T, 3) << endl;
depthFirstSearch(T);
DelectBST(T,12);
depthFirstSearch(T);
return 0;
}
