算法导论之二叉排序树

拼搏现实的明天。 2022-08-22 01:28 143阅读 0赞

二叉排序树定义：

1、以一颗二叉树来组织。

2、包含属性指向左孩子、右孩子和双亲。

3、对任何结点x，其左子树的关键字最大不超过x->value，其右子树中的关键字最小不低于x->value。

实现代码如下：

#include <stdio.h>
    #include <stdlib.h>
    
    struct TreeNode{
    	int value;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	struct TreeNode *p;
    };
    
    typedef struct TreeNode Node;
    
    //插入节点 
    Node *insertNode(Node *t,Node *insert){
    	Node *y = NULL;
    	Node *x= t;
    	while(x!=NULL){
    		y=x;
    		if(insert->value>x->value)
    			x=x->right;
    		else x=x->left;
    	}
    	insert->p=y;
    	if(y==NULL)
    		t=insert;
    	else{
    		if(insert->value<y->value)
    			y->left=insert;
    		else y->right=insert;
    	}
    	insert->right=NULL;
    	insert->left=NULL;
    	return t;
    } 
    
    //中序遍历
    void inOrder(Node *t){
    	if(t==NULL){
    		return;
    	}
    	inOrder(t->left);
    	printf("%d\t",t->value);
    	inOrder(t->right);
    } 
    
    //将一颗以v为根的子树来替换一颗以u为根的子树
    Node *TRANSPLANT(Node *T,Node *u,Node *v){
    	if(u->p==NULL){
    		T=v;
    	}else if(u==u->p->left){
    		u->p->left=v;
    	}else{
    		u->p->right=v;
    	}
    	if(v!=NULL){
    		v->p=u->p;
    	}
    	return T;
    } 
    //找到树T中最小的元素
    Node *TREEMININUM(Node *T){
    	while(T->left!=NULL)
    		T=T->left;
    	return T;
    } 
    //删除树中某结点
    Node *deleteNode(Node *T,Node *z){
    	if(T->left==NULL){
    		T=TRANSPLANT(T,z,z->right);
    	}else if(T->right==NULL){
    		T=TRANSPLANT(T,z,z->left);
    	}else{
    		Node *y=TREEMININUM(z->right);
    		if(y->p!=z){
    			T=TRANSPLANT(T,y,y->right);
    			y->right=z->right;
    			y->right->p=y;
    		}
    		T=TRANSPLANT(T,z,y);
    		y->left=z->left;
    		y->left->p=y;
    	}
    	return T;
    } 
    
    int main(int argc, char *argv[])
    {
    	Node *T = NULL,*insert=NULL;
    	srand((unsigned)time(NULL));
    	int n;
    	scanf("%d",&n);
    	int *num=(int *)malloc(sizeof(int)*n);
    	int i=0;
    	for(;i<n;i++){
    		num[i]=rand()%100;
    		insert= (Node *)malloc(sizeof(Node));
    		insert->value=num[i];
    		insert->p=NULL;
    		T = insertNode(T,insert);
    	}
    	printf("\n------------随机生成的数------------\n");
    	int j=0;
    	for(;j<n;j++){
    		printf("%d\t",num[j]);
    	}
    	printf("\n------------二叉排序树的中序遍历------------\n");
    	inOrder(T);
    
    	printf("\n------------删除二叉排序树的某元素后中序遍历------------\n");
    	T = deleteNode(T,T);
    	inOrder(T);
    
    	printf("\n");
    	return 0;
    }

接下来我们分析一下，各模块的执行时间复杂度。

对于中序遍历void inOrder(Node \*t)，如果有n个结点，那么调用的时间为O(n)。

对于查找树T中最小的结点Node \*TREEMININUM(Node \*T)，如果有n个结点，那么调用的时间为O(lgn)。

对于插入结点Node \*insertNode(Node \*t,Node \*insert)，如果有n个结点，那么调用的时间为O(lgn)。

对于删除某结点Node \*deleteNode(Node \*T,Node \*z)，如果有n个结点，那么调用的时间为O(lgn)。

删除分三种情况：

1、删除结点没有孩子结点，则直接删除，并修改z的父结点，用NULL替换z。

2、删除结点有一个孩子，则将孩子结点提升到树中z的位置上，并修改z的父结点，用z的孩子替换z。

3、删除结点有两个孩子，首先找到z的后继y，并让y占据树中z的位置。在这里又分两种情况：

3.1、y是z的右孩子，那么直接y替换z，z的父结点成为y的父结点，z的左孩子成为y的左孩子。

3.2、y不是z的右孩子，那么先用y的右孩子替换y，而后用y替换z，并修改y的左右孩子等信息。

对于将一颗以v为根的子树来替换一颗以u为根的子树Node \*TRANSPLANT(Node \*T,Node \*u,Node \*v)，时间复杂度为O(1)。