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