前言

昨天介紹了Binary tree的定義特性，今天講講儲存方式與走訪。

Binary Tree的儲存

• 一維陣列

< Complete Binary tree >

< Binary tree >

• 二維陣列
• 鏈結

Binary Tree Traversal

圖形有走訪，tree也有走訪，按照順序，逐一走訪tree上的node。
簡單來說，就是 Tree中的所有節點都要走過一次

• 以一個最簡單的Binary tree 來當示意圖:
  
  那我們要走訪每一個點會有6種可能: ABC、ACB、BAC、BCA、CAB、CBA。
  但是，依照Binary tree的特性，都是由左向右，那就只會剩下3種方式:ABC、BAC、BCA。
  那又將這3種方式，分別命名為前序、中序、後序走訪。

• 前序走訪 (preorder traverse)
  1.目前節點 / Root
  2.left subtree
  3.right subtree

  • 以下圖為例子:
    
    => A -> B -> C
  • Hint: 前序走訪就是 root在前面

• 中序走訪 (inorder traverse)
  1.left subtree
  2.目前節點 / Root
  3.right subtree

  • 以下圖為例子:
    
    => B -> A -> C
  • Hint: 中序走訪就是 root在中間

• 後序走訪 (postorder traverse)
  1.left subtree
  2.right subtree
  3.目前節點 / Root

  • 以下圖為例子:
    
    => B -> C -> A
  • Hint: 後序走訪就是 root在後面

參考

細談資料結構 第六版
ISBN 978-986-312-014-8