（本文是根據(jù)網(wǎng)絡視頻做的筆記，更新）
數(shù)據(jù)結構用得少渠概，經(jīng)常學了忘茶凳，忘了學嫂拴，這次干脆做個筆記。主要的目的是列個大綱贮喧，寫出基本概念筒狠，便于以后快速記憶與查找。
一）數(shù)據(jù)結構之隊列
- 什么隊列
隊列就是FIFO（first in first out）的數(shù)據(jù)結構 - 隊列的種類
普通隊列和環(huán)形隊列（常用）
二）數(shù)據(jù)結構之棧
- 什么是棧
棧就是LIFO（last in first out）的數(shù)據(jù)結構
三）數(shù)據(jù)結構之線性表（鏈表）
什么是線性表
線性表是n個數(shù)據(jù)元素（可以很復雜）的有限序列箱沦。-
線性表的分類
image.png
四）數(shù)據(jù)結構之樹
- 什么是樹
樹是節(jié)點的有限集合 - 理解孩子辩恼，雙親，度谓形，葉子（終端節(jié)點）灶伊，根（非終端節(jié)點），有序樹寒跳，無序樹的概念聘萨。
什么是雙親？
雙親是指一個節(jié)點童太，表示父節(jié)點米辐，注意叫法的問題。如B,C,D的雙親都是A康愤。
什么是孩子儡循？
對于B來說，E征冷，F(xiàn)都是B的孩子择膝。
什么是度？
指某以節(jié)點的直系孩子數(shù)检激，如A的度就是3肴捉，他有B，C叔收，D三個孩子齿穗，再如B的度是2，H的度為0饺律。
什么是葉子窃页？
就是終端節(jié)點，表示沒有孩子的節(jié)點复濒。如C脖卖，E，F(xiàn)巧颈，G畦木，H。
什么是根砸泛？
非終端節(jié)點十籍，表示有孩子的節(jié)點蛆封。如A，B勾栗，D
什么是有序樹惨篱，無序樹？
這是相對的概念围俘，比如E妒蛇，F(xiàn)交換順序而不影響邏輯，那么就是無序樹楷拳，否則就是有序樹。
什么是祖先吏奸？
節(jié)點的一直往上的節(jié)點欢揖，如對于E來說，B奋蔚，A就是他的祖先她混。對于G來說，D泊碑，A就是他的祖先坤按。
什么是子孫？
節(jié)點一直往下的節(jié)點馒过。如對與A來說臭脓，下方所有的節(jié)點就是他的子孫。對于D來說腹忽，G来累，H是他的子孫。
什么是層窘奏？
本圖可以看到嘹锁，有3層。
什么是節(jié)點深度着裹？
在第一層的節(jié)點的深度就是1领猾，如A的深度是1
在第二層的節(jié)點的深度就是2，如B骇扇，C摔竿，D的深度是2
在第三層的節(jié)點的深度就是3，如E匠题，F(xiàn)拯坟，G，H的深度是3
什么是樹的深度韭山？
節(jié)點的最大深度郁季，就是層數(shù)冷溃，即3。
二叉樹
- 什么是二叉樹梦裂？
所有節(jié)點的度都小于等于2似枕。
-
二叉樹的遍歷？
image.png
二叉搜索樹（二叉查找樹年柠、有序二叉樹凿歼、排序二叉樹）
什么是二叉搜索樹？
空樹或者滿足特性的樹二叉搜索樹的特性冗恨？
- 若任意節(jié)點的左子樹不空答憔，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值；
- 若任意節(jié)點的右子樹不空掀抹，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值虐拓；
- 任意節(jié)點的左、右子樹也分別為二叉查找樹傲武；
- 沒有鍵值相等的節(jié)點蓉驹。
平衡二叉樹（AVL樹）
什么是平衡二叉樹？
即平衡二叉搜索樹揪利，也叫AVL樹AVL樹的特性态兴？
空樹或滿足
- 它的左右兩個子樹的高度差的絕對值不超過1
- 左右兩個子樹都是一棵平衡二叉樹
紅黑樹
什么是紅黑樹？
紅黑樹本質(zhì)上是一種二叉查找樹疟位，但它在二叉查找樹的基礎上額外添加了一個標記（顏色）-
紅黑樹的特性瞻润？
image.png
- Every node is either red or black
- The root is black
- Every leaf (NIL) is black
- If a node is red, then both its children are black
- For each node, all simple paths from the node to descendant leaves contain the same number of black nodes
翻譯：
每個節(jié)點要么是紅色，要么是黑色甜刻；
根節(jié)點永遠是黑色的敢订；
所有的葉節(jié)點都是黑色的，注意這里說葉子節(jié)點是指上圖中的 NIL 節(jié)點罢吃；
每個紅色節(jié)點的兩個子節(jié)點一定都是黑色楚午；
從任一節(jié)點到其子樹中每個葉子節(jié)點的路徑都包含相同數(shù)量的黑色節(jié)點；
（五）數(shù)據(jù)結構之圖
（概念比較多尿招，整理更新中矾柜。。就谜。）
