樹與二叉樹
二叉樹和樹是兩種不同的概念這一點是必須要搞清楚的在這個部分我們要掌握樹的定義二叉樹的定義及主要特征(特殊的二叉樹二叉樹的性質)在二叉樹的順序存儲結構和鏈式存儲結構方面特別是鏈式存儲結構因為很多應用都是建立在鏈式存儲基礎上例如二叉樹的遍歷(前序遍歷中序遍歷後序遍歷)就是一種典型的應用
在特殊的二叉樹中完全二叉樹的概念是必須要搞清楚的其次線索二叉樹的基本概念和構造二叉排序樹平衡二叉樹的基本概念和應用特別是二叉排序樹的基本性質和特點要能很好地理解
多棵獨立的樹就組成了森林樹的存儲結構和遍歷森林的遍歷樹和二叉樹的轉換森林和二叉樹的轉換等知識也要有了了解
最後就是樹的應用通常會作為綜合應用類試題出現包括等價類問題哈夫曼(Huffman)樹和哈夫曼編碼等
圖
在數據結構中圖的結構是最復雜的這裡的概念也是最多的我們要掌握圖的基本概念(有向圖無向圖連通路徑子圖出度入度生成樹最短路徑關鍵路徑等)
圖的存儲及基本操作主要有鄰接矩陣法和鄰接表法我們要掌握這有向圖和無向圖的這種存儲方法要清楚圖的連通和存儲方法之間的關系例如一個頂點的出度和臨界矩陣中的個數有什麼關系等等
圖的遍歷方法有深度優先搜索和廣度優先搜索我們要掌握這種遍歷方法的算法實現給出一個具體的圖要能知道它的遍歷次序
在數據結構課程中圖的基本應用是最多的也是最復雜的我們要掌握這些應用的復雜度分析要掌握的具體應用主要包括最小(代價)生成樹最短路徑拓撲排序關鍵路徑在給出的一個具體的圖中我們要會利用已知條件求出上述應用的結果
[] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23543.html
