目錄

二叉查找樹的定義

二叉查找樹的基本操作

查找

插入

建立

刪除

二叉樹查找樹的性質

二叉查找樹的定義

二叉查找樹是一種特殊的二叉樹，又稱為排序二叉樹、二叉搜索樹、二叉排序樹。

二叉樹的遞歸定義如下：

（1）要么二叉查找樹是一棵空樹。

（2）要么二叉查找樹由根節點、左子樹、右子樹組成，其中左子樹和右子樹都是二叉查找樹，且左子樹上所以結點的數據域均小于或等于根節點的數據域，右子樹上的所有結點的數據域均大于根節點的數據域。

二叉查找樹的基本操作

查找

進行二叉樹的查找操作時，由于無法確定二叉樹的具體特性，因此只能對左右子樹都進行遞歸遍歷。但是二叉查找樹的性質決定了可以只選擇一棵子樹進行遍歷。因此查找將會是從根節點查找的一條路徑，故最壞時間復雜度是，其中h是二叉查找樹的高度。于是就可以得到查找操作的基本思路：

（1）如果當前根節點root為空，說明查找失敗，返回。

（2）如果需要查找的x等于當前根節點的數據域root->data，查找成功，訪問。

（3）如果需要查找的x小于當前根節點的數據域root->data，說明應該往左子樹查找，因此向root->lchild遞歸。

（4）如果需要查找的x大于當前結點的數據域root->data，則應該往右子樹查找，因此向root->rchild遞歸。

void search(node* root,int x){if(root==NULL){printf("search failed\n");return;}if(x==root->data){printf("%d\n",root->data);}else if(x<root->data){search(root->lchild,x);}else{search(root->rchild,x);}
}

可以看到，和普通二叉樹的查找函數不同，二叉查找樹的查找在于對左右子樹的選擇遞歸。在普通二叉樹中，無法確定需要查找的值x到底是在左子樹還是右子樹，但是在二叉查找樹中就可以確定，因為二叉查找樹中的數據域順序總是左子樹<根節點<右子樹。

插入

對一棵二叉查找樹來說，查找某個數據域的結點一定是沿著確定的路徑進行的。因此，當對某個需要查找的值在二叉查找樹中查找成功，說明結點已經存在。反之，如果這個需要查找的值在二叉查找樹中查找失敗，那么說明查找失敗的地方一定是結點需要插入的地方。因此可以在上面查找操作的基礎上，在root==NULL時新建需要插入的點。

void insert(node* &root,int x){if(root==NULL){root=newNode[x];return;}if(x==root->data){return;}else if(x<root->data){insert(root->lchild,x);}else{insert(root->rchild,x);}
}

建立

node* Create(int data[],int n){node* root=NULL;for(int i=0;i<n;i++){insert(root,data[i]);}return root;
}

需要注意的是，即使是一組相同的數字，如果插入它們的順序不同，最后生成的二叉查找樹也可能不同。

刪除

把二叉查找樹中比結點權值小的最大結點稱為該結點的前驅，而把比結點權值大的最小結點稱為該結點的后繼。顯然，結點的前驅是該結點左子樹的最右結點（也就是從左子樹根節點開始不斷沿著rchild往下直到rchild為NULL時的結點），而結點的后繼則是該結點右子樹的最左節點（也就是從右子樹根節點開始不斷沿著lchild往下直到lchild為NULL時的結點）。下面兩個函數用來尋找以root為根的樹中最大或最小權值的結點，用以輔助尋找結點的前驅和后繼：

//尋找以root為根結點的樹中的最大權值結點 
node* findMax(node* root){while(root->rchild!=NULL){root=root->rchild;}return root;
}
//尋找以root為根結點的樹中的最小權值結點
node* findMin(node* root){while(root->lchild!=NULL){root=root->lchild;}return root;
} 

刪除操作的基本思路如下：

（1）如果當前結點root為空，說明不存在權值為給定權值x的結點，直接返回。

（2）如果當前結點root的權值恰為給定的權值x，說明找到了想要刪除的結點，此時進入刪除處理。如果當前結點root不存在左右孩子，說明是葉子節點，直接刪除。如果當前結點root存在左孩子，那么在左子樹中尋找結點前驅pre，然后讓前驅的數據覆蓋root，接著在左子樹中刪除結點pre。如果當前結點root存在右孩子，那么在右子樹中尋找結點后繼next，然后讓next的數據覆蓋root，接著在右子樹中刪除結點next。

