樹和二叉樹（二）

*學習資料與算法結構第二天

（一）樹的周遊

• 前序周遊
• 後序周遊
• 層次周遊

  

（二）二叉樹的概念與特性

1. 二叉樹

1.1 滿二叉樹：

完整的金字塔型。
           

1.2 完全二叉樹：

a.如果一個二叉樹有n層那n-1層就是滿二叉樹。
b.最後一層要從左至右連續排列。
           

2. 二叉樹的重要特性

a. 二叉樹在i層上最多有2^（n-1）個節點（i>=1）
b. 深度為k的二叉樹最多有2^k - 1個節點（k>=1）
c. 對任何一棵二叉樹，如果其葉子節點數為a個，度為二的節點數為b個,a = b+1
           

（三）二叉樹的周遊

• 前序周遊
• 中序周遊
• 後序周遊
• 層次周遊

注意點：

先根周遊 = 前序周遊

後根周遊 = 後序周遊

（四）樹與二叉樹的轉換

對于任意一個節點，樹的孩子節點作為它轉乘二叉樹當中的左子樹節點，樹的兄弟節點全部變成新轉出的節點的右子樹節點