二叉查找樹，又名二叉排序樹，亦名二叉搜索樹，一種常用的樹形數據結構 ...
一、數據結構背景+代碼變數介紹
二叉查找樹，又名二叉排序樹，亦名二叉搜索樹
它滿足以下定義：
1、任意節點的子樹又是一顆二叉查找樹，且左子樹的每個節點均小於該節點，右子樹的每個節點均大於該節點。
2、由1可推出，任意節點的左孩子小於該節點，右孩子大於該節點
以上討論的是左（右）孩子（子樹）存在的情況
它的中序遍歷是一個升序的排序
在參考代碼中，我們定義有：
主程式中，k代表插入或刪除或查找的節點的值
root，根節點位置；a[i]，第 i 號節點的值；cl[i]，第 i 號節點左孩子的位置；cr[i]，第 i 號節點右孩子的位置；fa[i]，父親節點位置；
二、中序遍歷
中序遍歷的求法採用遞歸，先遞歸它的左孩子，然後列印當前節點，最後遞歸它的右孩子（當左或右孩子存在時才進行遞歸）
如上圖的中序遍歷為 DBEAFC
時間複雜度O(n)
1 void mid(int x) 2 { 3 if (time[cl[x]]!=0) mid(cl[x]); 4 cout<<a[x]<<" "; 5 if (time[cr[x]]!=0) mid(cr[x]); 6 } 7 8 主程式中：mid(root);
三、插入節點
我們採用遇到相同的節點，使該節點計數器+1的辦法
先從根節點出發：
1、若當前節點小於插入的數，則遞歸進入其左兒子
若左兒子計數器為0，即不存在左兒子，則直接將數插入到左兒子
2、若當前節點大於插入的數，則遞歸進入其右兒子
若右兒子計數器為0，即不存在右兒子，則直接將數插入到右兒子
3、若當前節點等於插入的數，則直接將該節點計數器+1
樣例一
如上圖，將6插入該二叉樹
1、與根節點比較，小於根節點，進入左兒子
2、與2比較，大於2，進入右兒子
3、與5比較，大於5，進入右兒子，但因右兒子不存在，所以將6作為其右兒子
樣例二
如上圖，將1插入該二叉樹：
1、與根節點比較，小於8，進入左兒子
2、與2比較，小於2，進入左兒子，但因其左兒子不存在，所以將1作為其左兒子
時間複雜度O(log2n)
1 void ins(int i,int x) 2 { 3 if (root==0) 4 { 5 a[1]=x; 6 time[1]=root=1; 7 return; 8 } 9 if (x<a[i]) 10 { 11 if (time[cl[i]]==0) 12 { 13 cl[i]=top>0?s[top--]:++tail;14 a[cl[i]]=x; 15 fa[cl[i]]=i; 16 time[cl[i]]++; 17 cr[cl[i]]=cl[cl[i]]=0; 18 } 19 else ins(cl[i],x); 20 } 21 else if (x>a[i]) 22 { 23 if (time[cr[i]]==0) 24 { 25 cr[i]=top>0?s[top--]:++tail;26 a[cr[i]]=x; 27 fa[cr[i]]=i; 28 time[cr[i]]++; 29 cr[cr[i]]=cl[cr[i]]=0; 30 } 31 else ins(cr[i],x); 32 } 33 else 34 { 35 time[i]++; 36 } 37 } 38 39 主程式中：ser(root,k); root代表起始位置，k代表插入的值
四、查找節點
查找類似於插入
同樣從根節點出發，如果遇到了空節點，即計數器等於0的節點，直接返回0，表示未查找到
若該節點等於查找的值，則返回該節點的位置
若該節點大於查找的值，則向左兒子遞歸查找
若該節點小於查找的值，則向右兒子遞歸查找
此處說明，若當前節點為空節點，則說明小於（大於）該節點父親的值不存在，即未查找到
查找類似於線段樹思想，是一步步向下把範圍縮小，直到找到期望的值或無結果
樣例一
如上圖，需查找的值為5
1、查找根節點，5<8，進入左兒子
2、5>2，進入右兒子
3、5=5，查找到該節點，返回該節點的位置
若需查找的值為4時，在第3步會進入其左兒子，又因左兒子為空節點，則返回0，說明未查找到
時間複雜度O(log2n)
1 int sea(int i,int x) 2 { 3 if (time[i]==0) return 0; 4 if (a[i]==x) return i; 5 else if (a[i]>x) return ser(cl[i],x); 6 else return ser(cr[i],x); 7 } 8 9 主程式中：sea(root,k); root代表查找的起始位置，k代表查找的值
五、刪除節點
當需要刪除節點時，先查找改值所在的位置，然後再進行刪除
如果該節點計數器大於1，則只用把計數器-1
如果計數器等於1，即刪除後該節點不再存在，則根據兒子的數目分為三種情況：
1、沒有兒子：直接將該節點刪除
2、一個兒子：將該節點父親的左（右）兒子直接指向該節點的唯一的那個兒子
3、兩個兒子：在該節點的右子樹中尋找一個最小的值，然後用最小的那個節點替代該節點，最後刪除最小的節點
尋找最小節點具體方法：先將目前節點指向右兒子，然後尋找不斷指向目前節點的左兒子，直到沒有左兒子為止
因為需要刪除的最小節點肯定沒有左兒子，所以只需遞歸執行第1或第2種情況，即 del（最小節點位置，最小節點的值）具體請參考代碼
樣例一
刪除9節點：調用查找，查找到9的位置，因為它沒有兒子，可直接刪除
樣例二
刪除5節點：同樣查找5節點的位置，發現其有1個孩子，則將 5節點 的 父親2節點 的 右孩子 指向 5節點 的 孩子6節點，這樣就自動刪除了5節點
樣例三
刪除2節點：
1、查找到2節點的位置
2、把最小節點指向其右孩子
3、不斷尋找目前最小節點的左孩子，直到盡頭，找到最小節點
4、將最小節點的信息賦給2節點
5、按照刪除節點的方法刪除最小節點4節點
時間複雜度O(log2n)
1 void del(int k,int x) 2 { 3 int ct=0; 4 if (cl[k]!=0) ct++; 5 if (cr[k]!=0) ct++; 6 time[k]--; 7 if (time[k]==0) 8 { 9 if (ct==1) 10 { 11 s[++top]=k;12 if (k==root) 13 { 14 root=time[cr[k]]==0?cl[k]:cr[k]; 15 return; 16 } 17 if (x<a[fa[k]]) cl[fa[k]]=time[cr[k]]==0?cl[k]:cr[k]; 18 else cr[fa[k]]=time[cr[k]]==0?cl[k]:cr[k]; 19 } 20 else if (ct==2) 21 { 22 int s=cr[k]; 23 if (time[cl[s]]!=0) s=cl[s]; 24 time[k]=time[s]; 25 a[k]=a[s]; 26 del(s,a[s]); 27 } 28 else s[++top]=k;29 } 30 } 31 32 主程式中：del(sea(root,k),k); 先查找到需刪除的節點的位置，然後刪除k
六、空節點位置棧
在刪除節點的時候，會產生許多空節點
為了節省空間，我們會開一個棧來保存空節點的位置，當刪除某個節點後，把它空出來的位置壓入棧中
當插入節點時，先詢問棧頂top是否大於0，若棧中有元素，則把棧中的位置彈出，用該位置存放節點
若棧中沒有元素，表示前面沒有空的位置，則新開一個空間來存放節點，通過保存最大位置數的變數tail來控制最大位置
七、特殊情況
對於二叉查找樹會產生如下圖的情況
則所有操作的時間往往會被卡成線性O(n)，而利用平衡二叉樹、伸展樹、紅黑樹等等數據結構便會幫我們解決這個問題
版權所有，轉載請聯繫作者，違者必究
QQ：740929894
