第6章樹與二叉樹(編輯修改稿)
2024-11-29 15:07 本頁面
【文章內(nèi)容簡介】 ；否則其左孩子 LCHILD(i)是節(jié)點 2i 。 ③ 如果 2i+1n，則節(jié)點 i無右孩子；否則其右孩子 RCHILD(i) 是節(jié)點 2i+1。 二叉樹的存儲結(jié)構(gòu) ? 順序存儲 以節(jié)點在向量中的相對位置來表示節(jié)點間的關(guān)系。 不足：一般的二叉樹也必須按完全二叉樹的形式來存儲，勢必會造成存儲的浪費。 53214( a ) 二叉樹T∧22∧1 14 ∧∧5 ∧345∧3 ∧ ∧214 ∧∧5 ∧∧3 ∧∧( b ) 二叉樹T 的單指針存儲 ( c ) 二叉樹T 的雙指針存儲 ( d ) 二叉樹T 的三指針存儲圖6 . 6 二叉樹鏈式存儲結(jié)構(gòu)示例root root root? 鏈式存儲 單叉鏈表 三叉鏈表 二叉鏈表 常用鏈式存儲結(jié)構(gòu)：二叉鏈表 二叉樹操作的實現(xiàn) ? 遍歷（周游）算法 深度優(yōu)先遍歷： 先序遍歷：若二叉樹為空 ， 則空操作；否則 (1)訪問根節(jié)點； (2)先序遍歷左子樹； (3)先序遍歷右子樹 。 中序遍歷：若二叉樹為空 ， 則空操作；否則 (1)中序遍歷左子樹； (2)訪問根節(jié)點； (3)中序遍歷右子樹 。 后序遍歷：若二叉樹為空 ， 則空操作；否則 (1)后序遍歷左子樹； (2)后序遍歷右子樹； (3)訪問根節(jié)點。 二叉樹遍歷的典型應(yīng)用－－表達式樹 cba*cba*cba*cba*(a)a*(bc)的 表達式樹T ( b ) 先序遍歷表達式樹T ( c ) 中序遍歷表達式樹T ( d ) 后序遍歷表達式樹T圖6 . 7 表達式樹與三種遍歷 先序遍歷此二叉樹 ， 得到的二叉樹的先序序列為： *abc； 中序遍歷此二叉樹 ， 得到該二叉樹的中序序列為： a*bc； 后序遍歷此二叉樹，得到該二叉樹的后序序列為： abc*； 前綴表示（波蘭式） 后綴表示（逆波蘭式） 中綴表示（中綴式） 非遞歸實現(xiàn)樹的深度優(yōu)先遍歷 利用棧 非遞歸實現(xiàn)樹的廣度優(yōu)先遍歷 利用隊列 ?遍歷算法 時間 復(fù)雜度： O(N) ?遍歷算法 空間 復(fù)雜度：至多為 O(N) 樹和森林 ? 樹的存儲結(jié)構(gòu) 三種典型的表示法： 第一種是 雙親表示法 。 第二種是孩子表示法 。 第三種是孩子兄弟表示法 。 RL M NP QWR 1L 0M 0N 0P 1Q 1W 30654321數(shù)組下標數(shù)據(jù)域 父節(jié)點域( a ) 樹的邏輯結(jié)構(gòu) ( b ) 樹的雙親表示法示例data c 1 c Dc 2 ?degree c 1 c dc 2 ?dataRLM ∧NP ∧Q ∧W ∧∧∧∧∧∧∧∧∧∧∧∧32010 00RLMNP QWrootroot節(jié)點的結(jié)構(gòu)節(jié)點的結(jié)構(gòu)( c ) 樹的一種孩子表示法示例( d ) 樹的另一種孩子表示法示例RLM ∧NP ∧Q ∧W ∧0654321數(shù)據(jù)域 子節(jié)點域L M N ∧P Q ∧W ∧RLM ∧NP ∧Q ∧W ∧0654321數(shù)據(jù)域 子節(jié)點域L M N ∧P Q ∧W ∧1000113父節(jié)點域( e ) 樹的孩子鏈表 ( e ) 樹的帶雙親的孩子鏈表 樹的雙 親表示法與孩子表示法R ∧LP∧ M∧N ∧Q ∧∧W ∧∧data nextSiblingfirstChild節(jié)點的數(shù)據(jù)域節(jié)點的下一個兄弟域節(jié)點的第一個孩子域( a ) 樹節(jié)點的存儲
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1