一、數據結構背景+代碼變量介紹
二叉查找樹，又名二叉排序樹，亦名二叉搜索樹
它滿足以下定義：
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
