樹基礎

引入

圖論中的樹和現實生活中的樹長得一樣，只不過我們習慣於處理問題的時候把樹根放到上方來考慮。這種數據結構看起來像是一個倒掛的樹，因此得名。

定義

一個沒有固定根結點的樹稱為 無根樹（unrooted tree）。無根樹有幾種等價的形式化定義：

• 有 \(n\) 個結點，\(n-1\) 條邊的連通無向圖

• 無向無環的連通圖

• 任意兩個結點之間有且僅有一條簡單路徑的無向圖

• 任何邊均為橋的連通圖

• 沒有圈，且在任意不同兩點間添加一條邊之後所得圖含唯一的一個圈的圖

在無根樹的基礎上，指定一個結點稱為 根，則形成一棵 有根樹（rooted tree）。有根樹在很多時候仍以無向圖表示，只是規定了結點之間的上下級關係，詳見下文。

有關樹的定義

適用於無根樹和有根樹

• 森林（forest）：每個連通分量（連通塊）都是樹的圖。按照定義，一棵樹也是森林。

• 生成樹（spanning tree）：一個連通無向圖的生成子圖，同時要求是樹。也即在圖的邊集中選擇 \(n - 1\) 條，將所有頂點連通。

• 無根樹的葉結點（leaf node）：度數不超過 \(1\) 的結點。

  為什麼不是度數恰為 \(1\)？

  考慮 \(n = 1\)。

• 有根樹的葉結點（leaf node）：沒有子結點的結點。

只適用於有根樹

• 父親（parent node）：對於除根以外的每個結點，定義為從該結點到根路徑上的第二個結點。
  根結點沒有父結點。
• 祖先（ancestor）：一個結點到根結點的路徑上，除了它本身外的結點。
  根結點的祖先集合為空。
• 子結點（child node）：如果 \(u\) 是 \(v\) 的父親，那麼 \(v\) 是 \(u\) 的子結點。
  子結點的順序一般不加以區分，二叉樹是一個例外。
• 結點的深度（depth）：到根結點的路徑上的邊數。
• 樹的高度（height）：所有結點的深度的最大值。
• 兄弟（sibling）：同一個父親的多個子結點互為兄弟。
• 後代（descendant）：子結點和子結點的後代。
  或者理解成：如果 \(u\) 是 \(v\) 的祖先，那麼 \(v\) 是 \(u\) 的後代。

• 子樹（subtree）：刪掉與父親相連的邊後，該結點所在的子圖。

  

特殊的樹

• 鏈（chain/path graph）：滿足與任一結點相連的邊不超過 \(2\) 條的樹稱為鏈。

• 菊花/星星（star）：滿足存在 \(u\) 使得所有除 \(u\) 以外結點均與 \(u\) 相連的樹稱為菊花。

• 有根二叉樹（rooted binary tree）：每個結點最多隻有兩個兒子（子結點）的有根樹稱為二叉樹。常常對兩個子結點的順序加以區分，分別稱之為左子結點和右子結點。
  大多數情況下，二叉樹 一詞均指有根二叉樹。

• 完整二叉樹（full/proper binary tree）：每個結點的子結點數量均為 0 或者 2 的二叉樹。換言之，每個結點或者是樹葉，或者左右子樹均非空。

  

• 完全二叉樹（complete binary tree）：只有最下面兩層結點的度數可以小於 2，且最下面一層的結點都集中在該層最左邊的連續位置上。

  

• 完美二叉樹（perfect binary tree）：所有葉結點的深度均相同，且所有非葉節點的子節點數量均為 2 的二叉樹稱為完美二叉樹。

  

Warning

Proper binary tree 的漢譯名稱不固定，且完全二叉樹和滿二叉樹的定義在不同教材中定義不同，遇到的時候需根據上下文加以判斷。

OIers 所説的「滿二叉樹」多指完美二叉樹。

存儲

只記錄父結點

用一個數組 parent[N] 記錄每個結點的父親結點。

這種方式可以獲得的信息較少，不便於進行自頂向下的遍歷。常用於自底向上的遞推問題中。

