資料結構：樹

授課老師

楊瑀婕

適合學習對象

高中生

課程目標

上完課程後，學生應具備的知識與能力：

• 知道「樹」這個資料結構的基礎知識、專有名詞。

• 知道二元樹的種類與其性質。

• 知道二元樹的四種走訪方式(前序、中序、後序、層序)。

• 藉由四種樹的走訪方式可以由樹推序列，序列逆推樹。

• 知道二元搜尋樹的插入、刪除與搜尋方法。

• 知道二元空間分割樹的原理。

學習表現(108課綱科技領域)

• 運 t-V-1 能了解資訊系統之運算原理。 

學習內容(108課綱科技領域)

• 資 A-V-1 重要資料結構的概念與應用。 

先備知識

• 指標(pointer)的概念。

課程單元

1. 樹是甚麼？

   • 影片連結

   • 上課講義

   • 學習單

2. 認識二元樹

   • 影片連結

   • 上課講義

   • 學習單

3. 走訪二元樹

   • 影片連結

   • 上課講義

4. 二元搜尋樹

   • 影片連結

   • 上課講義

   • 學習單

5. 二元空間分割樹

   • 影片連結

   • 上課講義

參考連結

1. 碰撞檢測的優化-四叉樹(Quadtree)  http://davidhsu666.com/archives/quadtree_in_2d/ 

2. 維基百科 

   • https://zh.m.wikipedia.org/zh-tw/%E5%9B%9B%E5%8F%89%E6%A0%91 

   • https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E7%A9%BA%E9%97%B4%E5%88%86%E5%89%B2 

3. 資料結構複習(十) : 二元搜索樹 https://medium.com/@lufor129/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B%E8%A4%87%E7%BF%92-%E5%8D%81-%E4%BA%8C%E5%85%83%E6%90%9C%E7%B4%A2%E6%A8%B9-7475815f0caa 

4. 二元空間分割樹 (Binary Space Partitioning Tree)  https://blog.csdn.net/Jane_yuhui/article/details/52608215 

5. 電腦是怎麼進行四則運算的？前序式、中序式、後序式又是什麼？ https://magiclen.org/arithmetic/