性质：
设x为二叉搜索树上的节点，如果y为x的左子树上的节点，则有y.key<=x.key；如果y为x的右子树上的节点，则有y.key>x.key。
二叉搜索树的节点删除
二叉搜索树的节点z删除大致可分为三种情况：
1、z没有子节点，则简单删除z，并修改z父节点，用nil代替z称为父节点的孩子
2、z有一个孩子节点c，则用c替代z。
3、z有两个孩子节点，则需找出z 的后继节点。z的后继节点必然位于z的右子树当中，且为右子树的最小关键字节点。
#include<stdio.h>
#include<stdlib.h>
/******************************************************
* 二叉搜索树
******************************************************/
/******************************************************
* data structure and definition
******************************************************/
typedef int ElemType;
typedef struct TNode
{
ElemType key;
struct TNode *parent;
struct TNode *left;
struct TNode *right;
}TNode,*Tree;
typedef enum{
OK = 0,
ERROR = -1
}Status;
/******************************************************
* function : tree_destroy
* description : 销毁一个以T节点为根节点的树
* input : Tree *T
* output : Tree *T
* return value : Status(OK/ERROR)
* author : HanyoungXue
* date : 2018-04-22
*******************************************************/
Status tree_destroy(Tree *T){
if (*T){
TNode* left = (*T)->left;
TNode* right = (*T)->right;
free(*T);
*T = NULL;
tree_destroy(&left);
tree_destroy(&right);
return OK;
}
return ERROR;
}
/******************************************************
* function : tree_search
* description : 寻找关键字值为key的节点
* input : Tree T,ElemType key
* output : N/A
* return value : TNode* T
* author : HanyoungXue
* date : 2018-04-22
******************************************************/
TNode* tree_search(Tree T,ElemType key){
if(T==NULL || key==T->key){
return T;
}
if(key<T->key){
return tree_search(T->left,key);
}else{
return tree_search(T->right,key);
}
}
/*******************************************************
* function : tree_in_order_traverse
* description : 中序遍历输出以节点T为根节点的树
* input : Tree T
* output : N/A
* return value : Status(OK/ERROR)
* author : HanyoungXue
* date : 2018-04-22
*******************************************************/
Status tree_in_order_traverse(Tree T){
if(T!=NULL){
tree_in_order_traverse(T->left);
printf("%d\t",T->key );
tree_in_order_traverse(T->right);
return OK;
}
return ERROR;
}
/************************************************************
* function : tree_min
* description : 寻找以节点T为根节点的二叉树的最小关键字值的节点
* input : Tree T
* output : N/A
* return value : TNode* T
* author : HanyoungXue
* date : 2018-04-22
************************************************************/
TNode* tree_min(Tree T){
while(T->left){
T = T->left;
}
return T;
}
/************************************************************
* function : tree_max
* description : 寻找以节点T为根节点的二叉树的最大关键字值的节点
* input : Tree T
* output : N/A
* return value : TNode* T
* author : HanyoungXue
* date : 2018-04-22
************************************************************/
TNode* tree_max(Tree T){
while (T->right){
T = T->right;
}
return T;
}
/************************************************************
* function : tree_successor
* description : 寻找节点T的后继节点
* input : TNode* T
* output : N/A
* return value : TNode* y
* author : HanyoungXue
* date : 2018-04-22
************************************************************/
TNode* tree_successor(TNode* T){
if(T->right){
return tree_min(T->right);
}
TNode* y = T->parent;
while(y&&y->right == T){
T = y->right;
y = T->parent;
}
return y;
}
/************************************************************
* function : tree_insert
* description : 插入关键字为key的节点
* input : Tree *T,ElemType key
* output : N/A
* return value : Status(OK/ERROR)
* author : HanyoungXue
* date : 2018-04-22
************************************************************/
Status tree_insert(Tree *T,ElemType key){
TNode *z = (TNode *)malloc(sizeof(TNode));
z->key = key;
z->left = NULL;
z->right = NULL;
TNode *y = NULL;
TNode *x = *T;
while(x){
y = x;
if(z->key < x->key){
x = x->left;
}else{
x = x->right;
}
}
z->parent = y;
if(!y){
*T = z;
}else if(z->key < y->key){
y->left = z;
}else{
y->right = z;
}
return OK;
}
/***********************************************************
* function : tree_translate
* description : 用一棵子树替换另一棵子树
* input : Tree *T,TNode *u,TNode *v
* output : Tree *T
* return value : N/A
* author : HanyoungXue
* date : 2018-04-22
***********************************************************/
void tree_translate(Tree *T,TNode *u,TNode *v){
if(!(u->parent)){
*T = v;
}else if(u==u->parent->left){
u->parent->left = v;
}else{
u->parent->right = v;
}
if(v){
v->parent = u->parent;
}
}
/*********************************************************
* function : tree_delete
* description : 删除树T的某个节点z
* input : Tree *T,TNode *z
* output : Tree *T,TNode *z
* return value : N/A
* author : HanyoungXue
* date : 2018-04-22
*********************************************************/
void tree_delete(Tree *T,TNode *z){
if(!(z->left)){
tree_translate(T,z,z->right);
}else if(!(z->right)){
tree_translate(T,z,z->left);
}else{
TNode *y = tree_min(z->right);
if(y->parent!=z){
tree_translate(T,y,y->right);
y->right = z->right;
y->right->parent = y;
}
tree_translate(T,z,y);
y->left = z->left;
y->left->parent = y;
tree_destroy(&z);
}
}
int main(int argc, char const *argv[])
{
Tree T;
int n;
scanf("%d",&n);
for (int i = 0; i < n; ++i){
ElemType key = rand()%100;
tree_insert(&T,key);
}
tree_in_order_traverse(T);
printf("\n");
// printf("%d\n", tree_successor(tree_min(T))->key);
tree_delete(&T,tree_min(T));
tree_in_order_traverse(T);
printf("\n");
tree_delete(&T,tree_search(T,78));
tree_in_order_traverse(T);
printf("\n");
// tree_destroy(&T);
// tree_in_order_traverse(T);
return 0;
}
网友评论