簡介 · 數據結構和算法

[TOC] # 為什么有樹結構? ![](https://box.kancloud.cn/37d2961d64dd617b180c58f77d3779c1_818x1000.png) ![](https://box.kancloud.cn/87c16384680729e4fad4ccf515440a4a_1450x1216.png) ![](https://box.kancloud.cn/cc02b3522bfcae372d5930c0342e853c_2080x1048.png) # 二叉樹 ![](https://box.kancloud.cn/2eca627b68e482d0878b5ee2d03b21b1_2924x1090.png) ![](https://box.kancloud.cn/4389a2d33d08032453b6fbd6df326f94_2908x1106.png) 二叉樹不一定是滿的,葉子節點有可能只有1個一個根節點也可以是二叉樹 null也可以是二叉樹 # 二分搜索樹(BST) ![](https://box.kancloud.cn/ccdb101f5f5fd32ef8f92da30028fd52_2880x1132.png) 存儲的元素必須具有可比較性 # 遍歷前序遍歷(先訪問節點,再訪問左右子樹) 中序遍歷(先訪問左子樹或者右子樹,再訪問根節點,再訪問其他節點)(二分搜索樹的中序遍歷結果是順序的) 后序遍歷(先遍歷左右子樹再遍歷根節點)(應用,為二分搜索樹釋放內存) ## 前序遍歷,遞歸 ![](https://box.kancloud.cn/a7dd2b31d3b0923e9a40e0f63af6124e_1280x671.png) ## 中序遍歷,遞歸 ![](https://box.kancloud.cn/0e8cc944d053aa08d74c16534b4e3568_1279x680.png) ## 后序遍歷,遞歸 ![](https://box.kancloud.cn/4d7eb3a51a7aea893941a2c395dfffb2_1262x682.png) ## 前序遍歷,非遞歸利用棧遍歷 ![](https://box.kancloud.cn/04874b8db5fad3337be2c2f17b0c7bd4_1339x635.png) ## 層序遍歷(廣度優先) 借助隊列 ![](https://box.kancloud.cn/c0e2cb7c772beb60fd2b391fa44d9119_1366x620.png) 意義在于可以很快找到你要查找的元素,區別在于搜索策略常用于最短路徑圖中的深度優先遍歷和廣度優先遍歷 # 刪除最小值找左邊,直到為null,那就是自己 ![](https://box.kancloud.cn/d2366ce3ea09c3fa5da910e2f9825bb2_661x570.png) # 刪除最大值找右邊,直到為null,那就是自己 ![](https://box.kancloud.cn/2db9e37dd2092bacfdacfada31e45fff_874x571.png)