數(shù)據(jù)結(jié)構(gòu)第九章 查找part4

1、 (1) 若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；1.二叉排序樹二叉排序樹(二叉查找樹二叉查找樹)定義：定義： 二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹： (3) 它的左、右子樹也都分別是二叉排序樹。 (2) 若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；2二叉排序樹的查找算法：二叉排序樹的查找算法：1) 若給定值等于等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功查找成功； 2) 若給定值小于小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子繼續(xù)在左子樹上進(jìn)行查找；樹上進(jìn)行查找；3) 若給定值大于大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右繼續(xù)在右子樹上進(jìn)行查找。子樹上進(jìn)行查找。否則， 若二叉排序樹

2、為空為空，則查找不成功查找不成功；50308020908540358832例如例如:二叉排序樹二叉排序樹查找關(guān)鍵字查找關(guān)鍵字= 50 ,505035 ,503040355090 ,50809095 ,從上述查找過程可見，從上述查找過程可見，在查找過程中，生成了一條查找路徑查找路徑： 從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點(diǎn)層向下直至關(guān)鍵字等于給定值的結(jié)點(diǎn);或者 從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹為止。層向下直至指針指向空樹為止。 查找成功查找成功 查找不成功查找不成功算法描述如下

3、：算法描述如下：Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p ) / 在根指針在根指針 T 所指二叉排序樹中遞歸地查找其所指二叉排序樹中遞歸地查找其 / 關(guān)鍵字等于關(guān)鍵字等于 key 的數(shù)據(jù)元素，若的數(shù)據(jù)元素，若查找成功查找成功， / 則返回指針則返回指針 p 所指該數(shù)據(jù)元素的結(jié)點(diǎn)，并返回所指該數(shù)據(jù)元素的結(jié)點(diǎn)，并返回 / 函數(shù)值為函數(shù)值為 TRUE; / SearchBST 否則表明否則表明查找不成功查找不成功，返回，返回 / 指針指針 p所指查找路徑上訪問的最后一個結(jié)點(diǎn)，所指查找路徑上訪問的最后一個結(jié)點(diǎn)， / 并返回

4、函數(shù)值為并返回函數(shù)值為FALSE, 指針指針 f 指向當(dāng)前訪問指向當(dāng)前訪問 / 的結(jié)點(diǎn)的雙親，其初始調(diào)用值為的結(jié)點(diǎn)的雙親，其初始調(diào)用值為NULLif (!T)else if ( EQ(key, T-data.key) ) else if ( LT(key, T-data.key) ) else p = f; return FALSE; / 查找不成功查找不成功 p = T; return TRUE; / 查找成功查找成功SearchBST (T-lchild, key, T, p ); / 在左子樹中繼續(xù)查找在左子樹中繼續(xù)查找SearchBST (T-rchild, key, T, p );

5、/ 在右子樹中繼續(xù)查找在右子樹中繼續(xù)查找30201040352523fT設(shè) key = 48fTfT22pfTfTTTTfffp 根據(jù)動態(tài)查找表的定義，“插入插入”操作在操作在查找不成功查找不成功時才進(jìn)行時才進(jìn)行；3二叉排序樹的插入算法二叉排序樹的插入算法 若二叉排序樹為空樹空樹，則新插入的結(jié)點(diǎn)為新的根結(jié)點(diǎn)新的根結(jié)點(diǎn)；否則，新插入的結(jié)點(diǎn)必為一個新的葉子結(jié)點(diǎn)新的葉子結(jié)點(diǎn)，其插入位置插入位置由查找過程得到。Status Insert BST(BiTree &T, ElemType e ) / 當(dāng)二叉排序樹中不存在關(guān)鍵字等于當(dāng)二叉排序樹中不存在關(guān)鍵字等于 e.key 的的 / 數(shù)據(jù)元素時，插入元素值

