# 1.4 Tree

由邊和節點構成的資料結構, 節點通常就是儲存資料的實體.

```
     o  -> root node
    / \
   o   o
  / \   \
 o   o   o -> 這層都是葉節點
```

## 常見術語

根: 樹的頂端節點, 一棵樹只有一個根

邊: 節點到節點的連接

路徑: 沿著邊, 從一個節點走到另一個節點, 所經過的節點順序稱為路徑

父節點, 子節點

節點, 葉節點(沒有子節點的節點)

度: 一個節點所包含的子節點數

子樹

層: 從根開始到指定節點的層數, 也稱為高度或深度

走訪: 按照某個特定的順序存取節點

關鍵字: 節點物件域中的某個屬性, 用來識別節點物件

## 二元樹

### 定義: 樹中的每個節點, 最多只能有兩個子節點

對二元樹的理解

1. 二元樹與樹的區別為:

   a. 樹中節點的子節點樹沒有限制, 而二元樹中限制節點數為不超過兩個

   b. 樹的節點沒有左右之分, 但二元樹的節點是分左右的
2. 二元樹有五種基本型態

   a. 空二元樹, 連根節點都沒有

   b. 只有一個根節點的二元樹

   c. 只有左樹

   d. 只有右樹

   e. 完全二元樹(complete binary tree): 若設二元樹的高度為h, 除了第h層外, 其它各層的節點樹都達到最大個數,

   第h層有葉節點, 並且葉節點都是從左到右依次排序, 此即完全二元樹
3. 滿二元樹(full binary tree): 除了葉節點外, 每個節點都有左右子節點, 且葉節點都處在最底層
4. 滿二元樹必為完全二元樹, 完全二元樹不必然為滿二元樹
5. 二元樹常被用作二元搜尋樹(Binary Search Tree, a.k.a BST), 二元排序樹, 二元堆(Binary Heap, a.k.a Heap Tree)

## 性質

性質1. 在二元樹的第i層上至多有2^(i-1)個節點

性質2. 深度為k的二元樹至多有(2^k)-1個節點

性質3. 對任何一顆二元樹T, 若其終端節點數量為n0, 度為2的節點數為n2, 則n0=n2+1

性質4. 具有N個節點的完全二元樹的深度為\[log2以N為底]+1

性質5. 如果對一顆有n個節點的完全二元樹的節點按層序編號, 即從第1層到第\[log2以n為底]+1層,

每層從左到右, 對任一節點i(1 <= i <= n)有:

a. 若i = 1, 則節點i是二元樹的根; 若i > 1, 則其父節點是\[i/2]

b. 若2i > n, 則節點i無左子節點; 否則其左子節點是2i. 即該節點是葉節點

c. 若2i+1 > n, 則節點i無右子節點; 否則其右子節點是2i+1

d. 若i為奇數且不小於1, 則Ki的左兄弟編號是i-1; 否則Ki無左兄弟

d. 若i為偶數且小於n, 則Ki的右兄弟編號是i+1; 否則Ki無右兄弟


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://clu.gitbook.io/data-structure-note/tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.