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