（3）如果當前結點root的權值大于給定權值的x，則在左子樹中遞歸刪除權值為x的結點。

（4）如果當前結點root的權值小于給定權值的x，則在右子樹中遞歸刪除權值為x的結點。

//尋找以root為根結點的樹中的最大權值結點 
node* findMax(node* root){while(root->rchild!=NULL){root=root->rchild;}return root;
}
//尋找以root為根結點的樹中的最小權值結點
node* findMin(node* root){while(root->lchild!=NULL){root=root->lchild;}return root;
} 
void deleteNode(node* &root,int x){if(root==NULL){return;}if(root->data==x){if(root->lchild==NULL&&root->rchild==NULL){root==NULL;}else if(root->lchild!=NULL){node* pre=findMax(root->lchild);root->data=pre->data;deleteNode(root->lchild,pre->data);}else{node* next=findMin(root->rchild);root->data=next->data;deleteNode(root->rchild,next->data);}}else if(root->data>x){deleteNode(root->lchild,x);}else{deleteNode(root->rchild,x);}
}

但是也要注意，總是優先刪除前驅或后繼容易導致樹的左右子樹高度極度不平衡，使得二叉查找樹退化成一條鏈。解決這一問題的辦法有兩種：一種是每次交替刪除前驅或后繼；另一種是記錄子樹高度，總是優先在高度較高的一棵子樹里刪除結點。

二叉樹查找樹的性質

二叉查找樹一個實用的性質：對二叉查找樹進行中序遍歷，遍歷的結果是有序的。

另外，如果合理調整二叉查找樹的形態，使得樹上的每個結點都盡量有兩個子節點，這樣整個二叉查找樹的高度就會很低，也即樹的高度大概在的級別。

例題

給出N個正整數來作為一棵二叉排序樹的結點插入順序，問：這串序列是否是該二叉排序樹的先序序列或是該二叉排序樹的鏡像樹的先序序列。所謂鏡像樹是指交換二叉樹的所有結點的左右子樹而形成的樹（也即左子樹所有結點數據域大于或等于根節點，而根節點數據域小于右子樹所有結點的數據域）。如果是，則輸出YES，并輸出對應的樹的后序序列；否則，輸出NO。

思路

通過給定的插入序列，構建出二叉排序樹。對鏡像樹的先序遍歷只需要在原樹的先序遍歷時交換左右子樹的訪問順序即可。

//鏡像樹先序遍歷，結果存放于vi
void preordermirror(node* root,vector<int>&vi){if(root==NULL){return;}vi.push_back(root->data);preordermirror(root->right,vi);preordermirror(root->left,vi);
} 

注意點

使用vector來存放初始序列、先序序列、鏡像樹先序序列，可以方便相互之間的比較。若使用數組，則比較操作需要使用循環才能實現。

#include<cstdio>
#include<vector>
using namespace std;
struct node{int data;node* left,*right;
}; 
vector<int> origin,pre,preM,post,postM;
void insert(node* &root,int data){if(root==NULL){root=new node;root->data=data;root->left=root->right=NULL;return;}if(data<root->data){insert(root->left,data);}else{insert(root->right,data);}
}
void preorder(node* root,vector<int> &vi){if(root==NULL){return;}vi.push_back(root->data);preorder(root->left,vi);preorder(root->right,vi);
}
void preordermirror(node* root,vector<int> &vi){if(root==NULL){return;}vi.push_back(root->data);preordermirror(root->right,vi);preordermirror(root->left,vi);
}
void postorder(node* root,vector<int> &vi){if(root==NULL){return;}postorder(root->left,vi);postorder(root->right,vi);vi.push_back(root->data);
}
void postordermirror(node* root,vector<int> &vi){if(root==NULL){return;}postordermirror(root->right,vi);postordermirror(root->left,vi);vi.push_back(root->data);
}
int main(){int n,data;node* root=NULL;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&data);origin.push_back(data);insert(root,data);}preorder(root,pre);preordermirror(root,preM);postorder(root,post);postordermirror(root,postM);if(origin==pre){printf("YES\n");for(int i=0;i<post.size();i++){printf("%d",post[i]);if(i<post.size()-1){printf(" ");}}}else if(origin==preM){printf("YES\n");for(int i=0;i<postM.size();i++){printf("%d",postM[i]);if(i<postM.size()-1){printf(" ");}}}else{printf("NO\n");return 0;}
}