解：
情況一：根節點
1>無孩子：則放回空
2>有一個孩子，則放回其孩子
3>有兩個孩子，則傳回其左孩子，将右孩子作為左子樹的最右邊的結點的右孩子；或者傳回右子樹，将左子樹作為右子樹的最左結點的左孩子。
情況二：非根結點
1>無孩子：直接删去
2>一個孩子：則将孩子代替自己接入父節點。
3>兩個孩子：
方法一：如果本身是左孩子，則将左子樹接入父節點，将右子樹作為左子樹最右結點的右孩子。
如果本身是右孩子，則将右子樹接入父節點，将左子樹作為右子樹最左結點的左孩子。
方法二：用直接前驅或者後繼來代替自己，再删除直接前驅或者後繼。
直接前驅為左子樹的最右結點；
直接後繼為右子樹的最左結點。
先将數組排序，再用兩個指針，一個指向數組頭，一個指向數組尾，
将指向内容相加，如果大于0，則右指針左移，
如果小于0，則左指針右移，如果等于0，則放回兩個數。
如果A,B在CD的同一側，或者C,D在AB的同一側，
則兩線段不相交。否則相交。
相關知識：
二叉排序樹的插入和删除：
與次優二叉樹相對，二叉排序樹是一種動态樹表。其特點是：樹的結構通常不是一次生成的，而是在查找過程中，當樹中不存在關鍵字等于給定值的節點時再進行插入。新插入的結點一定是一個新添加的葉子節點，并且是查找不成功時查找路徑上通路的最後一個結點的左孩子或右孩子結點。
下面引自：
1．二叉樹重要性質：
性質1 二叉樹第i層上的結點數目最多為2i-1(i≥1)。
證明：用數學歸納法證明：
歸納基礎：i=1時，有2i-1=20=1。因為第1層上隻有一個根結點，是以命題成立。
歸納假設：假設對所有的j(1≤j<i)命題成立，即第j層上至多有2j-1個結點，證明j=i時命題亦成立。
歸納步驟：根據歸納假設，第i-1層上至多有2i-2個結點。由于二叉樹的每個結點至多有兩個孩子，故第i層上的結點數至多是第i-1層上的最大結點數的2倍。即j=i時，該層上至多有2×2i-2=2i-1個結點，故命題成立。
性質2 深度為k的二叉樹至多有2k-1個結點(k≥1)。
證明：在具有相同深度的二叉樹中，僅當每一層都含有最大結點數時，其樹中結點數最多。是以利用性質1可得，深度為k的二叉樹的結點數至多為：
20+21+…+2k-1=2k-1
故命題正确。
性質3 在任意-棵二叉樹中，若終端結點的個數為n0，度為2的結點數為n2，則no=n2+1。
證明：因為二叉樹中所有結點的度數均不大于2，是以結點總數(記為n)應等于0度結點數、1度結點(記為n1)和2度結點數之和：
n=no+n1+n2 (式子1)
另一方面，1度結點有一個孩子，2度結點有兩個孩子，故二叉樹中孩子結點總數是：
nl+2n2
樹中隻有根結點不是任何結點的孩子，故二叉樹中的結點總數又可表示為：
n=n1+2n2+1 (式子2)
由式子1和式子2得到：
no=n2+1
滿二叉樹和完全二叉樹是二叉樹的兩種特殊情形。
1、滿二叉樹(FullBinaryTree)
一棵深度為k且有2k-1個結點的二又樹稱為滿二叉樹。
滿二叉樹的特點：
（1） 每一層上的結點數都達到最大值。即對給定的高度，它是具有最多結點數的二叉樹。
（2） 滿二叉樹中不存在度數為1的結點，每個分支結點均有兩棵高度相同的子樹，且樹葉都在最下一層上。
2、完全二叉樹(CompleteBinaryTree)
若一棵二叉樹至多隻有最下面的兩層上結點的度數可以小于2，并且最下一層上的結點都集中在該層最左邊的若幹位置上，則此二叉樹稱為完全二叉樹。
特點：
（1） 滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。
（2） 在滿二叉樹的最下一層上，從最右邊開始連續删去若幹結點後得到的二叉樹仍然是一棵完全二叉樹。
（3） 在完全二叉樹中，若某個結點沒有左孩子，則它一定沒有右孩子，即該結點必是葉結點。
性質4 具有n個結點的完全二叉樹的深度為
順序存儲結構
該方法是把二叉樹的所有結點按照一定的線性次序存儲到一片連續的存儲單元中。結點在這個序列中的互相位置還能反映出結點之間的邏輯關系。
1．完全二叉樹結點編号
（1）編号辦法
在一棵n個結點的完全二叉樹中，從樹根起，自上層到下層，每層從左至右，給所有結點編号，能得到一個反映整個二叉樹結構的線性序列。
【例】如下圖所示。
（2）編号特點
完全二叉樹中除最下面一層外，各層都充滿了結點。每一層的結點個數恰好是上一層結點個數的2倍。從一個結點的編号就可推得其雙親，左、右孩子，兄弟等結點的編号。假設編号為i的結點是ki(1≤i≤n)，則有：
①若i>1，則ki的雙親編号為 ；若i=1，則Ki是根結點，無雙親。
②若2i≤n，則Ki的左孩子的編号是2i；否則，Ki無左孩子，即Ki必定是葉子。是以完全二叉樹中編号 的結點必定是葉結點。
③若2i+1≤n，則Ki的右孩子的編号是2i+1；否則，Ki無右孩子。
④若i為奇數且不為1，則Ki的左兄弟的編号是i-1；否則，Ki無左兄弟。
⑤若i為偶數且小于n，則Ki的右兄弟的編号是i+1；否則，Ki無右兄弟。
2．完全二叉樹的順序存儲
将完全二叉樹中所有結點按編号順序依次存儲在一個向量bt[0..n]中。
其中：
bt[1．．n]用來存儲結點
bt[0]不用或用來存儲結點數目。
【例】表6.1是圖6.8所示的完全二叉樹的順序存儲結構，bt[0]為結點數目，b[7]的雙親、左右孩子分别是bt[3]、bt[l4]和bt[15]。
3．一般二叉樹的順序存儲
（1）具體方法
① 将一般二叉樹添上一些 "虛結點"，成為"完全二叉樹"
② 為了用結點在向量中的相對位置來表示結點之間的邏輯關系，按完全二叉樹形式給結點編号
③ 将結點按編号存入向量對應分量，其中"虛結點"用"∮"表示
【例】圖6-9中單支樹的順序存儲結構如下圖
（2）優點和缺點
① 對完全二叉樹而言，順序存儲結構既簡單又節省存儲空間。
② 一般的二叉樹采用順序存儲結構時，雖然簡單，但易造成存儲空間的浪費。
【例】最壞的情況下，一個深度為k且隻有k個結點的右單支樹需要2k-1個結點的存儲空間。
③在對順序存儲的二叉樹做插入和删除結點操作時，要大量移動結點。
鍊式存儲結構
1．結點的結構
二叉樹的每個結點最多有兩個孩子。用連結方式存儲二叉樹時，每個結點除了存儲結點本身的資料外，還應設定兩個指針域lchild和rchild，分别指向該結點的左孩子和右孩子。結點的結構為：
2．結點的類型說明
typedef char DataType； //使用者可根據具體應用定義DataType的實際類型
typedef struct node{
DataType data；
Struct node *lchild，*rchild； //左右孩子指針
}BinTNode； //結點類型
typedef BinTNode *BinTree；//BinTree為指向BinTNode類型結點的指針類型
3．二叉連結清單（二叉樹的常用鍊式存儲結構）
在一棵二叉樹中，所有類型為BinTNode的結點，再加上一個指向開始結點(即根結點)的BinTree型頭指針(即根指針)root，就構成了二叉樹的鍊式存儲結構，并将其稱為二叉連結清單。
【例】下面左圖所示二叉樹的二叉連結清單如下面中圖所示。
注意：
① 一個二叉連結清單由根指針root惟一确定。若二叉樹為空，則root=NULL；若結點的某個孩子不存在，則相應的指針為空。
② 具有n個結點的二叉連結清單中，共有2n個指針域。其中隻有n-1個用來訓示結點的左、右孩子，其餘的n+1個指針域為空。
4．帶雙親指針的二叉連結清單
經常要在二叉樹中尋找某結點的雙親時，可在每個結點上再加一個指向其雙親的指針parent，形成一個帶雙親指針的二叉連結清單。
【例】上面右圖是上面左圖所示的二叉樹的帶雙親指針的二叉連結清單。
當用線性表作為表的組織形式時，可以有三種查找法。其中以二分查找效率最高。但由于二分查
找要求表中結點按關鍵字有序，且不能用連結清單作存儲結構，是以，當表的插入或删除操作頻繁時，為維護表的有序性，勢必要移動表中很多結點。這種由移動結點引
起的額外時間開銷，就會抵消二分查找的優點。也就是說，二分查找隻适用于靜态查找表。若要對動态查找表進行高效率的查找，可采用下面介紹的幾種特殊的二叉
樹或樹作為表的組織形式。不妨将它們統稱為樹表。下面将分别讨論在這些樹表上進行查找和修改操作的方法。
二叉排序樹
1、二叉排序樹的定義
二叉排序樹(Binary SortTree)又稱二叉查找(搜尋)樹(Binary SearchTree)。其定義為：二叉排序樹或者是空樹，或者是滿足如下性質的二叉樹：
①若它的左子樹非空，則左子樹上所有結點的值均小于根結點的值；
②若它的右子樹非空，則右子樹上所有結點的值均大于根結點的值；
③左、右子樹本身又各是一棵二叉排序樹。
上述性質簡稱二叉排序樹性質(BST性質)，故二叉排序樹實際上是滿足BST性質的二叉樹。
2、二叉排序樹的特點
由BST性質可得：
（1） 二叉排序樹中任一結點x，其左(右)子樹中任一結點y(若存在)的關鍵字必小(大)于x的關鍵字。
（2） 二叉排序樹中，各結點關鍵字是惟一的。
實際應用中，不能保證被查找的資料集中各元素的關鍵字互不相同，是以可将二叉排序樹定義中BST性質(1)裡的"小于"改為"大于等于"，或将BST性質(2)裡的"大于"改為"小于等于"，甚至可同時修改這兩個性質。
（3） 按中序周遊該樹所得到的中序序列是一個遞增有序序列。
3、二叉排序樹的存儲結構
typedef int KeyType； //假定關鍵字類型為整數
typedef struct node { //結點類型
KeyType key； //關鍵字項
InfoType otherinfo； //其它資料域，InfoType視應用情況而定，下面不處理它
struct node *lchild，*rchild； //左右孩子指針
} BSTNode；
typedef BSTNode *BSTree； //BSTree是二叉排序樹的類型
4、二叉排序樹上的運算
（1）二叉排序樹的插入和生成
①二叉排序樹插入新結點的過程
在二叉排序樹中插入新結點，要保證插入後仍滿足BST性質。其插入過程是：
(a)若二叉排序樹T為空，則為待插入的關鍵字key申請一個新結點，并令其為根；
(b)若二叉排序樹T不為空，則将key和根的關鍵字比較：
(i)若二者相等，則說明樹中已有此關鍵字key，無須插入。
(ii)若key<T→key，則将key插入根的左子樹中。
(iii)若key>T→key，則将它插入根的右子樹中。
子樹中的插入過程與上述的樹中插入過程相同。如此進行下去，直到将key作為一個新的葉結點的關鍵字插入到二叉排序樹中，或者直到發現樹中已有此關鍵字為止。
②二叉排序樹插入新結點的遞歸算法
【參見參考書目】
③二叉排序樹插入新結點的非遞歸算法
void InsertBST(BSTree *Tptr，KeyTypekey)
{ //若二叉排序樹*Tptr中沒有關鍵字為key，則插入，否則直接傳回
BSTNode *f，*p=*TPtr； //p的初值指向根結點
while(p){ //查找插入位置
if(p->key==key)return；//樹中已有key，無須插入
f=p； //f儲存目前查找的結點
p=(key<p->key)?p->lchild：p->rchild；
//若key<p->key，則在左子樹中查找，否則在右子樹中查找
} //endwhile
p=(BSTNode *)malloc(sizeof(BSTNode))；
p->key=key； p->lchild=p->rchild=NULL； //生成新結點
if(*TPtr==NULL) //原樹為空
*Tptr=p； //新插入的結點為新的根
else //原樹非空時将新結點關p作為關f的左孩子或右孩子插入
if(key<f->key)
f->lchild=p；
else f->rchild=p；
} //InsertBST
④二叉排序樹的生成
二叉排序樹的生成，是從空的二叉排序樹開始，每輸入一個結點資料，就調用一次插入算法将它插入到目前已生成的二叉排序樹中。生成二叉排序樹的算法如下：
BSTree CreateBST(void)
{ //輸入一個結點序列，建立一棵二叉排序樹，将根結點指針傳回
BSTree T=NULL； //初始時T為空樹
KeyType key；
scanf("％d"，&key)； //讀人一個關鍵字
while(key){ //假設key=0是輸人結束标志
InsertBST(&T，key)； //将key插入二叉排序樹T
scanf("％d"，&key)；//讀人下一關鍵字
}
return T； //傳回建立的二叉排序樹的根指針
} //BSTree
⑤二叉排序樹的生成過程
輸入序列決定了二叉排序樹的形态。
二叉排序樹的中序序列是一個有序序列。是以對于一個任意的關鍵字序列構造一棵二叉排序樹，其實質是對此關鍵字序列進行排序，使其變為有序序列。"排序
樹"的名稱也由此而來。通常将這種排序稱為樹排序(TreeSort)，可以證明這種排序的平均執行時間亦為O(nlgn)。
對相同的輸入執行個體，樹排序的執行時間約為堆排序的2至3倍。是以在一般情況下，構造二叉排序樹的目的并非為了排序，而是用它來加速查找，這是因為在一個有序的集合上查找通常比在無序集合上查找更快。是以，人們又常常将二叉排序樹稱為二叉查找樹。
（2）二叉排序樹的删除
從二叉排序樹中删除一個結點，不能把以該結點為根的子樹都删去，并且還要保證删除後所得的二叉樹仍然滿足BST性質。
①删除操作的一般步驟
(1) 進行查找
查找時，令p指向目前通路到的結點，parent指向其雙親(其初值為NULL)。若樹中找不到被删結點則傳回，否則被删結點是*p。
(2) 删去*p。
删*p時，應将*p的子樹(若有)仍連接配接在樹上且保持BST性質不變。按*p的孩子數目分三種情況進行處理。
②删除*p結點的三種情況
(1)*p是葉子(即它的孩子數為0)
無須連接配接*p的子樹，隻需将*p的雙親*parent中指向*p的指針域置空即可。
(2)*p隻有一個孩子*child
隻需将*child和*p的雙親直接連接配接後，即可删去*p。
(3)*p有兩個孩子
先令q=p，将被删結點的位址儲存在q中；然後找*q的中
序後繼*p，并在查找過程中仍用parent記住*p的雙親位置。*q的中序後繼*p一定是*q的右子樹中最左下的結點，它無左子樹。是以，可以将删
③二叉排序樹删除算法
分析：
上述三種情況都能統一到情況(2)，算法中隻需針對情況(2)處理即可。
注意邊界條件：若parent為空，被删結點*p是根，故删去*p後，應将child置為根。
算法：
void DelBSTNode(BSTree *Tptr，KeyType key)
{//在二叉排序樹*Tptr中删去關鍵字為key的結點
BSTNode *parent=NUll，*p=*Tptr，*q，*child；
while(p){ //從根開始查找關鍵字為key的待删結點
if(p->key==key) break；//已找到，跳出查找循環
parent=p； //parent指向*p的雙親
p=(key<p->key)?p->lchild：p->rchild； //在關p的左或右子樹中繼續找
}
if(!p) return； //找不到被删結點則傳回
q=p； //q記住被删結點*p
if(q->lchild&&q->rchild)//*q的兩個孩子均非空，故找*q的中序後繼*p
for(parent=q，p=q->rchild； p->lchild； parent=p，p=p=->lchild)；
//現在情況(3)已被轉換為情況(2)，而情況(1)相當于是情況(2)中child=NULL的狀況
child=(p->lchild)?p->lchild：p->rchild；//若是情況(2)，則child非空；否則child為空
if(!parent) //*p的雙親為空，說明*p為根，删*p後應修改根指針
*Tptr=child； //若是情況(1)，則删去*p後，樹為空；否則child變為根
else{ //*p不是根，将*p的孩子和*p的雙親進行連接配接，*p從樹上被摘下
if(p==parent->lchild) //*p是雙親的左孩子
parent->lchild=child； //*child作為*parent的左孩子
elseparent->rchild=child； //*child作為 parent的右孩子
if(p!=q) //是情況(3)，需将*p的資料複制到*q
q->key=p->key； //若還有其它資料域亦需複制
} //endif
free(p)； /釋放*p占用的空間
} //DelBSTNode
（3）二叉排序樹上的查找
①查找遞歸算法
在二叉排序樹上進行查找，和二分查找類似，也是一個逐漸縮小查找範圍的過程。
遞歸的查找算法：
BSTNode *SearchBST(BSTree T，KeyType key)
{ //在二叉排序樹T上查找關鍵字為key的結點，成功時傳回該結點位置，否則傳回NUll
if(T==NULL||key==T->key)//遞歸的終結條件
return T； //T為空，查找失敗；否則成功，傳回找到的結點位置
if(key<T->key)
returnSearchBST(T->lchild，key)；
else
returnSearchBST(T->rchild，key)；//繼續在右子樹中查找
} //SearchBST
②算法分析
在二叉排序樹上進行查找時，若查找成功，則是從根結點出發走了一條從根到待查結點的路徑。若查找不成功，則是從根結點出發走了一條從根到某個葉子的路徑。
(1) 二叉排序樹查找成功的平均查找長度
在等機率假設下，下面(a)圖中二叉排序樹查找成功的平均查找長度為
在等機率假設下，(b)圖所示的樹在查找成功時的平均查找長度為：
ASLb=(1+2+3+4+5+6+7+8+9+10)/10=5.5
與二分查找類似，和關鍵字比較的次數不超過樹的深度。
(2)在二叉排序樹上進行查找時的平均查找長度和二叉樹的形态有關
二分查找法查找長度為n的有序表，其判定樹是惟一的。含有n個結點的二叉排序樹卻不惟一。對于含有同樣一組結點的表，由于結點插入的先後次序不同，所構成的二叉排序樹的形态和深度也可能不同
【例】下圖(a)所示的樹，是按如下插入次序構成的：
45，24，55，12，37，53，60，28，40，70
下圖(b)所示的樹，是按如下插入次序構成的：
12，24，28，37，40，45，53，55，60，70
在二叉排序樹上進行查找時的平均查找長度和二叉樹的形态有關：
①在最壞情況下，二叉排序樹是通過把一個有序表的n個結點依次插入而生成的，此時所得的二叉排序樹蛻化為棵深度為n的單支樹，它的平均查找長度和單連結清單上的順序查找相同，亦是(n+1)/2。
②在最好情況下，二叉排序樹在生成的過程中，樹的形态比較勻稱，最終得到的是一棵形态與二分查找的判定樹相似的二叉排序樹，此時它的平均查找長度大約是lgn。
③插入、删除和查找算法的時間複雜度均為O(lgn)。
(3)二叉排序樹和二分查找的比較
就平均時間性能而言，二叉排序樹上的查找和二分查找差不多。
就維護表的有序性而言，二叉排序樹無須移動結點，隻需修改
指針即可完成插入和删除操作，且其平均的執行時間均為O(lgn)，是以更有效。二分查找所涉及的有序表是一個向量，若有插入和删除結點的操作，則維護表
的有序性所花的代價是O(n)。當有序表是靜态查找表時，宜用向量作為其存儲結構，而采用二分查找實作其查找操作；若有序表裡動态查找表，則應選擇二叉排
序樹作為其存儲結構。
(4)平衡二叉樹
為了保證二叉排序樹的高度為lgn，進而保證然二叉排序樹
上實作的插入、删除和查找等基本操作的平均時間為O(lgn)，在往樹中插入或删除結點時，要調整樹的形态來保持樹的"平衡。使之既保持BST性質不變又
保證樹的高度在任何情況下均為O(lgn)，進而確定樹上的基本操作在最壞情況下的時間均為O(lgn)。
注意：
①平衡二叉樹(Balanced Binary Tree)是指樹中任一結點的左右子樹的高度大緻相同。
②任一結點的左右子樹的高度均相同(如滿二叉樹)，則二叉樹是完全平衡的。通常，隻要二叉樹的高度為O(1gn)，就可看作是平衡的。
③平衡的二叉排序樹指滿足BST性質的平衡二叉樹。
④AVL樹中任一結點的左、右子樹的高度之差的絕對值不超過1。在最壞情況下，n個結點的AVL樹的高度約為1.44lgn。而完全平衡的二叉樹度高約為lgn，AVL樹是接近最優的。
微信公衆号：
<a target="_blank" href="https://yqfile.alicdn.com/img_e00999465d1c2c1b02df587a3ec9c13d.jpg">猿人谷</a>
如果您認為閱讀這篇部落格讓您有些收獲，不妨點選一下右下角的【推薦】
如果您希望與我交流互動，歡迎關注微信公衆号
本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接。
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)