一、線性表:分類:
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)中序遍歷:可以確定根節點的左右子樹。(它的特點為:輸出序列中,根節點兩邊的為它的左右子樹,和先序遍歷配合可以確定一棵樹)
閱讀更多 技匠志 的文章