一、隊列

? ? ? ? 隊列是只允許一段進行插入，另一端進行刪除操作的線性表；

? ? ? ? 允許插入的一端叫隊尾，允許刪除的一端叫對頭；

? ? ? ? 先進先出；

? ? ? ? 用于解決速度不匹配（例如一快一慢），做緩沖用；

二、樹

? ? ? ? 1.樹：有n個結點的有限集合，n=0時是空樹；

? ? ? ? 在任意非空樹中：有且僅有一個根結點；n>1時又分幾個互不相交子樹；

? ? ? ? 結點擁有子樹的個數稱謂為度；

? ? ? ? 度為0的（最下面的）叫葉子結點，度不為0的（中間的）叫分支結點；

? ? ? ? 度最大的結點的度數叫樹的度；

? ? ? ? 樹的高度（或深度）從根開始，根為第一層，根的孩子為第二層；

? ? ? ? 2.二叉樹

? ? ? ? n個結點的有限集合，集合要么為空樹，要么由一個根結點和兩顆互不相交的二叉樹組成；

? ? ? ? 每個結點最多兩個子樹；左子樹和右子樹是有順序的，次序不能顛倒；如果結點只有一個子樹也要區分左右子樹；

? ? ? ? 斜樹：假設所有結點都只有左子樹的叫左斜樹；

? ? ? ? 滿二叉樹：所有分支都存在左右子樹，葉子節點都在同一層；

? ? ? ? 完全二叉樹 ：按層序編號的二叉樹；

? ? ? ? 特性：

? ? ? ? （1）在第i層最多有2的i-1次方（2^(i-1)）個結點；

? ? ? ? （2）深度為k的二叉樹最多有2的k次方-1個結點（2^k-1）；

? ? ? ? （3）一個二叉樹，如果有n0個葉子結點，度數為2的結點數為n0-1；

? ? ? ? （4）有n個結點的完全二叉樹深度為(logn/long2)+1；

? ? ? ? 3.樹的層序遍歷（廣度遍歷）

? ? ? ? 4.樹的深度遍歷（前序，中序，后序）

? ? ? ? ? ? ? ? 前序：根左右：先訪問根，然后訪問左，訪問右；

????????????????中序：左根右：從根開始（不訪問），先訪問左，再訪問根，最后訪問右；

????????????????后序：左右根：從根開始（不訪問），先訪問左，再訪問右，最后訪問根；

????????

????????

????????