管理學(xué)六樹ppt課件(編輯修改稿)
2025-01-04 05:31 本頁面
【文章內(nèi)容簡介】 到一個結(jié)點(diǎn)，先把它推入棧中，讓 PopTim=0。在遍歷其左子樹前，改結(jié)點(diǎn)的PopTim=1，將其左子女推入棧中。在遍歷完左子樹后，還不能訪問該結(jié)點(diǎn)，必須繼續(xù)遍歷右子樹，此時改結(jié)點(diǎn)的 PopTim=2，并把其右子女推入棧中。在遍歷完右子樹后，結(jié)點(diǎn)才退棧訪問。 ? 請寫出后序遍歷的算法（遞歸與非遞歸算法） 層次遍歷 從根開始逐層訪問， 用 FIFO隊列實現(xiàn)。 遍歷順序 樹的遍歷 先根次序遍歷：先訪問樹的根結(jié)點(diǎn)，然后依次 先根遍歷根的每棵子樹 后根次序遍歷：先依次后根遍歷每棵子樹，然 后訪問根結(jié)點(diǎn) 先根序列： A B C D E 后根序列： B C E D A 求出該樹的先根序列和后根序列。 先根序列： ABCEIJFGKHD A B C D E I J F G K H 后根序列： BIJEFKGHCDA 森林的遍歷 森林的二叉樹表示 (1) 先序遍歷的規(guī)則： ? 若森林 F為空 , 返回；否則 ? 訪問 F的第一棵樹的根結(jié)點(diǎn)； ? 先根次序遍歷第一棵樹的根結(jié)點(diǎn)的子樹森林； ? 先根次序遍歷其它樹組成的森林。 先序遍歷時結(jié)點(diǎn)的訪問序列： A B C D E F G H I K J 森林的遍歷 森林的二叉樹表示 (2) 中序遍歷的規(guī)則： ? 若森林 F為空，返回；否則 ? 中根次序遍歷第一棵樹的根結(jié)點(diǎn)的子樹森林； ? 訪問 F的第一棵樹的根結(jié)點(diǎn)； ? 中根次序序遍歷其它樹組成的森林。 中根遍歷時結(jié)點(diǎn)的訪問序列： B C E D A G F K I J H 森林的遍歷 森林的二叉樹表示 (3) 廣度優(yōu)先遍歷 (層次序遍歷 ) ： ? 若森林 F為空，返回；否則 ? 依次遍歷各棵樹的根結(jié)點(diǎn)； ? 依次遍歷各棵樹根結(jié)點(diǎn)的所有子女； ? 依次遍歷這些子女結(jié)點(diǎn)的子女結(jié)點(diǎn) 。 ?? 層次序遍歷時結(jié)點(diǎn)的訪問序列： A F H B C D G I J E K 二叉樹的計數(shù) 問題： n 個數(shù)據(jù)值，可能構(gòu)造多少種不同的二叉樹？ 二叉樹的計數(shù) 由二叉樹的前序序列和中序序列可唯一地確定一棵二叉樹。 例 , 前序序列 { ABHFDECKG } 和 中序序列 { HBDFAEKCG }, 構(gòu)造二叉樹過程如下： 二叉樹的計數(shù) 由二叉樹的前序序列和中序序列可唯一地確定一棵二叉樹。 例 , 前序序列 { ABHFDECKG } 和 中序序列 { HBDFAEKCG }, 構(gòu)造二叉樹過程如下： 二叉樹的計數(shù) 由二叉樹的前序序列和中序序列可唯一地確定一棵二叉樹。 例 , 前序序列 { ABHFDECKG } 和 中序序列 { HBDFAEKCG }, 構(gòu)造二叉樹過程如下： 二叉樹的計數(shù) 由二叉樹的前序序列和中序序列可唯一地確定一棵二叉樹。 例 , 前序序列 { ABHFDECKG } 和 中序序列 { HBDFAEKCG }, 構(gòu)造二叉樹過程如下： 二叉樹的計數(shù) 由二叉樹的前序序列和中序序列可唯一地確定一棵二叉樹。 例 , 前序序列 { ABHFDECKG } 和 中序序列 { HBDFAEKCG }, 構(gòu)造二叉樹過程如下： 二叉樹的計數(shù) 由二叉樹的前序序列和中序序列可唯一地確定一棵二叉樹。 例 , 前序序列 { ABHFDECKG } 和 中序序列 { HBDFAEKCG }, 構(gòu)造二叉樹過程如下： 二叉樹的計數(shù) 由二叉樹的前序序列和中序序列可唯一地確定一棵二叉樹。 例 , 前序序列 { ABHFDECKG } 和 中序序列 { HBDFAEKCG }, 構(gòu)造二叉樹過程如下： 二叉樹的計數(shù) 由二叉樹的前序序列和中序序列可唯一地確定一棵二叉樹。 例 , 前序序列 { ABHFDECKG } 和 中序序列 { HBDFAEKCG }, 構(gòu)造二叉樹過程如下： 二叉樹的計數(shù) 由二叉樹的前序序列和中序序列可唯一地確定一棵二叉樹。 例 , 前序序列 { ABHFDECKG } 和 中序序列 { HBDFAEKCG }, 構(gòu)造二叉樹過程如下： 若研究 n 個數(shù)據(jù)值可能構(gòu)造多少種不同的二叉樹？我們可以固定前序排列，選擇所有可能的中序排列。 如果前序序列固定不變，給出不同的中序序列，可得到不同的二叉樹。 例如，有 3 個數(shù)據(jù) { 1, 2, 3 }，可得 5種不同的二叉樹。它們的前序排列均為 123， 中序序列可能是 123， 132， 213， 231， 321。 有 0個 , 1個 , 2個 , 3個結(jié)點(diǎn)的不同二叉樹如下 計算具有 n個結(jié)點(diǎn)的不同二叉樹的棵數(shù) 1 bi bni1 根 例如，具有 4個結(jié)點(diǎn)的不同二叉樹 b n n nn nn nnC? ? ? ? ?1 1 1 1 22 ( ) !! !Catalan函數(shù) ? 問題的提出 哈夫曼編碼及其應(yīng)用 電子期刊、網(wǎng)絡(luò)音樂、網(wǎng)絡(luò)電影 …… 數(shù)據(jù)存儲的壓力 數(shù)據(jù)通信的壓力 大數(shù)據(jù)量 計算機(jī)處理的壓力 數(shù)據(jù)壓縮是關(guān)鍵。 壓縮的關(guān)鍵在于編碼 。 ? 教學(xué)目的 本節(jié)課的教學(xué)目的是在研
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1