鄰接表

• 對於無根樹：為每個結點開闢一個線性列表，記錄所有與之相連的結點。

  std::vector<int> adj[N];
  

• 對於有根樹：
  • 方法一：若給定的是無向圖，則仍可以上述形式存儲。下文將介紹如何區分結點的上下關係。
  • 方法二：若輸入數據能夠確保結點的上下關係，則可以利用這個信息。為每個結點開闢一個線性列表，記錄其所有子結點；若有需要，還可在另一個數組中記錄其父結點。

    std::vector<int> children[N];
    int parent[N];
    

    當然也可以用其他方式（如鏈表）替代 std::vector。

左孩子右兄弟表示法

過程

對於有根樹，存在一種簡單的表示方法。

首先，給每個結點的所有子結點任意確定一個順序。

此後為每個結點記錄兩個值：其 第一個子結點 child[u] 和其 下一個兄弟結點 sib[u]。若沒有子結點，則 child[u] 為空；若該結點是其父結點的最後一個子結點，則 sib[u] 為空。

實現

遍歷一個結點的所有子結點可由如下方式實現。

int v = child[u];  // 從第一個子結點開始
while (v != EMPTY_NODE) {
  // ...
  // 處理子結點 v
  // ...
  v = sib[v];  // 轉至下一個子結點，即 v 的一個兄弟
}

也可簡寫為以下形式。

for (int v = child[u]; v != EMPTY_NODE; v = sib[v]) {
  // ...
  // 處理子結點 v
  // ...
}

二叉樹

需要記錄每個結點的左右子結點。

實現

int parent[N];
int lch[N], rch[N];
// -- or --
int child[N][2];

樹的遍歷

樹上 DFS

在樹上 DFS 是這樣的一個過程：先訪問根節點，然後分別訪問根節點每個兒子的子樹。

可以用來求出每個節點的深度、父親等信息。

二叉樹 DFS 遍歷

先序遍歷

按照 根，左，右 的順序遍歷二叉樹。

實現

void preorder(BiTree* root) {
  if (root) {
    cout << root->key << " ";
    preorder(root->left);
    preorder(root->right);
  }
}

中序遍歷

按照 左，根，右 的順序遍歷二叉樹。

實現

void inorder(BiTree* root) {
  if (root) {
    inorder(root->left);
    cout << root->key << " ";
    inorder(root->right);
  }
}

後序遍歷

按照 左，右，根 的順序遍歷二叉樹。

實現

void postorder(BiTree* root) {
  if (root) {
    postorder(root->left);
    postorder(root->right);
    cout << root->key << " ";
  }
}

反推

已知中序遍歷序列和另外一個序列可以求第三個序列。

1. 前序的第一個是 root，後序的最後一個是 root。
2. 先確定根節點，然後根據中序遍歷，在根左邊的為左子樹，根右邊的為右子樹。
3. 對於每一個子樹可以看成一個全新的樹，仍然遵循上面的規律。

樹上 BFS

從樹根開始，嚴格按照層次來訪問節點。

BFS 過程中也可以順便求出各個節點的深度和父親節點。

樹的層序遍歷

樹層序遍歷是指按照從根節點到葉子節點的層次關係，一層一層的橫向遍歷各個節點。根據 BFS 的定義可以知道，BFS 所得到的遍歷順序就是一種層序遍歷。但層序遍歷要求將不同的層次區分開來，所以其結果通常以二維數組的形式表示。

例如，下圖的樹的層序遍歷的結果是 [[1], [2, 3, 4], [5, 6]]（每一層從左向右）。

實現

vector<vector<int>> levelOrder(Node* root) {
  if (!root) {
    return {};
  }
  vector<vector<int>> res;
  queue<Node*> q;
  q.push(root);
  while (!q.empty()) {
    int currentLevelSize = q.size();  // 當前層的節點個數
    res.push_back(vector<int>());
    for (int i = 0; i < currentLevelSize; ++i) {
      Node* cur = q.front();
      q.pop();
      res.back().push_back(cur->val);
      for (Node* child : cur->children) {  // 把子節點都加入
        q.push(child);
      }
    }
  }
  return res;
}

