数据结构—二叉查找树相关

科科都不挂

下面代码中有两个删除二叉查找树结点的函数，一个是用递归来找目标节点，一个是循环来找目标节点。本意都是找目标节点，但是当我使用循环删除结点时时，后面的中序（或换成前序遍历）就会显示溢出。劳烦各位鱼油帮我看看啦~~

/*
二叉查找树 BST

1.二叉查找树的结构体
2.插入
3.删除 
*/
#include <stdio.h>
#include <stdlib.h>

typedef int Elemtype;
typedef struct TNode{
        Elemtype data;
        struct TNode *lchild, *rchild;
}TNode, *Tree;

Tree SearchBST (Tree T, Elemtype K);
void Delete (Tree *T);
int DeleteBST (Tree *T, Elemtype key);
int In_orderTraversal(Tree T);

//(递归)数据的查找,返回目标结点或NULL
Tree SearchBST (Tree T, Elemtype K)
{
        if (T == NULL || T->data == K)
                return T;
        else if (K > T->data)
                return SearchBST (T->rchild, K);
        else
                return SearchBST (T->lchild, K);
}

//标准数据的插入
void InsertBST (Tree *T, Elemtype K)
{
        if (*T == NULL)
        {
                *T = (Tree)malloc(sizeof(TNode));
                (*T)->data = K;
                (*T)->lchild = NULL;
                (*T)->rchild = NULL;
        }
        else if (K > (*T)->data)
                InsertBST (&((*T)->rchild), K);
        else if (K < (*T)->data) //这步也重要，因为要过滤掉相等的元素
                InsertBST (&((*T)->lchild), K);
}

////标准数据的删除
//int DeleteBST (Tree *T, Elemtype key)
//{
//        if (*T == NULL)
//                return 0;
//        
//        //查找合适的结点
//        if (key > (*T)->data)
//                return DeleteBST (&(*T)->rchild, key);
//        else if (key < (*T)->data)
//                return DeleteBST (&(*T)->lchild, key);
//        else
//        {
//                printf ("(删除%d)", (*T)->data);
//                Delete (T);
//                return 1;
//        }
//}

////标准数据的删除
//int DeleteBST (Tree *T, Elemtype key)
//{
//        Tree current;
//        
//        current = *T;
//        //查找合适的结点
//        while (current != NULL)
//        {
//                if (key > current->data)
//                        current = current->rchild;
//                else if (key < current->data)
//                        current = current->lchild;
//                else
//                {
//                        printf ("(删除%d)", current->data);
//                        Delete (¤t);
//                        return 1;
//                }
//        }
//        return 0;
//}

void Delete (Tree *T)
{
        Tree temp;
        Tree cur; //当前的结点
        
        //ps:不需要特意去判断是否没有两个孩子
        if ((*T)->lchild == NULL) //结点没左孩子
        {
                temp = *T;
                *T = (*T)->rchild; //接上右孩子
                free (temp);
        }
        else if ((*T)->rchild == NULL)//结点没右孩子
        {
                temp = *T;
                *T = (*T)->lchild; //接上左孩子
                free (temp);
        }
        else //两个孩子都有
        {
                cur = (*T)->lchild;
                while (cur->rchild != NULL) //找左子树中最大的结点（左子树中最右边）
                        cur = cur->rchild;
                
                (*T)->data = cur->data; //移动位置 (数据)
                Delete (&cur); //删除左子树的最大结点（缓存）
        }
}

int In_orderTraversal(Tree T)
{
        if (T == NULL)
                return 0;
        
        printf ("-%d-", T->data); //输出数据
        In_orderTraversal(T->lchild); //不断查找左子树
        In_orderTraversal(T->rchild); //如果存在右子树的话，就查右子树有无左子树
}

int main (void)
{
        Tree T = NULL;
        int num;
        
        scanf ("%d", &num);
        while (num != 0)
        {
                InsertBST (&T, num);
                scanf ("%d", &num);
        }
        
        In_orderTraversal (T); //中序遍历
        
        scanf ("%d", &num);
        while (num != 0)
        {
                DeleteBST (&T, num);
                In_orderTraversal (T); //中序遍历
                scanf ("%d", &num);
        }
        
        return 0;
}

xieglt

该了两个函数

int DeleteBST (Tree *T, Elemtype key)
{
        Tree current = *T;
        Tree father = *T;
        int flag = 0;
        
        //问题出在删除当点节点后，当前节点在其父节点中的链接并没有被改变。
        //因此，需要设置一个当前节点的父节点指针，删除当前节点后，重新设置
        //在父节点中的链接
        while(current != NULL) 
        {
                if(key > current->data)
                {
                        father = current;
                        current = current->rchild;
                        flag = -1;
                }
                else if(key < current->data)
                {
                        father = current;
                        current = current->lchild;
                        flag = 1;
                }
                else
                {
                        printf("删除(%d)",key);
                        Delete(¤t);
                        //根据 flag 重新链接树
                        //flag = 0 ，则删除的是根节点
                        if(flag == 0)
                        {
                                *T = current;
                        }
                        //=-1 删除的是父节点的右节点
                        else if(flag == -1)
                        {
                                father->rchild = current;
                        }
                        //=1 删除的是父节点的左节点
                        else
                        {
                                father->lchild = current;
                        }
                        break;
                }
        }
        return 0;
}

void Delete (Tree *T)
{
        Tree temp;
        Tree cur; //当前的结点
        
        //ps:不需要特意去判断是否没有两个孩子
        if ((*T)->lchild == NULL) //结点没左孩子
        {
                temp = *T;
                *T = (*T)->rchild; //接上右孩子
                free (temp);
        }
        else if ((*T)->rchild == NULL)//结点没右孩子
        {
                temp = *T;
                *T = (*T)->lchild; //接上左孩子
                free (temp);
        }
        else //两个孩子都有
        {
                        /*
                cur = (*T)->lchild;
                while (cur->rchild != NULL) //找左子树中最大的结点（左子树中最右边）
                        cur = cur->rchild;
                (*T)->data = cur->data; //移动位置 (数据)
                Delete (&cur); //删除左子树的最大结点（缓存）
                        */
                        /*
                        按照规则，左子节点小于父节点，右子节点大于父亲节点，比如
                                         10
                                         |
                                        / \
                                      5  20(删除20)
                                         /   \
                                        16    25
                                       /  \    / \
                                      15  18   24 26
                                          / \
                                       17  19
                        按规则删除20后，将该节点替换其子节点16，其右节点25应该作为19的右子节点
                        代码实现如下：
                        */
                        //取得当前节点
                        temp = * T;
                        //保存当前节点的右子节点
                        cur = (*T)->rchild;
                        //将当前节点替换为其左子节点
                        *T = (*T)->lchild;
                        //释放内存
                        free(temp);
                        //找左子节点中的最右子节点。
                        temp = *T;
                        while(temp->rchild != NULL)
                        {
                                temp = temp->rchild;
                        }
                        //连接右子节点
                        temp->rchild = cur;
        }
}