6、為數(shù)據(jù)元素時，插入元素值為 e 的結(jié)點(diǎn)，并返的結(jié)點(diǎn)，并返 / 回回 TRUE; 否則，不進(jìn)行插入并返回否則，不進(jìn)行插入并返回FALSE if (!SearchBST ( T, e.key, NULL, p ) else return FALSE; / Insert BST s = (BiTree) malloc (sizeof (BiTNode); / 為新結(jié)點(diǎn)分配空間為新結(jié)點(diǎn)分配空間s-data = e; s-lchild = s-rchild = NULL; if ( !p ) T = s; / 插入插入 s 為新的根結(jié)點(diǎn)為新的根結(jié)點(diǎn)else if ( LT(e.key, p-data.k

7、ey) ) p-lchild = s; / 插入插入 *s 為為 *p 的左孩子的左孩子else p-rchild = s; / 插入插入 *s 為為 *p 的右孩子的右孩子return TRUE; / 插入成功插入成功(1) 被刪除的結(jié)點(diǎn)是葉子；(2) 被刪除的結(jié)點(diǎn)只有左子樹或者只有右子樹；(3) 被刪除的結(jié)點(diǎn)既有左子樹，也有右子樹。4二叉排序樹的刪除算法二叉排序樹的刪除算法可分三種情況討論： 和插入相反，刪除在查找成功查找成功之后進(jìn)行，并且要求在刪除二叉排序樹上某個結(jié)點(diǎn)之后，仍然保持二叉排序樹的特性仍然保持二叉排序樹的特性。50308020908540358832(1) 被刪除的結(jié)點(diǎn)是葉子

8、結(jié)點(diǎn)葉子結(jié)點(diǎn)例如例如:被刪關(guān)鍵字被刪關(guān)鍵字 = 2088其雙親結(jié)點(diǎn)中相應(yīng)指針域的值改為其雙親結(jié)點(diǎn)中相應(yīng)指針域的值改為“空空”50308020908540358832(2) 被刪除的結(jié)點(diǎn)只有左子樹只有左子樹或者只有右子樹只有右子樹 其雙親結(jié)點(diǎn)的相應(yīng)指針域的值改為其雙親結(jié)點(diǎn)的相應(yīng)指針域的值改為 “指向指向被刪除結(jié)點(diǎn)的左子樹或右子樹被刪除結(jié)點(diǎn)的左子樹或右子樹”。被刪關(guān)鍵字被刪關(guān)鍵字 = 408050308020908540358832(3) 被刪除的結(jié)點(diǎn)既有左子樹，也有右子樹既有左子樹，也有右子樹4040以其前驅(qū)替代之，然以其前驅(qū)替代之，然后再刪除該前驅(qū)結(jié)點(diǎn)后再刪除該前驅(qū)結(jié)點(diǎn)被刪結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)被刪關(guān)鍵

9、字被刪關(guān)鍵字 = 50Status DeleteBST (BiTree &T, KeyType key ) / 若二叉排序樹若二叉排序樹 T 中存在其關(guān)鍵字等于中存在其關(guān)鍵字等于 key 的的 / 數(shù)據(jù)元素，則刪除該數(shù)據(jù)元素結(jié)點(diǎn)，并返回?cái)?shù)據(jù)元素，則刪除該數(shù)據(jù)元素結(jié)點(diǎn)，并返回 / 函數(shù)值函數(shù)值 TRUE，否則返回函數(shù)值，否則返回函數(shù)值 FALSE if (!T) return FALSE; / 不存在關(guān)鍵字等于不存在關(guān)鍵字等于key的數(shù)據(jù)元素的數(shù)據(jù)元素 else / DeleteBST算法描述如下：算法描述如下： if ( EQ (key, T-data.key) ) / 找到關(guān)鍵字等于找到關(guān)鍵

