二叉排序樹的定義

二叉排序樹又稱為排序二叉樹、二叉搜索樹，它的遞歸定義如下：

(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);		} 	}}