【二叉树】二叉搜索树创建、插入、删除、查找等操作

二叉搜索树性质如下：

//二叉搜索树篇
#include <stdio.h>
#include <stdlib.h>

struct search_tree_typedef;
struct search_tree_typedef{
	struct search_tree_typedef *p;
	struct search_tree_typedef *lc;
	struct search_tree_typedef *rc;
	int key;
};
typedef struct search_tree_typedef stree_node;

//向二叉搜索树插入一个元素
int insert_search_tree(stree_node **T, int key){
	stree_node *x, *y, *new_node;

	if((new_node = (stree_node*)malloc(sizeof(stree_node)))==NULL)
		return -1;
	new_node->lc = NULL;
	new_node->rc = NULL;
	new_node->key = key;
	x=*T;
	if(x==NULL){
		new_node->p = NULL;
		*T = new_node;

		return 0;
	}
	while(x!=NULL){
		y = x;
		if(key>x->key){
			x = x->rc;
		}
		else{
			x = x->lc;
		}
	}
	new_node->p = y;
	if(key>y->key)
		y->rc = new_node;
	else
		y->lc = new_node;

	return 0;
}

//创建二叉搜索树

int create_search_tree(stree_node **T){
	int key;

	while(1){
		scanf("%d", &key);
		if(key==0)
			return 0;
		if(insert_search_tree(T, key)==-1)
			return -1;
	}
}

//查找关键字为key的节点
stree_node* find_node(stree_node *T, int key){
	stree_node *x;
	x = T;
	while(x!=NULL){
		if(x->key==key)
			break;
		else if(key<x->key){
			x=x->lc;
		}
		else{
			x=x->rc;
		}
	}
	return x;
}

//查找最大关键字的节点
stree_node* find_maxkey(stree_node *T){
	stree_node *x, *y;

	x = T;
	if(T==NULL)
		return NULL;
	while(x!=NULL){
		y = x;
		x = x->rc;
	}
	return y;
}

//查找最小关键字的节点

stree_node* find_minkey(stree_node *T){
	stree_node *x, *y;

	x = T;
	if(T==NULL)
		return NULL;
	while(x!=NULL){
		y = x;
		x = x->lc;
	}
	return  y;
}

//查找指定关键字的节点的前驱节点
stree_node* find_precursor(stree_node *T, int key){
	stree_node *x, *y;

	x = find_node(T, key);
	if(x==NULL)
		return NULL;
	else{
		if(x->lc==NULL){
			if(x->p!=NULL){
				if(x->p->rc == x){
					return x->p;
				}
				else
					return NULL;
			}
		}
		else{
			return find_maxkey(x->lc);
		}
	}
}

//查找指定节点的前驱结点

stree_node* find_precursor2(stree_node *x){
	if(x==NULL)
		return NULL;
	else{
		if(x->lc==NULL){
			if(x->p!=NULL){
				if(x->p->rc == x){
					return x->p;
				}
				else
					return NULL;
			}
		}
		else{
			return find_maxkey(x->lc);
		}
	}
}

//查找指定关键字key的节点的后驱节点

stree_node* find_successor(stree_node *T, int key){
	stree_node *x, *y;

	x = find_node(T, key);
	if(x==NULL)
		return NULL;
	else{
		if(x->rc==NULL){
			if(x->p!=NULL){
				if(x->p->lc == x){
					return x->p;
				}
				else
					return NULL;
			}
		}
		else{
			return find_minkey(x->rc);
		}
	}
}

//查找指定节点的后驱节点

stree_node* find_successor2(stree_node *x){
	if(x==NULL)
		return NULL;
	else{
		if(x->rc==NULL){
			if(x->p!=NULL){
				if(x->p->lc == x){
					return x->p;
				}
				else
					return NULL;
			}
		}
		else{
			return find_minkey(x->rc);
		}
	}
}

//删除指定关键字key的节点

int delete_stree_node(stree_node **T, int del_key){
	stree_node *x, *temp;

	x = find_node(*T, del_key);
	if(x==NULL)
		return -1;
	else{
	//1.如果删除结点左右子树都为空，则直接释放该结点
	//2.如果删除结点左右子树其一不为空，则找出删除结点后继结点，将该后继结点代替删除结点（后继结点父节点为删除结点父节点，后继结点左子树为删除结点左子树，后继结点右子树为删除结点右子树），释放后继结点
	//3.如果删除结点左右子树都不为空，则将该后继结点代替删除结点，相应修改后继结点父结点的左子树
		if(x->lc==NULL&&x->rc==NULL){
			if(x->p==NULL)
				*T = NULL;
		}
		else if(x->lc&&x->rc){
			//先在x的右子树找出后继结点
			temp = find_successor2(x);

			if(x->p==NULL){
				*T = temp;
				if(temp->p == x){  //x->rc->lc必为空
					temp->lc = x->lc;
				}
				else{
					temp->p->lc = temp->rc;
					temp->lc = x->lc;
					temp->rc = x->rc;
				}
			}
			else{
				if(x->p->lc == x)
					x->p->lc = temp;
				else
					x->p->rc = temp;
				if(temp->p == x){  //x->rc->lc必为空
					temp->lc = x->lc;
				}
				else{
					temp->p->lc = temp->rc;
					temp->lc = x->lc;
					temp->rc = x->rc;
				}
			}
		}
		else{
			if(x->lc){
				if(x->p==NULL)
					*T = x->lc;
				else{
					if(x->p->lc == x)
						x->p->lc = x->lc;
					else
						x->p->rc = x->lc;
				}
			}
			else{
				if(x->p==NULL)
					*T = x->rc;
				else{
					//最简单方法就是另x->p的左子树或右子树指向x的右子树
					if(x->p->lc == x)
						x->p->lc = x->rc;
					else
						x->p->rc = x->rc;
				}
			}
		}
		free(x);
	}
}

//中序遍历二叉树

void in_visit_tree(stree_node *tree){
	if(tree==NULL)
		return;
	if(tree->lc!=NULL){
		in_visit_tree(tree->lc);
	}
	printf("%d ", tree->key);
	if(tree->rc!=NULL){
		in_visit_tree(tree->rc);
	}
}

//测试数据：建树序列13 5 2 9 6 18 15 17 19，中序序列为2 5 6 9 13 15 17 18 19
int main(void){
	stree_node *thead=NULL;
	stree_node *maxkey, *minkey, *precursor, *successor;

	create_search_tree(&thead);          //测试成功
	in_visit_tree(thead); printf("
");  //测试成功
	maxkey = find_maxkey(thead);         //测试成功
	minkey = find_minkey(thead);         //测试成功
	printf("min=%d
", (maxkey==NULL)?-1:maxkey->key);
	printf("max=%d
", (minkey==NULL)?-1:minkey->key);
	precursor = find_precursor(thead, minkey->key);
	successor = find_successor(thead, 13);
	printf("precursor=%d
", (precursor==NULL)?-1:precursor->key);        //测试成功
	printf("successor=%d
", (successor==NULL)?-1:successor->key);        //测试成功

	delete_stree_node(&thead, 5);        //测试成功
	in_visit_tree(thead); printf("
");

	system("pause");
	return 0;
}