# DS Tree

{%hackmd theme-dark %}

## 樹

:::info
某張圖是一棵樹，若且唯若
* 連通無環
* 任兩點恰有一條路徑
* 連通且點數 = 邊數 + 1
* 連通但移除任意一條邊會導致不連通
* 沒有環但加任何一條邊會導致有環
:::

## 名詞定義

* 環：沿著邊走可以走回起點
* 節點：樹上的每個點
* 分支：連接任兩點的邊
* 根：視為從該點延伸形成樹的節點，樹上任一節點都可視為根
* 親代節點：任相連兩點較靠近根者
* 子代節點：任相連兩點較遠離根者
* 同輩節點：相同親代節點的兩節點
* 祖宗節點：位於根到某節點路徑上的節點
* 後代節點：位於某節點到葉節點路徑上的節點
* 葉節點：不再延伸的節點，又稱**終端節點**
* 階層：節點到根的路徑長
* 高度：階層最大值
* 分支度：又稱階度，所有節點的支度最大值
* 子樹：由一節點及其後代構成的集合
* 森林：樹的集合

## 實作

struct TreeNode{
  int val;
  vector<TreeNode*> childs;
};

## 二元樹

:::info
* 樹為空
* 或者樹的分支度不超過2
:::

* 平衡二元樹：每個節點的左右子樹高度差不超過1
* 完全二元樹：除了葉節點層以外其他各層節點數達最大值，且葉節點層由左往右加
* 完滿二元樹：除了葉節點外所有節點都有左右子節點

### 二元樹高度、節點數

高度 $h$, 節點數 $< 2^h - 1$

## 二元樹實作

### Array-based

:::info
* 設 T 為長度 4(通常設為4)*N 的陣列，其中 N 為最大節點數
* 根節點為 T[1]
* 對於節點 $i$，其左子節點為 T[$i*2$]
* 對於節點 i, 其右子節點為 T[$i*2+1$]
:::

### Pointer-based

struct TNode{
    int val;
    TNode *l, *r;
};

### 遍歷

* 前序：根節點 左子樹 右子樹

void PreOrder( Node *k ){
    if (!k) return;
    cout << k << endl;
    PreOrder( k->leftChild );
    PreOrder( k->rightChild);
}

* 中序：左子樹 根節點 右子樹

void InOrder( Node *k ){
    if (!k) return;
    InOrder( k->leftChild );
    cout << k << endl;
    InOrder( k->rightChild );
}

* 後序：左子樹 右子樹 根節點

void PostOrder( Node *k ){
    if (!k) return;
    PostOrder( k->leftChild );
    PostOrder( k->rightChild );
    cout << k << endl;
}