二叉树删除结点详细代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>typedef int data_t;
typedef struct _node
{data_t data;struct _node* left;struct _node* right;
}node_t;int bst_create(node_t**, data_t);//函数声明BST创建
int bst_add(node_t**, data_t);//函数声明结点增加
void bst_preorder(node_t* root);
void bst_midorder(node_t* root);
void bst_posorder(node_t* root);
void bst_destroy(node_t** root);
int bst_find(node_t*, data_t);//函数声明结点查询
int bst_delete(node_t** root, data_t data);//函数声明结点删除int bst_create(node_t** root, data_t data)
{node_t* pnew = (node_t*)malloc(sizeof(node_t));if (pnew == NULL)return -1;pnew->data = data;pnew->left = pnew->right = NULL;*root = pnew;return 0;
}int bst_add(node_t** root, data_t data)
{node_t* pnew = (node_t*)malloc(sizeof(node_t));if (pnew == NULL)return -1;pnew->data = data;pnew->left = pnew->right = NULL;// 如果树为空，创建根节点if (*root == NULL){return bst_create(root, data);}node_t* p = *root, * parent = NULL;while (p){parent = p;if (data < p->data)p = p->left;elsep = p->right;}if (data < parent->data)parent->left = pnew;elseparent->right = pnew;return 0;}
int bst_find(node_t* root, data_t data)
{node_t* p = root;while (p){if (data < p->data)p = p->left;else if (data > p->data)p = p->right;elsereturn 0;}return -1;
}//前序遍历，根左右
void bst_preorder(node_t* root)
{if (root == NULL)return;printf("%3d", root->data);bst_preorder(root->left);bst_preorder(root->right);
}
//中序遍历，左根右
void bst_midorder(node_t* root)
{if (root == NULL)return;bst_midorder(root->left);printf("%3d", root->data);bst_midorder(root->right);
}//后序遍历，左右根
void bst_posorder(node_t* root)
{if (root == NULL)return;bst_posorder(root->left);bst_posorder(root->right);printf("%3d", root->data);
}
//删除结点
int bst_delete(node_t** root, data_t data)
{node_t* del = *root;//指向待删除结点node_t* replace = NULL;//指向实际被删除结点node_t* parent = NULL;//指向实际被删除结点的双亲结点while (del){if (data < del->data){parent = del;del = del->left;}else if (data > del->data){parent = del;del = del->right;}else//找到待删除结点{if (del->left)//待删除结点有左子树{parent = del;replace = del->left;while (replace->right)//在左子树中找出最大值结点{parent = replace;replace = replace->right;}del->data = replace->data;//用找到的结点数据替换待删除的结点数据if (parent->right == replace)parent->right = replace->left;else//待删除结点左子树最大值恰好是待删除结点的左节点parent->left = replace->left;free(replace);}else if (del->right)//待删除结点仅有右子树{parent = del;replace = del->right;while (replace->left)//在右子树中找出最小值结点{parent = replace;replace = replace->left;}del->data = replace->data;//用找到的结点数据替换待删除的结点数据if (parent->left == replace)parent->left = replace->right;else//待删除结点you子树最大值恰好是待删除结点的you节点parent->right = replace->right;free(replace);}else//待删除结点为叶子结点{if (parent == NULL)//删除的是唯一的结点{free(del);return 0;}if (parent->left == del)parent->left = NULL;elseparent->right = NULL;free(del);}return 0;}}return -1;
}//BST树回收
static void bst_free(node_t* root)
{if (root == NULL)return;bst_free(root->left);bst_free(root->right);free(root);
}void bst_destroy(node_t** root)
{bst_free(*root);*root = NULL;
}int main()
{node_t* root = NULL;srand(time(NULL));for (int i = 0; i < 10; i++){int data = rand() % 100;bst_add(&root, data);printf("%3d", data);}printf("\n");puts("=====前序遍历====");bst_preorder(root);printf("\n");puts("=================");printf("\n");puts("=====中序遍历====");bst_midorder(root);printf("\n");puts("=================");puts("=====后序遍历====");bst_posorder(root);printf("\n");puts("=================");while (1){printf("请输入要查询的数据(-1退出)：");data_t data;scanf_s("%d", &data);if (data == -1)break;if (bst_find(root, data) == 0)printf("找到数据 %d\n", data);elseprintf("未找到数据 %d\n", data);puts("=====中序遍历====");bst_midorder(root);printf("\n");puts("=================");}while (1){printf("请输入要删除的数据(-1退出)：");data_t data;scanf_s("%d", &data);if (data == -1)break;if (bst_delete(&root, data) == 0)printf("找到数据 %d\n", data);elseprintf("未找到数据 %d\n", data);puts("=====中序遍历====");bst_midorder(root);printf("\n");puts("=================");}bst_destroy(&root);return 0;}

运行结果：