Hello 算法用數(shù)組表示二叉樹——索引映射公式與 ArrayBinaryTree 的完整 Python 實(shí)現(xiàn)【免費(fèi)下載鏈接】hello-algo《Hello 算法》動(dòng)畫圖解、一鍵運(yùn)行的數(shù)據(jù)結(jié)構(gòu)與算法教程。支持簡(jiǎn)中、繁中、English、日本語(yǔ)提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代碼實(shí)現(xiàn)項(xiàng)目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本文基于 hello-algo 倉(cāng)庫(kù)的codes/pythontutor/chapter_tree/array_binary_tree.mdPython Tutor 可視化數(shù)據(jù)文件及其對(duì)應(yīng)的可運(yùn)行源碼 array_binary_tree.py系統(tǒng)講解“用數(shù)組表示二叉樹”的核心思想通過(guò)索引映射公式2i1 / 2i2 / (i-1)//2替代指針引用實(shí)現(xiàn)對(duì)節(jié)點(diǎn)值、父子關(guān)系的 O(1) 訪問(wèn)與前/中/后序及層序遍歷并說(shuō)明該文件在 Python Tutor 單步可視化中的使用方式。一、這個(gè)文檔文件是什么Python Tutor 可視化數(shù)據(jù)codes/pythontutor/目錄下的每個(gè).md文件并非普通文章而是喂給 Python Tutor 為例它的結(jié)構(gòu)非常固定!-- File: array_binary_tree.md Created Time: 2024-01-05 Author: krahets (krahets163.com) -- !-- [file]{array_binary_tree}-[class]{array_binary_tree}-[func]{} -- https://pythontutor.com/render.html#code...URL 編碼后的完整 Python 源碼py311modedisplay...頭部注釋中的[file]{array_binary_tree}-[class]{array_binary_tree}-[func]{}是與文檔站代碼塊標(biāo)記 Python多語(yǔ)言切換器中[file]{...}語(yǔ)法對(duì)應(yīng)的錨點(diǎn)標(biāo)明這段代碼屬于array_binary_tree文件、ArrayBinaryTree類、全部方法。緊隨其后的render.html#code...鏈接是把完整 Python 源碼做了 URL 編碼后拼出來(lái)的渲染地址參數(shù)py311表示按 Python 3.11 語(yǔ)法高亮modedisplay表示展示模式。把該鏈接粘貼進(jìn)瀏覽器就能在 Python Tutor 中獲得帶內(nèi)存視圖、可逐指令單步執(zhí)行的ArrayBinaryTree運(yùn)行演示——這正是該目錄名為pythontutor的原因。將 URL 編碼部分解碼后得到的完整代碼與倉(cāng)庫(kù)中可直接運(yùn)行的 array_binary_tree.py 基本一致可視化版用更小的示例數(shù)組去掉了對(duì)modules工具的依賴保證單文件即可在 Python Tutor 中獨(dú)立運(yùn)行。下文以可運(yùn)行版本為主體逐段講解兩者差異處會(huì)單獨(dú)指出。二、表示完美二叉樹索引映射公式在鏈表表示下二叉樹的存儲(chǔ)單元是TreeNode節(jié)點(diǎn)節(jié)點(diǎn)之間靠指針left/right引用連接倉(cāng)庫(kù)中的定義見 tree_node.pyclass TreeNode: 二叉樹節(jié)點(diǎn)類 def __init__(self, val: int 0): self.val: int val # 節(jié)點(diǎn)值 self.height: int 0 # 節(jié)點(diǎn)高度 self.left: TreeNode | None None # 左子節(jié)點(diǎn)引用 self.right: TreeNode | None None # 右子節(jié)點(diǎn)引用那么能否不用指針、只用一個(gè)數(shù)組答案是肯定的。先考慮最理想的情況——完美二叉樹把所有節(jié)點(diǎn)按層序遍歷的順序存入數(shù)組每個(gè)節(jié)點(diǎn)對(duì)應(yīng)唯一的數(shù)組索引。根據(jù)層序遍歷的特性可以推導(dǎo)出父/子索引之間的映射公式若某節(jié)點(diǎn)的索引為i則其左子節(jié)點(diǎn)索引為2i 1右子節(jié)點(diǎn)索引為2i 2父節(jié)點(diǎn)索引為(i - 1) // 2。這些映射公式的角色等價(jià)于鏈表表示中的指針給定數(shù)組中的任意一個(gè)節(jié)點(diǎn)通過(guò)公式即可 O(1) 定位它的左子、右子與父節(jié)點(diǎn)無(wú)需任何引用存儲(chǔ)。三、表示任意二叉樹顯式寫出 None完美二叉樹只是特例。真實(shí)的二叉樹中間層通常存在許多空位而普通層序遍歷序列并不包含這些None因此同一條層序序列可能對(duì)應(yīng)多種不同的樹結(jié)構(gòu)無(wú)法唯一表示。解決方法是在層序遍歷序列中顯式地寫出所有None占位這樣序列就能唯一確定二叉樹。倉(cāng)庫(kù)使用的統(tǒng)一示例是# 二叉樹的數(shù)組表示 # 使用 None 來(lái)表示空位 tree [1, 2, 3, 4, None, 6, 7, 8, 9, None, None, 12, None, None, 15]這個(gè)數(shù)組對(duì)應(yīng)一棵非完美樹索引 4、9、10、12、13 為空位。各語(yǔ)言對(duì)“空位”的表示不同但編碼規(guī)則完全一致例如 C/C 用INT_MAX、Java 用Integer[]null、Go 用[]anynil、Rust 用Optioni32完整對(duì)照見 array_representation_of_tree.md。值得一提的是完全二叉樹按定義空位只出現(xiàn)在最底層且靠右的位置因此所有None必然出現(xiàn)在數(shù)組末尾序列化時(shí)可以全部省略數(shù)組表示最為緊湊。堆heap就是最典型的“完全二叉樹的數(shù)組表示”倉(cāng)庫(kù)中 print_util.py 的print_heap正是把堆數(shù)組用list_to_tree還原成樹狀圖形打印。四、ArrayBinaryTree 類逐方法解析下面結(jié)合 array_binary_tree.py 的源碼逐方法說(shuō)明。4.1 構(gòu)造與容量class ArrayBinaryTree: 數(shù)組表示下的二叉樹類 def __init__(self, arr: list[int | None]): 構(gòu)造方法 self._tree list(arr) def size(self): 列表容量 return len(self._tree)構(gòu)造時(shí)用list(arr)做一次淺拷貝避免外部修改原數(shù)組影響樹的內(nèi)容size()返回?cái)?shù)組長(zhǎng)度即“列表容量”注意它不等于節(jié)點(diǎn)個(gè)數(shù)。4.2 節(jié)點(diǎn)訪問(wèn)val / left / right / parentdef val(self, i: int) - int | None: 獲取索引為 i 節(jié)點(diǎn)的值 # 若索引越界則返回 None 代表空位 if i 0 or i self.size(): return None return self._tree[i] def left(self, i: int) - int | None: 獲取索引為 i 節(jié)點(diǎn)的左子節(jié)點(diǎn)的索引 return 2 * i 1 def right(self, i: int) - int | None: 獲取索引為 i 節(jié)點(diǎn)的右子節(jié)點(diǎn)的索引 return 2 * i 2 def parent(self, i: int) - int | None: 獲取索引為 i 節(jié)點(diǎn)的父節(jié)點(diǎn)的索引 return (i - 1) // 2四個(gè)方法共同構(gòu)成數(shù)組表示的“指針系統(tǒng)”方法公式說(shuō)明val(i)tree[i]越界時(shí)返回None與“空位”語(yǔ)義統(tǒng)一調(diào)用方無(wú)需做邊界判斷l(xiāng)eft(i)2i 1返回索引而非節(jié)點(diǎn)越界與否交由val判定right(i)2i 2同上parent(i)(i - 1) // 2整除向下取整i0根節(jié)點(diǎn)會(huì)得到(0-1)//2 -1val(-1)因越界保護(hù)而返回None這種“返回索引 由val統(tǒng)一兜底越界”的設(shè)計(jì)使遞歸代碼可以無(wú)邊界檢查地寫self.dfs(self.left(i), order)邏輯非常干凈。4.3 層序遍歷數(shù)組的先天優(yōu)勢(shì)def level_order(self) - list[int]: 層序遍歷 self.res [] # 直接遍歷數(shù)組 for i in range(self.size()): if self.val(i) is not None: self.res.append(self.val(i)) return self.res因?yàn)閿?shù)組本身就是按層序排好的層序遍歷不需要隊(duì)列一次線性掃描跳過(guò)None即可時(shí)間復(fù)雜度 O(n)比鏈表表示下需要顯式維護(hù)隊(duì)列的 BFS 實(shí)現(xiàn)簡(jiǎn)單得多。4.4 深度優(yōu)先遍歷用 order 參數(shù)統(tǒng)一前/中/后序def dfs(self, i: int, order: str): 深度優(yōu)先遍歷 if self.val(i) is None: return # 前序遍歷 if order pre: self.res.append(self.val(i)) self.dfs(self.left(i), order) # 中序遍歷 if order in: self.res.append(self.val(i)) self.dfs(self.right(i), order) # 后序遍歷 if order post: self.res.append(self.val(i)) def pre_order(self) - list[int]: 前序遍歷 self.res [] self.dfs(0, orderpre) return self.res # in_order / post_order 同理分別傳 in 與 post實(shí)現(xiàn)要點(diǎn)有三個(gè)剪枝val(i) is None時(shí)直接返回。注意即使父節(jié)點(diǎn)為空l(shuí)eft/right公式仍會(huì)算出子索引因此必須依賴空位判斷終止遞歸而不能依賴“父為空則子必為空”。三序合一訪問(wèn)時(shí)機(jī)記錄節(jié)點(diǎn)值分別放在遞歸左子樹之前、左右之間、遞歸右子樹之后用一個(gè)order字符串復(fù)用同一套遞歸骨架。結(jié)果容器self.res由三個(gè)入口方法各自初始化dfs只做累加保證每次遍歷都得到獨(dú)立結(jié)果。對(duì)照鏈表版實(shí)現(xiàn)可以看到數(shù)組版的dfs(i, order)與鏈表版dfs(root)的遞歸結(jié)構(gòu)完全同構(gòu)差別僅在于“取子節(jié)點(diǎn)”從node.left變成了self.left(i)的索引計(jì)算——這正是映射公式替代指針的直接體現(xiàn)。五、運(yùn)行示例Driver Code 與可視化版的差異可運(yùn)行版的驅(qū)動(dòng)代碼array_binary_tree.py演示了完整鏈路if __name__ __main__: # 初始化二叉樹 # 這里借助了一個(gè)從數(shù)組直接生成二叉樹的函數(shù) arr [1, 2, 3, 4, None, 6, 7, 8, 9, None, None, 12, None, None, 15] root list_to_tree(arr) print(\n初始化二叉樹\n) print(二叉樹的數(shù)組表示) print(arr) print(二叉樹的鏈表表示) print_tree(root) # 數(shù)組表示下的二叉樹類 abt ArrayBinaryTree(arr) # 訪問(wèn)節(jié)點(diǎn) i 1 l, r, p abt.left(i), abt.right(i), abt.parent(i) print(f\n當(dāng)前節(jié)點(diǎn)的索引為 {i} 值為 {abt.val(i)}) print(f其左子節(jié)點(diǎn)的索引為 {l} 值為 {abt.val(l)}) print(f其右子節(jié)點(diǎn)的索引為 {r} 值為 {abt.val(r)}) print(f其父節(jié)點(diǎn)的索引為 {p} 值為 {abt.val(p)}) # 遍歷樹 res abt.level_order() # 層序遍歷 res abt.pre_order() # 前序遍歷 res abt.in_order() # 中序遍歷 res abt.post_order() # 后序遍歷其中l(wèi)ist_to_tree與print_tree分別來(lái)自 tree_node.py 和 print_util.py它們同樣基于同一套索引公式工作從源碼結(jié)構(gòu)可以印證公式的正確性def list_to_tree_dfs(arr: list[int], i: int) - TreeNode | None: 將列表反序列化為二叉樹遞歸 # 如果索引超出數(shù)組長(zhǎng)度或者對(duì)應(yīng)的元素為 None 則返回 None if i 0 or i len(arr) or arr[i] is None: return None # 構(gòu)建當(dāng)前節(jié)點(diǎn) root TreeNode(arr[i]) # 遞歸構(gòu)建左右子樹 root.left list_to_tree_dfs(arr, 2 * i 1) root.right list_to_tree_dfs(arr, 2 * i 2) return root數(shù)組到樹list_to_tree_dfs與樹到數(shù)組tree_to_list_dfs見 tree_node.py用res [None] * (i - len(res) 1)補(bǔ)位到目標(biāo)索引互為逆操作TreeNode類注釋里還直接給出了示例數(shù)組與對(duì)應(yīng)樹形圖可作為人工驗(yàn)證映射公式的對(duì)照表。Python Tutor 可視化版即 array_binary_tree.md 解碼后的內(nèi)容為了單文件自包含做了兩處簡(jiǎn)化內(nèi)置了一個(gè)精簡(jiǎn)版TreeNode僅val/left/right三個(gè)屬性不再 importmodules示例數(shù)組縮小為arr [1, 2, 3, 4, None, 6, None]便于在可視化器的小畫布上觀察內(nèi)存幀變化。解碼后的驅(qū)動(dòng)部分如下Driver Code if __name__ __main__: # 初始化二叉樹 arr [1, 2, 3, 4, None, 6, None] abt ArrayBinaryTree(arr) # 訪問(wèn)節(jié)點(diǎn) i 1 l, r, p abt.left(i), abt.right(i), abt.parent(i) # 遍歷樹 res abt.level_order() res abt.pre_order() res abt.in_order() res abt.post_order()對(duì)索引i 1值為 2應(yīng)用公式left 2*11 3值為 4、right 2*12 4空位val(4)返回None、parent (1-1)//2 0值為 1與樹形結(jié)構(gòu)完全吻合——這就是在 Python Tutor 中逐幀單步時(shí)應(yīng)當(dāng)核對(duì)的內(nèi)存狀態(tài)。六、優(yōu)點(diǎn)與局限性綜合文檔 array_representation_of_tree.md 的結(jié)論與上述源碼實(shí)現(xiàn)數(shù)組表示的取舍如下優(yōu)點(diǎn)數(shù)組存儲(chǔ)在連續(xù)內(nèi)存中對(duì)緩存友好訪問(wèn)與遍歷速度較快層序遍歷甚至可降為簡(jiǎn)單掃描不需要存儲(chǔ)指針比較節(jié)省空間且節(jié)點(diǎn)間關(guān)系通過(guò)純算術(shù)公式 O(1) 獲取允許隨機(jī)訪問(wèn)任意節(jié)點(diǎn)實(shí)現(xiàn)緊湊完全二叉樹可省略末尾空位序列化即存儲(chǔ)天然適合堆等場(chǎng)景。局限性數(shù)組需要連續(xù)內(nèi)存空間不適合存儲(chǔ)數(shù)據(jù)量過(guò)大的樹增刪節(jié)點(diǎn)需要借助數(shù)組插入/刪除操作實(shí)現(xiàn)效率較低O(n) 搬移當(dāng)二叉樹中存在大量None如極度不平衡的樹時(shí)有效數(shù)據(jù)占比低空間利用率差。因此實(shí)踐中常見“雙表示”策略對(duì)外用指針鏈表表示方便結(jié)構(gòu)操作內(nèi)部堆、線段樹等用數(shù)組表示追求性能——本倉(cāng)庫(kù)同時(shí)提供 array_binary_tree.py 與 binary_tree.py 兩套實(shí)現(xiàn)恰好構(gòu)成這一對(duì)比學(xué)習(xí)的完整閉環(huán)。七、小結(jié)數(shù)組表示二叉樹的核心是三條索引映射公式左子2i1、右子2i2、父(i-1)//2它們完全替代了鏈表中的指針任意二叉樹需要在層序序列中顯式保留None占位才能被唯一表示完全二叉樹則可直接省略末尾空位ArrayBinaryTree展示了四個(gè)節(jié)點(diǎn)訪問(wèn)方法與一套“order參數(shù)驅(qū)動(dòng)”的三序 DFS層序遍歷則退化為線性掃描codes/pythontutor/chapter_tree/array_binary_tree.md 以 URL 編碼鏈接的形式承載上述代碼可直接在 Python Tutor 中逐指令單步觀察每一幀中self._tree列表與遞歸棧的內(nèi)存變化是理解該表示法的交互式教具。【免費(fèi)下載鏈接】hello-algo《Hello 算法》動(dòng)畫圖解、一鍵運(yùn)行的數(shù)據(jù)結(jié)構(gòu)與算法教程。支持簡(jiǎn)中、繁中、English、日本語(yǔ)提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代碼實(shí)現(xiàn)項(xiàng)目地址: https://gitcode.com/GitHub_Trending/he/hello-algo創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考