[其它]數(shù)據(jù)結(jié)構(gòu)第9章-閱讀頁(yè)
2024-11-02 22:27本頁(yè)面
【正文】 struct BiTNode *lchild,*rchild。 45 12 53 3 37 100 90 24 61 78 CAO ZHAO DING CHEN WANG LI XIA DU MA 2. 二叉排序樹上的查找 二叉排序樹可看做是一個(gè)有序表 ， 在二叉排序樹上進(jìn)行查找 ,和折半查找類似 ,也是一個(gè)逐步縮小查找范圍的過程 。 else if (key Tkey) return SearchBST(Tlchild, key)。 /*在右子樹中遞歸查找 */ } BiTree SearchBST(BiTree T, KeyType key) { p = T。 else p = prchild。 } p amp。 pkey!=key ④ ① ② ③ p 3. 二叉排序樹的插入和生成 90281224 5345( g ) 插入 90281224 5345( f ) 插入 281224 5345( e ) 插入 1224 5345( d ) 插入 532445( c ) 插入 2445( b ) 插入 45( a ) 空樹關(guān)鍵字序列： {45, 24, 53, 45, 12, 28, 90} ?新插入的結(jié)點(diǎn)一定是個(gè)葉子結(jié)點(diǎn) int InsertBST(BiTree amp。 Tkey=key。 return 1。 else if(key Tkey) return InsertBST(Tlchild, key)。 /*插入到右子樹中 */ } ?在以 T為根結(jié)點(diǎn)的 BST中插入一個(gè)關(guān)鍵字為 key的結(jié)點(diǎn)。 //鍵值為 key的結(jié)點(diǎn)已經(jīng)存在 s = new BiTNode。 slchild = srchild = NULL。 else if (keyfatherkey) fatherrchild = s。 return 1。 father = NULL。amp。 if (keypkey) p = prchild。 }//while int InsertBST(BiTree amp。關(guān)鍵字?jǐn)?shù)組 A[0..n1]. BiTree CreatBST(KeyType A[], int n) /*返回樹根指針 */ { BiTree T = NULL。 while (in){ InsertBST(T, A[i])。 } return T。假設(shè)要?jiǎng)h除的結(jié)點(diǎn)為 p，結(jié)點(diǎn) p的雙親結(jié)點(diǎn)為 f。 此時(shí)有兩種處理方法： 方法 1： 將 p的左子樹改為 f的左子樹，而將 p的右子樹改為 s的右子樹。 CLC…Q LQSLSPPRF Status DeleteBST(BiTree amp。 else{ if(Tkey == key) return Delete(T)。 else return DeleteBST(Trchild, key)。 } } void Delete( BiTree amp。 p = plchild。 }//右子樹空 else if( !plchild) { q = p。 free(q)。 s = plchild。 s = srchild。 if(q!=p) qrchild = slchild。 free(s)。 若查找成功，則走了一條從根結(jié)點(diǎn)到某結(jié)點(diǎn)的路徑，若查找失敗，則走到一棵空的子樹時(shí)為止。 例：已知一組關(guān)鍵字為 {25,18,46,2,53,39,32,4,74,67,60,11}。 (不成功時(shí)的平均查找長(zhǎng)度 ASLunsucc) 25 18 46 39 53 2 4 11 32 74 67 60 12615243332211?????????????s uc cA S L 25 18 46 39 53 2 4 11 32 74 67 60 136253443321???????????uns uc cA S L?作業(yè)：
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1