正文內容

第6章樹與二叉樹(編輯修改稿)

2025-11-29 15:07 本頁面

　

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

點擊復制文檔內容

教學課件相關推薦

第6章樹與二叉樹(編輯修改稿)

算法與數據結構第4章樹與二叉樹ppt-資料下載頁

樹和二叉樹ppt課件(2)-資料下載頁

第六章樹和二叉樹-資料下載頁

數據結構---樹和二叉樹-資料下載頁

特殊二叉樹ppt課件-資料下載頁

二叉樹期權定價模型-資料下載頁

二叉樹的建立與遍歷與二叉樹的線索化與線索化遍歷-資料下載頁

樹和森林與二叉樹的轉換-資料下載頁

樹和二叉樹實驗報告-資料下載頁

期權二叉樹模型ppt課件-資料下載頁

二叉樹定價模型-資料下載頁

最優二叉樹哈夫曼樹-資料下載頁

數據結構實驗四樹與二叉樹-資料下載頁

[工學]數據結構11樹和二叉樹-資料下載頁

程序二叉樹習題(answer)-資料下載頁

第6章樹與二叉樹(已改無錯字)

第6章樹與二叉樹-資料下載頁

第6章樹與二叉樹(參考版)

第6章樹與二叉樹-文庫吧資料

第6章樹與二叉樹-展示頁