一、線性表：分類：
1）線性表順序存儲：
2）線性表線性存儲：
1）單向鏈表
2）單向鏈表（企業鏈表）
3）循環鏈表（企業鏈表單向）
4）解決約瑟夫問題（用單項循環鏈表）
5）雙向鏈表
6）受限的線性表
1）棧的順序存儲（ stack ）
2）棧的鏈式存儲（ stack ）
3）隊列的順序存儲（ queue ）
4）隊列的鏈式存儲（ queue ）
5）棧的應用（1.就近匹配，用來測試編碼的括號使用規範）
6）棧的應用（2.中綴表達式轉後綴表達式）
7）（計算機）基於後綴表達式的計算；
二、樹的特點：
1）非線性結構，有 1 個直接前驅，但可能有多個直接後繼（1 ：n);
2)樹的定義具有遞歸性，樹中還有樹。
3）樹可以為空，即節點為0。
4.樹的一些專業名稱
1）節點的度：節點掛接的子樹數（即一個節點有幾個直接後繼就有幾度）。
2）節點的層次：即根到該節點的層數（根節點算一層）
3）樹的度：所有 節點的度 中的最大值
4）樹的深度(或高度）:指所有節點中的最大層數。
5）節點數：一棵樹中的所有節點個數（包括根節點）。
6）葉子節點：即終端節點，沒有後繼。
5 二叉樹
1）二叉樹的基本特徵：（1 ：2）
每個節點最多隻有兩個子樹
左子樹和右子樹的位置不能顛倒
2）二叉樹的性質：
1）在二叉樹的第 i 層上，最多隻有2^(i-1)個節點。（i > 0）
2）深度為 k 的二叉樹，最多隻有 2^k -1 個節點。（k>0）
3)對於任何一個二叉樹，若度為2 的節點有n2個，則它的葉子數必為 n2+1個。
4）滿二叉樹：深度為K,有 2^K-1 個節點。特點是：每層都充滿了節點。
6.完全二叉樹：
1）除最後一層外，每層的節點數都達到了最大值，且最後一層的節點盡力靠左。
2）對於完全二叉樹：若從上至下，從左至右編號，則編號為i的節點，其左孩子編號為 2i， 右孩子編號為 2i+1， 雙親的編號為 i/2；（i等於1時，為根除外）。
1）左孩子右兄弟：可以將一顆多叉樹轉變為二叉樹
2）遞歸遍歷（周遊）二叉樹
3）非遞歸遍歷二叉樹（用棧的方法）
4）遍歷的三種方法：
1）先序：先根再左再右
2）中序：先左再根再右
3）後序：先左再右再根
5）
1)已知二叉樹的"先序"遍歷和"後序"遍歷序列"不能"唯一地確定這這棵樹。
2)已知二叉樹的"先序"遍歷和"中序"遍歷"可以"唯一地確定這這棵樹。
1)先根據先序找到根節點，在根據中序確定根節點左右兩邊的節點
2）再根據先序找到下一個根節點，再根據中序找到根節點左右兩邊的節點。
3）"中序"、"後序"可以確定一棵樹
4)總體結論為：帶"中序"的都可以確定一棵樹，反之則確定不了
6）三種遍歷的特點：
1）先序遍歷：可以確定每棵樹的根節點。（特點： 它的輸出序列中：第一個數為樹的總根節點；剩下的子根節點，和中序遍歷可以確定）
2）中序遍歷：可以確定根節點的左右子樹。（它的特點為：輸出序列中，根節點兩邊的為它的左右子樹，和先序遍歷配合可以確定一棵樹）
閱讀更多 技匠志 的文章