二叉樹 Morris 遍歷

二叉樹遍歷的核心問題是，當遍歷當前節點的子節點後，如何返回當前節點並繼續遍歷。遍歷二叉樹的遞歸方法和非遞歸方法都使用了棧結構，記錄返回路徑，來實現從下層到上層的移動。其空間複雜度最好時為 \(O(\log n)\)，最壞時為 \(O(n)\)（二叉樹呈線性）。

Morris 遍歷的實質是避免使用棧，利用底層節點空閒的 right 指針指回上層的某個節點，從而完成下層到上層的移動。

Morris 遍歷的過程

假設來到當前節點 cur，開始時來到根節點位置。

1. 如果 cur 為空時遍歷停止，否則進行以下過程。
2. 如果 cur 沒有左子樹，cur 向右移動（cur = cur->right）。
3. 如果 cur 有左子樹，找到左子樹上最右的節點，記為 mostRight。
   • 如果 mostRight 的 right 指針指向空，讓其指向 cur，然後 cur 向左移動（cur = cur->left）。
   • 如果 mostRight 的 right 指針指向 cur，將其修改為 null，然後 cur 向右移動（cur = cur->right）。

例如，cur 從節點 1 開始訪問。

cur 第一次訪問節點 2 時，找到左子樹上最右的節點 4，將 4 的 right 指針指向 cur（節點 2)。

cur 通過 4 的 right 指針返回上層，第二次訪問節點 2 時，找到左子樹上最右節點 4，將 4 的 right 指針修改為 null，然後繼續訪問右子樹。之後的過程省略。

整棵樹的訪問順序是 1242513637。可以發現有左子樹的節點訪問兩次，沒有左子樹的節點只訪問一次。

實現

void morris(TreeNode* root) {
  TreeNode* cur = root;
  while (cur) {
    if (!cur->left) {
      // 如果當前節點沒有左子節點，則輸出當前節點的值並進入右子樹
      std::cout << cur->val << " ";
      cur = cur->right;
      continue;
    }
    // 找到當前節點的左子樹的最右節點
    TreeNode* mostRight = cur->left;
    while (mostRight->right && mostRight->right != cur) {
      mostRight = mostRight->right;
    }
    if (!mostRight->right) {
      // 如果最右節點的right指針為空，將其指向當前節點，並進入左子樹
      mostRight->right = cur;
      cur = cur->left;
    } else {
      // 如果最右節點的right指針指向當前節點，説明左子樹已經遍歷完畢，輸出當前節點的值並進入右子樹
      mostRight->right = nullptr;
      std::cout << cur->val << " ";
      cur = cur->right;
    }
  }
}

無根樹

過程

樹的遍歷一般為深度優先遍歷，這個過程中最需要注意的是避免重複訪問結點。

由於樹是無環圖，因此只需記錄當前結點是由哪個結點訪問而來，此後進入除該結點外的所有相鄰結點，即可避免重複訪問。

實現

void dfs(int u, int from) {
  // 遞歸進入除了 from 之外的所有子結點
  // 對於出發結點，from 為空，故會訪問所有相鄰結點，這與期望一致
  for (int v : adj[u])
    if (v != from) {
      dfs(v, u);
    }
}

// 開始遍歷時
int EMPTY_NODE = -1;  // 一個不存在的編號
int root = 0;         // 任取一個結點作為出發點
dfs(root, EMPTY_NODE);

有根樹

對於有根樹，需要區分結點的上下關係。

考察上面的遍歷過程，若從根開始遍歷，則訪問到一個結點時 from 的值，就是其父結點的編號。

通過這個方式，可以對於無向的輸入求出所有結點的父結點，以及子結點列表。

本頁面部分內容引用自博文 二叉樹：前序遍歷、中序遍歷、後續遍歷，遵循 CC 4.0 BY-SA 版權協議。

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用