夕拾算法进阶篇：24)二叉树排序树

二叉排序树的定义

二叉排序树又称为排序二叉树、二叉搜索树，它的递归定义如下：

(1)要么二叉排序树是一棵空树。

(2)要么二叉排序树由根节点、左子树、右子树组成，其中左右子树都是二叉排序树，且左子树上所有节点的数据域均小于或等于根节点，右子树的所有节点的数据域均大于根节点。

二叉排序树的基本操作

二叉排序树建立

对一棵二叉排序树来说，插入的过程就是查找的过程，当查找失败即root==NULL的时候就是插入的地方。

树结构的定义：

//树结构定义 struct Node{	int data;	Node *lchild,*rchild; 	 }; //简单封装下新建节点的操作 Node* newNode(int x){	Node* n=new Node();	n->data=x;	n->lchild=n->rchild=NULL; }二叉树排序的插入操作：
//在二叉排序树中插入数据域为x的新节点(注意root必须要添加&引用) void insert(Node* &root,int x){	if(root==NULL){ //空树查找失败，即插入的位置 		root=newNode(x); 	}else if(root->data>=x){//x节点比根节点小，说明x需要插在左子树 		insert(root->lchild,x);//往左子树搜索x 	}else {//x节点比根节点大，说明x需要插在右子树 		insert(root->rchild,x);//往右子树搜索x 	}}二叉排序树的建立过程就是不断插入的过程：
int a[6]={1,3,5,4,6,2};Node *root=NULL; //root初始为空 for(int i=0;i<6;i++){	insert(root,a[i]);}
二叉排序树的删除
如下图所示要删除根节点5，那应该怎么做呢？为了保证删除之后仍然是一棵二叉排序树，一种办法是以树种比5小的最大节点(也就是4节点，称为5节点的前驱节点)覆盖节点5，然后在删除节点4；另一种方法就是把树种比5大的最小节点(也就是节点6，称为5节点的后继节点)覆盖节点5，然后删除节点6。 (很明显，这又是一个递归的操作)首先实现找到root的节点的前驱或者后继节点，很明显root节点的前驱节点就是其左子树最靠右的节点，而后继节点就是右子树最靠左的节点。假设已经找到了待删除的节点x，则有以下几种情况：(1)如果当前的节点x不存在左右孩子，说明是叶子节点，直接删除(2)如果当前的节点x存在左孩子，那么在x的左子树中找到x的前驱节点PRe，然后让节点pre覆盖x节点的值，接着再删除pre节点(3)如果当前的节点x存在右孩子，那么在x的右子树中找到x的后继节点next，然后让节点next覆盖x节点的值，接着再删除next节点
//查找root节点的最小权值结点 Node* findMin(Node *root){	while(root->lchild){		root=root->lchild;	}	return root;} //查找root节点的最大权值结点 Node* findMax(Node *root){	while(root->rchild){		root=root->rchild;	}	return root;} //删除以root为根节点的树种权值为x的结点 Node* deleteNode(Node* &root,int x){ 	if(root){//树不为空		if(root->data==x){//找到了待删除结点 			if(root->lchild==NULL&&root->rchild==NULL){				root=NULL;			}else if(root->lchild){ //左孩子存在 				Node* pre=findMax(root->lchild);//获得当前结点的前驱  				root->data=pre->data; //覆盖当前root节点的值 				deleteNode(root->lchild,pre->data); //递归删除pre节点 			}else{//右孩子存在 				Node* next=findMin(root->rchild); //获得当前结点的后继 				root->data=next->data;//覆盖当前root节点的值				deleteNode(root->rchild,next->data); //递归删除next节点 			} 		}else if(root->data>x){//节点x在当前节点的左子树上 			deleteNode(root->lchild,x);		}else{//节点x在当前节点的右子树上 				deleteNode(root->rchild,x);		} 	}}这里注意一个问题：在递归删除当前root结点的前驱时deleteNode(root->lchild,pre->data)，第一个参数如果直接使用pre，是没有效果的。因为C++的引用类似于变量的别名，若使用pre在deleteNode中操作root实际上是操作的是pre，而不是root->lchild！上面的代码递归删除前驱和后继的代码还可以优化，比如上图如用节点6来取代root结点，此时结点6已然无左子树，而让结点6的右子树(若存在，为空亦可)取代结点6即可，因此在findMin中需要记录前驱结点的父节点以便进行删除操作。但注意这种情况，如果删除的是结点3，而使用结点2进行取代，但结点3的左子树只有一个结点(没有进入findMax的while循环)，因此只需root->lchild=NULL即可。
//查找root节点的最小权值结点 Node* findMin(Node *root,Node* &father){	while(root->lchild){		father=root;//记录父节点		root=root->lchild;	}	return root;} //查找root节点的最大权值结点 Node* findMax(Node *root,Node* &father){	while(root->rchild){		father=root;		root=root->rchild;	}	return root;} //删除以root为根节点的树种权值为x的结点 Node* deleteNode(Node* &root,int x){ 	if(root){//树不为空		if(root->data==x){//找到了待删除结点 			if(root->lchild==NULL&&root->rchild==NULL){				root=NULL;			}else if(root->lchild){ //左孩子存在 				Node* f=root;//记录前驱节点的父节点 				Node* pre=findMax(root->lchild,f);//获得当前结点的前驱  				root->data=pre->data; //覆盖当前root节点的值 				if(f==root){//说明root的左子树只有一个结点 					f->lchild=NULL; //直接删掉该结点 				}else{ //让前驱节点(f->rchild)的左子树取代前驱结点 					f->rchild=f->rchild->lchild;					}			}else{//右孩子存在 				Node* f=root;//记录前驱节点的父节点 				Node* next=findMin(root->rchild,f); //获得当前结点的后继 				root->data=next->data;//覆盖当前root节点的值				if(f==root){//说明root的右子树只有一个结点					f->rchild=NULL; //直接删掉该结点				}else{//让后继节点(f->lchild)的右子树取代后继节点 					f->lchild=f->lchild->rchild;					}			} 		}else if(root->data>x){//节点x在当前节点的左子树上 			deleteNode(root->lchild,x);		}else{//节点x在当前节点的右子树上 				deleteNode(root->rchild,x);		} 	}}