c++模板實現(xiàn)的叉排序樹

1、C模板實現(xiàn)的二叉排序（查找）樹二叉排序樹定義：二叉排序樹定義：二叉排序樹是這樣的樹，結(jié)點左邊的值都小于結(jié)點的值，結(jié)點右邊的值都大于結(jié)點的值，所以按照二叉樹的中序遍歷的話，得到的的將是按順序排列的值。二叉排序樹的主要操作：二叉排序樹的主要操作：1：插入：插入插入的操作非常簡單，從根結(jié)點開始，如果插入值大于根節(jié)點值，則向右遍歷，如果小于根節(jié)點值，則想左遍歷，知道遇到一個葉子結(jié)點為止。按插入值大于葉子則將插入值作為葉子結(jié)點的右孩子，否則左孩子

2、。中間過程中如果遇到跟插入值相等的，則插入失敗。2：刪除：刪除關(guān)于有三種情況需要不同對待。如果是葉子結(jié)點，那么直接刪除就行（注意相關(guān)的孩子指針要變成NULL）。如果要刪除的結(jié)點只有左孩子或者右孩子，這樣也好辦，我們只需要把相應(yīng)的孩子賦值給待刪除結(jié)點的雙親結(jié)點的孩子指針即可，孫子升級當兒子。如果要刪除的結(jié)點既有左孩子，又有右孩子，那么情況就稍微有點麻煩，在這里我們可以采取兩種策略來實現(xiàn)，第一種是“前驅(qū)不動，移動右孩子法”，第二種是“右孩子

3、不動，移動前驅(qū)法”。具體如下圖所示：3：遍歷：遍歷遍歷采用遞歸方法，遍歷的實現(xiàn)就很簡單了。4：清除：清除在清除樹的所有結(jié)點的時候，采取了遞歸思想，判斷左孩子是否為空，如果不空則清空做孩子；再判斷右孩子是否為空，不為空則清空右孩子；只有當結(jié)點左右孩子結(jié)點都為空的時候，才釋放該結(jié)點的空間。5：查找：查找查找要利用二叉排序樹的自身優(yōu)點來進行，每次根據(jù)與結(jié)點的比較結(jié)果選擇再繼續(xù)跟左孩子比較還是跟右孩子比較。templateBSTrees::BS