二叉排序樹C的實現，如何構造二叉排序樹

如果你不自己找出錯誤，你的能力永遠不會提高。

其他人可以幫你一段時間，但不能幫一輩子。

重要的不是故障，而是如何知道故障。

假設二進位排序樹 t 為空，則建立乙個關鍵字為 k 的節點。 將其用作根節點。

否則，將k與根節點的關鍵字進行比較，相等則返回，假設k小於根節點的關鍵字插入到根節點的左子樹中，否則插入到根節點的右子樹中。

int insertbst(bstnode *p, keytype k)

else if(k==p->key)

return 0;

else if(kkey)

return insertbst(p->lchild, k);

elsereturn insertbst(p->rchild, k);

生成二叉排序樹的演算法：

bstnode *createbst(keytype a,int n)

bstnode *bt=null;

int i=0;

while(i<>

當由於查詢失敗而需要插入資料元素時，資料元素的插入位置必須位於二叉排序樹的葉節點處，並且必須是搜尋失敗時訪問的最後乙個節點的左子節點或右子節點。

二叉排序樹也稱為二叉搜尋樹和二叉搜尋樹。 二叉排序樹是左子樹上的節點小於根節點，右子樹上的節點大於根節點，左右子樹也是二叉樹的二叉樹。

例項。 當要在二叉排序樹中插入乙個元素時，從根節點開始搜尋，首先取根節點作為當前節點，如果要插入的值小於當前節點的值，則判斷當前節點的左子節點是否為空，如果為空， 要插入的值將是當前節點的左子節點作為當前節點的左子節點，如果不為空，則當前節點的左子節點將繼續作為當前節點進行搜尋當待插入的值大於當前節點的值時，判斷當前節點的右子節點是否為空，如果為空，則待插入的值將作為當前節點的右子節點，如果不為空，則當前節點的右子節點將繼續作為當前節點進行搜尋。

節點定義。 遞迴實現。

非遞迴實現。

對於中階遍歷，遍歷的結構恰好是按公升序排列的數字序列。

遞迴寫作。 非遞迴寫作。

搜尋二叉排序樹時，從根節點開始搜尋，將根節點作為當前節點，如果當前節點的值等於搜尋的值，則搜尋結束並返回成功如果當前節點的值小於搜尋值，則判斷當前節點的左子節點是否為空，如果為空，則搜尋的值不在樹中，搜尋結束時返回失敗，如果不為空，則以當前節點的左子節點為當前節點並繼續搜尋; 如果當前節點的值大於搜尋值，則判斷當前節點的右子樹是否為空，如果為空，則搜尋的值不在樹中，搜尋結束，返回失敗，如果不為空，則使用當前節點的右子節點作為當前節點， 搜尋仍在繼續。

刪除二叉排序樹有三種基本方案。

您可以直接刪除該節點。

將要刪除的節點的子節點替換為當前節點。

在要刪除的節點的右子樹中找到最小的值，替換要刪除的節點，刪除最小的節點（也可以從左子樹中找到最大的節點）。

細節。 演算法實現：

二叉排序樹的搜尋時間與二叉樹的高度有關，高度越高，需要的搜尋時間就越多。

二叉排序樹的高度有兩種極端情況，一種是完整的二叉樹，另一種是每層只有乙個節點的情況，就變成了鍊表。

當它是乙個完整的二叉樹時：在這種情況下，時間複雜度是 o（log2n）。

當每層只有乙個節點時，即當鍊表被製作時：在這種情況下，時間複雜度為 o（n）。

o（n）。

邊看邊插值的方法類似於重新建立一維陣列o（n），因為深度不平衡，會發展成單鏈的形狀，深如一條線n點。

當樹中沒有關鍵字等於搜尋過程中給定值的節點時，將插入二叉排序樹。 如果查詢不成功，則新插入的節點必須是新新增的葉節點，並且是路徑上訪問的最後乙個節點的左節點或右節點。

因此，二叉排序樹插入的最大時間複雜度為 o（n）。 如果二叉排序樹是平衡的，則其時間複雜度降低，最小時間複雜度為 O（logn）。

二叉排序樹：空樹或具有以下屬性的二叉樹：

1.如果其左子樹不為空，則左子樹上所有節點的值小於其根節點的值;

2.如果其右子樹不為空，則右子樹上所有節點的值都大於其根節點的值;

3.它的左子樹和右子樹也分別是二元排序樹。

二叉樹的基本概念是可以理解的。

二叉排序樹，首先它是一棵樹，“二進位分叉”的描述已經很明顯了，也就是說樹上的乙個分支有兩個分叉，所以遞迴就是乙個二叉樹（如下圖所示），並且這個樹上的節點已經有序了，具體排序如下：

如果左邊的子樹不為空，則左邊子樹上所有節點的值都小於其根節點的值，如果右邊子樹不為空，則右邊所有節點的字數值大於其根節點的值，其左邊，右邊的子樹也是二進位排序的次數（遞迴定義）從圖中可以看出， 二叉排序樹在整理資料的時候，用它來查詢比較方便，因為每次經過乙個節點，可能性最多可以降低一半，但是在極端情況下，所有節點都位於同一側，直觀上是一條直線，所以這個查詢的效率比較低， 所以需要平衡二叉樹的左右子樹的高度，所以就有了平衡二叉樹（balenced binary）。樹）

我們所說的“平衡”，是指樹的枝條高度是均勻的，左右枝條高度的絕對差值小於1，這樣就不會出現一根枝條特別長的情況。 因此，在這樣乙個平衡樹中向上查詢時，比較節點的總數不超過樹的高度，這保證了查詢的效率（時間複雜度為o（logn））。