m0_55350262
2022-03-24 13:33
采纳率: 100%
浏览 26

二叉查找树的操作,删除节点的指针和内存释放问题

学习删除二叉排序树时遇到的问题,在删除结点时遇到问题,如下,注释的是我自己的想法,原本的内容是看小甲鱼的视频弄的,但感觉不太对,找了不少博客还是没解决问题

运行结果及报错内容

问题
每种情况的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;
}

1条回答 默认 最新

相关推荐 更多相似问题