樹 · 做前端有饅頭吃

* 一種分層數據的抽象模型 * 前端工作中常見的樹包括：DOM樹、級聯選擇、樹形控件... * JS中沒有樹，但是可以用Object 和 Array 構建樹 * *深度、廣度優先遍歷、先中后序遍歷 # 深度優先遍歷（dfs） * 訪問根節點 * 對根節點的children挨個進行深度優先遍歷。 ![](https://img.kancloud.cn/09/2f/092fcfd42fc9630fe4516189b6458c96_992x300.png) # 廣度優先遍歷（bfs） * 新建一個隊列，把根節點入隊 * 把隊頭出隊并訪問 * 把隊頭的children挨個入隊 * 重復第二、第三步，知道隊列為空 ![](https://img.kancloud.cn/e2/72/e27234d04ce6a89910ab3c1b688debfd_1164x532.png) # 二叉樹先中后遍歷 ## 先序遍歷(preorder)的算法口訣`[根-左-右]` * 訪問根節點 * 對根節點的`左`子樹進行先序遍歷 * 對根節點的`右`子樹進行先序遍歷 ![](https://img.kancloud.cn/20/3a/203a36ce0998fc9ffede7a589720023b_866x514.png) ![](https://img.kancloud.cn/a2/4c/a24cf4539ba37bbe2eb1a3fea5790196_936x592.png) ## 中序遍歷(inorder)的算法口訣`[左-根-右]` * 對根節點的左子樹進行中序遍歷 * 訪問根節點 * 對根節點的右子樹進行中序遍歷 ![](https://img.kancloud.cn/f5/7f/f57f7e8ab424ba145e3118035e701754_846x536.png) 非遞歸，棧+循環實現： ![](https://img.kancloud.cn/4c/b1/4cb1f97b742d38d9b6cf19b61a59f88e_746x730.png) ## 后序遍歷(postorder)的算法口訣`[左-右-根]` * 對根節點的左子樹進行后序遍歷 * 對根節點的右子樹進行后序遍歷 * 訪問根節點 ![](https://img.kancloud.cn/8e/b7/8eb7e65ba84ad9da8d1a370811b12e4b_928x574.png) 非遞歸，棧+循環實現： ![](https://img.kancloud.cn/00/05/0005c0acf591445674a2961095825771_800x848.png) LeetCode：104. 二叉樹的最大深度 ![](https://img.kancloud.cn/37/ad/37ad3002c695d83e10e84aa470290c01_930x654.png) LeetCode：111. 二叉樹的最小深度 ![](https://img.kancloud.cn/aa/ed/aaed8014e208ae3e5f177d2ff7b03288_994x718.png) 遍歷 JSON 的所有節點值：遍歷json節點，順便把路徑輸出來 ![](https://img.kancloud.cn/f6/db/f6dbe68119a6eeb268957c00210f9636_1044x642.png) 改進加個判斷版： ![](https://img.kancloud.cn/43/21/43217227d69bea790c95bb2ef0580096_1184x740.png)