10、字等于key的數(shù)據(jù)元素的數(shù)據(jù)元素else if ( LT (key, T-data.key) ) else Delete (T); return TRUE; DeleteBST ( T-lchild, key ); / 繼續(xù)在左子樹中進(jìn)行查找繼續(xù)在左子樹中進(jìn)行查找DeleteBST ( T-rchild, key ); / 繼續(xù)在右子樹中進(jìn)行查找繼續(xù)在右子樹中進(jìn)行查找void Delete ( BiTree &p ) / 從從二叉排序樹中刪除結(jié)點(diǎn)二叉排序樹中刪除結(jié)點(diǎn) p， / 并重接它的左子樹或右子樹并重接它的左子樹或右子樹 if (!p-rchild) else if (!p-lchild)

11、 else / Delete其中刪除操作刪除操作過程如下所描述： / 右子樹為空樹則只需重接它的左子樹右子樹為空樹則只需重接它的左子樹q = p; p = p-lchild; free(q);pp/ 左子樹為空樹只需重接它的右子樹左子樹為空樹只需重接它的右子樹q = p; p = p-rchild; free(q);ppq = p; s = p-lchild;while (!s-rchild) q = s; s = s-rchild; / s 指向被刪結(jié)點(diǎn)的前驅(qū)指向被刪結(jié)點(diǎn)的前驅(qū)/ 左右子樹均不空左右子樹均不空p-data = s-data;if (q != p ) q-rchild = s-

12、lchild; else q-lchild = s-lchild; / 重接重接*q的左子樹的左子樹free(s);pqs結(jié)論：結(jié)論： 一個無序序列可以通過構(gòu)造一棵二叉一個無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個有序序列，構(gòu)造樹的過程排序樹而變成一個有序序列，構(gòu)造樹的過程即為對無序序列進(jìn)行排序的過程；即為對無序序列進(jìn)行排序的過程； 每次插入的新結(jié)點(diǎn)都是二叉排序樹的每次插入的新結(jié)點(diǎn)都是二叉排序樹的葉子結(jié)點(diǎn)，在進(jìn)行插入操作時，不必移動其葉子結(jié)點(diǎn)，在進(jìn)行插入操作時，不必移動其它結(jié)點(diǎn)，僅需修改某個結(jié)點(diǎn)的指針由空變?yōu)樗Y(jié)點(diǎn)，僅需修改某個結(jié)點(diǎn)的指針由空變?yōu)榉强占纯?。這就相當(dāng)于在一個有序序列上插非空即可

13、。這就相當(dāng)于在一個有序序列上插入一個元素而沒有移動其它元素。這個特性入一個元素而沒有移動其它元素。這個特性告訴我們，對于需要經(jīng)常插入和刪除記錄的告訴我們，對于需要經(jīng)常插入和刪除記錄的有序表采用二叉排序樹結(jié)構(gòu)更為合適。有序表采用二叉排序樹結(jié)構(gòu)更為合適。5查找性能的分析查找性能的分析 對于每一棵特定的二叉排序樹，均可按照平均查找長度的定義來求它的 ASL 值，顯然，由值相同的 n 個關(guān)鍵字，構(gòu)造所得的不同形態(tài)的各棵二叉排序樹的平均查找長度的值不同，甚至可能差別很大。由關(guān)鍵字序列由關(guān)鍵字序列 3，1，2，5，4構(gòu)造而得的二叉排序樹，構(gòu)造而得的二叉排序樹，由關(guān)鍵字序列由關(guān)鍵字序列 1，2，3，4，5構(gòu)造而得的二叉排序樹，構(gòu)造而得的二叉排序樹，例如：例如：2134535412ASL =（1+2+3+4+5）/ 5 = 3ASL =（1+2+3+2+3）/ 5 = 2.2 下面討論平均情況下面討論平均情況: 不失一般性，假設(shè)長度為 n 的序列中有 k 個關(guān)鍵字小于小于第一個關(guān)鍵字，則必有 n-k-1 個關(guān)鍵字大于大于第一個關(guān)鍵字,由它構(gòu)造的二叉排序樹n-k-1k的平均查找長度是 n 和 k 的函數(shù)P(n, k) ( 0 k n-1 )。 假設(shè) n 個關(guān)鍵字可能出現(xiàn)的 n! 種排列的可能性相同，則含 n 個關(guān)