请问删除的代码是不是不对呀,用一个指针指向要删除的节点后再改变他的值对原来的树没影响吧?
那我如果想用 那个 search函数的话 应该怎么写呢 还是必须直接用T开始找呀 就像最下面的代码一样
#include<stdio.h>
#include<stdlib.h>
typedef int KeyType;
typedef struct BSTNode {
KeyType key;
struct BSTNode* lchild;
struct BSTNode* rchild;
}BSTNode,*BiTree;
//54,20,66,40,28,79,58
int BST_Insert(BiTree& T, KeyType k)
{
if (NULL == T)
{
T = (BiTree)malloc(sizeof(BSTNode));//为新结点申请空间
T->key = k;
T->lchild = NULL;
T->rchild = NULL;
return 1;
}
if (k == T->key)
return 0;//相同元素不插入
else if (k < T->key)
return BST_Insert(T->lchild, k);
else
return BST_Insert(T->rchild, k);
}
void Create_BST(BiTree& T, KeyType str[], int n)
{
T = NULL;
for (int i = 0; i < n; i++)
{
BST_Insert(T, str[i]);
}
}
void Inorder(BiTree T)
{
if(T != NULL)//注意不要用while
{
Inorder(T->lchild);
printf("%3d", T->key);
Inorder(T->rchild);
}
}
BSTNode* BST_Search(BiTree T, KeyType key, BiTree& p)
{
p = NULL;
while (NULL != T && key != T->key)
{
p = T;
if (key > T->key) T = T->rchild;//比当前节点大,去右边找
else T = T->lchild;//比当前节点小,去左边找
}
return T;
}
void DeleteNode(BiTree& T, KeyType x)
{
BiTree p;
BiTree del = BST_Search(T, x, p);
if (del == NULL) return;
if (del->lchild == NULL)
{
BiTree temp = del;
del = del->rchild;
free(temp);
}
else if (del->rchild == NULL)
{
BiTree temp = del;
del = del->lchild;
free(temp);
}
else
{
BiTree dead = del->lchild;
while (NULL != dead->rchild) dead = dead->rchild;
del->key = dead->key;
DeleteNode(del->lchild, dead->key);
}
}
int main()
{
BiTree search;
BiTree parent;//存储父亲结点的地址值
BiTree T;
KeyType str[]= { 54,20,66,40,28,79,58 };//将要进入二叉排序树的元素值
Create_BST(T, str, 7);
Inorder(T);
printf("\n");
search = BST_Search(T, 40, parent);
if (search)
{
printf("找到对应结点,值=%d\n", search->key);
}
else {
printf("未找到对应结点\n");
}
DeleteNode(T,54);
Inorder(T);
printf("\n");
}
就像这样
void DeleteNode(BiTree& T, KeyType x)
{
BiTree p;
BiTree del = BST_Search(T, x, p);
if (del == NULL) return;
if (del->lchild == NULL)
{
BiTree temp = del;
del = del->rchild;
free(temp);
}
else if (del->rchild == NULL)
{
BiTree temp = del;
del = del->lchild;
free(temp);
}
else
{
BiTree dead = del->lchild;
while (NULL != dead->rchild) dead = dead->rchild;
del->key = dead->key;
DeleteNode(del->lchild, dead->key);
}
}