數(shù)據(jù)結(jié)構(gòu)算法之樹(shù)的應(yīng)用-資料下載頁(yè)
2025-04-29 08:39本頁(yè)面
【正文】 還是 “全 ”線(xiàn)索化（前驅(qū)后繼都要）； ? 三是只有空指針處才能加線(xiàn)索。 二叉搜索樹(shù) ?二叉 搜索 樹(shù)又稱(chēng)為二叉排序樹(shù)，其定義是一個(gè)遞歸過(guò)程： ? 它或者是一棵空樹(shù)；或者是具有下列性質(zhì)定義的二叉樹(shù)： ?⑴ 若左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；若右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于或等于根結(jié)點(diǎn)的值。 ?⑵ 左右子樹(shù)都分別是一棵二叉 搜索 樹(shù) 。 ? 中序 遍歷二叉搜索樹(shù)可以得到解決一個(gè)按關(guān)鍵字有序的序列。 ? 構(gòu)造二叉搜索樹(shù)的目的不是為了排序，而是用來(lái)加速查找。 ? 二叉 搜索 樹(shù)的建立： ? 由空集為初始狀態(tài) ， 將結(jié)點(diǎn)按關(guān)鍵字依次插入到二叉樹(shù)中去 。 先將第一個(gè)結(jié)點(diǎn)作為二叉樹(shù)的根結(jié)點(diǎn) ， 插入其它結(jié)點(diǎn)時(shí) ， 若結(jié)點(diǎn)的值小于根結(jié)點(diǎn)的值 ， 則插入左子樹(shù) ， 否則插入右子樹(shù) ，該過(guò)程依次進(jìn)行 ， 直到整個(gè)過(guò)程結(jié)束 。 ? 動(dòng)態(tài)生成二叉排樹(shù)時(shí) ， 樹(shù)的形狀 、 高度不僅依賴(lài)于記錄 關(guān)鍵字 的大小 ， 還與記錄輸入的 先后順序 有關(guān) {70， 35， 85， 20， 70， 90} 70 35 85 20 70 90 {20 ， 35， 70 ， 70 ， 85 ， 90} 20 35 70 70 85 90 ?查找結(jié)點(diǎn) ? 根據(jù)前面的定義可知，二叉 搜索 樹(shù)的查找是一個(gè)遞歸的過(guò)程，具體如下： ? ① 若二叉排序樹(shù)為空，則查找失敗，輸出相關(guān)信息。 ? ② 若二叉查找樹(shù)不為空，將給定值 x與查找樹(shù)的根結(jié)點(diǎn)關(guān)鍵字進(jìn)行比較。 ?③ 若比較結(jié)果為相等，則查找成功，整個(gè)查找結(jié)束。 ?否則，完成下面的判斷： ? (i) 若給定的值 x小于根結(jié)點(diǎn)關(guān)鍵字的值，查找將按照遞歸的方式在左子樹(shù)上進(jìn)行。 ? (ii)若給定的值 x大于根結(jié)點(diǎn)關(guān)鍵字的值，查找將按照遞歸的方式在右子樹(shù)上進(jìn)行。 ?(iii)重復(fù)以上過(guò)程，直到查找結(jié)束（成功或者失?。?。 50 30 80 20 90 85 40 35 88 32 查找關(guān)鍵字 == 50 , 35 , 90 , 95 查找失敗 ?算法分析： ? 對(duì)于深度為 d的二叉搜索樹(shù)，若設(shè)第 i層有 ni個(gè)結(jié)點(diǎn)，則在等查找概率情況下，其平均查找長(zhǎng)度為： ASL= ?? ?diinin11最好情況下， O（ log2n） 最壞情況下， O（ n） ASL ???niin 1121?? n
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1