博客園傳送門：https://www.cnblogs.com/yx1999/p/10352828.html
排序二叉樹
二叉樹我們已經(jīng)非常熟悉了全蝶，但是除了尋常的儲存、遍歷芽卿，我們還能用二叉樹做什么呢揭芍？
我們都知道不同的遍歷方式會對相同的樹中產(chǎn)生不同的序列結(jié)果，排序二叉樹就是利用二叉樹的遍歷特征實現(xiàn)的特殊樹種卸例。
排序二叉樹從根結(jié)點起的每一個結(jié)點的左子樹元素均小于其自身沼沈，右子樹元素值均大于其自身
即任何結(jié)點的值均大于其左子樹所有元素，均小于其右子樹所有元素
如：
就是一個排序二叉樹币厕，直觀的一批列另，從子樹到根結(jié)點，永遠符合左小右大的規(guī)則（中序遍歷）
Ⅰ旦装、結(jié)構(gòu)定義
排序二叉樹的定義與一般二叉樹無異
Ⅱ页衙、排序二叉樹的查找
我們先來看一下排序二叉樹的查找實現(xiàn)，因為插入在排序二叉樹中是實現(xiàn)后續(xù)建立阴绢、刪除結(jié)點的基礎(chǔ)店乐，因為結(jié)點帶有順序，故而遍歷條件有所改變呻袭，代碼如下：
清爽遞歸眨八，不解釋
Ⅲ、二叉排序樹的插入
代碼在這里：
這個插入上來先判斷一哈我們現(xiàn)有的樹里面有沒有這個元素左电，如果有就不會進入循環(huán)廉侧，至于插入操作的框架也基本符合中序遍歷的操作，只是加上了判斷大小
Ⅳ篓足、二叉排序樹刪除結(jié)點（HARD）
輕松愉快的建立段誊、查找排序二叉樹的操作完成之后，我們來看看比較困難的刪除排序二叉樹結(jié)點的操作栈拖。為什么說它困難呢连舍，相比插入或者查找，刪除面對的是一個已經(jīng)成型的樹涩哟，我們不僅要考慮怎樣去掉這個結(jié)點索赏，還要想到按照中序以及數(shù)字大小將原有結(jié)點按序放到正確位置。
好的贴彼，我們先來考慮一下我們可能刪除哪幾種結(jié)點：
第一類：待刪除結(jié)點只有左子樹潜腻，沒有右子樹，可以想見锻弓，這種情況下只需要把后續(xù)的左子樹接到待刪除結(jié)點的上一個結(jié)點上砾赔，再釋放待刪除結(jié)點的空間就OK
第二類：帶刪除結(jié)點只有右子樹蝌箍，沒有左子樹青灼，跟第一類一個道理暴心，這樣的操作只需要三行就解決，但是棘手的問題總在短暫的輕松過后
第三類：這一類情況就是大魔王遼杂拨，左右孩子一個不缺专普，手心手背都是肉，哪個也不能少弹沽，怎么解決這個問題呢檀夹？讓我們來看一個例子。
看這個丑不拉嘰的排序二叉樹策橘，非常體現(xiàn)中序遍歷特點
現(xiàn)在我們要刪除 34 這個結(jié)點炸渡，就是我們剛才說的那種第三類情況，左右均有結(jié)點丽已，這個時候蚌堵，我們有這兩種方法闊以達成目的
第一種：姑且叫他 犧牲前驅(qū)法 ，我們要去掉 34 沛婴，就要把他的前驅(qū)拿來頂替這個位置吼畏，保持二叉排序樹的序，然后當然要檢測一下嘁灯，如果犧牲的這個前驅(qū)點（在我們這里是 33 ）有子樹泻蚊，還需要把子樹和上一級連上（如32），這是第一種方法
1丑婿、用直接前驅(qū) 33 替換 34?
2性雄、刪除原有的 33 結(jié)點
3、把結(jié)點 32 羹奉，移到原 33 位置
第二種：相信你也猜到了毅贮，犧牲后繼法，反正兄弟兩個要挑一個頂上去尘奏，讓我們看一哈在這個例子中滩褥，怎么個犧牲后繼
?35 已經(jīng)被我們放上來遼?
1、用直接后繼 35 替換 34
2炫加、刪除結(jié)點 35?
因為這里的 35 煢煢孑立瑰煎，沒兒沒女，所以這個例子的這里不需要連接子樹俗孝，但是千萬注意不要認為所有的替換后繼法都不用管子樹
好的酒甸，方法講明白了遼，我們代碼實現(xiàn)一哈
解讀見注釋
測試用主函數(shù)部分：
