Jason's Notes

這段程式碼定義了一個二元樹（Binary Tree）結構，並提供操作和管理樹中節點的功能。主要目的是構建一個完全二元樹，讓用戶可以輸入兩個節點的值來查找它們之間的路徑。下面是程式的詳細分解與說明：

1. 變數 MAX_DEPTH

• 設定樹的最大深度，這裡設定為 5，代表樹最多可以有 6 層（根節點為第 0 層）。這個設定影響樹的總節點數。

2. Node 類別

• 定義了樹中每個節點的結構，包括：
  • value: 節點的值（例如 A, B 等）。
  • parent_index: 父節點在節點列表中的索引，用於找出上一層節點。
  • is_right: 是否是右子節點（0 表示左子節點，1 表示右子節點）。
  • depth: 節點的深度（層數），根節點的深度為 0。
  • path: 使用位運算儲存節點的路徑，用來表示從根節點到當前節點的左右走向。

在這個程式中，path 使用位運算來表示節點從根節點到該節點的左右走向，方便在樹中存儲節點路徑。每個節點的 path 是一個整數，該整數的二進位表示了從根節點走到該節點時的左右移動方向（左為 0，右為 1）。例如，如果我們有一個完全二元樹，從根節點 A 開始，並構建以下結構：

       A
     /   \
    B     C
   / \   / \
  D   E F   G

我們可以分別查看每個節點的 path 值：

例子說明

假設每次走向左子節點為 0、右子節點為 1。節點 path 值的計算會是這樣：

1. 節點 A (根節點)

   • A 的 path 是 0，因為它是根節點，不需要任何移動。

2. 節點 B (A 的左子節點)

   • 從 A 到 B 走左邊，因此 B 的 path 是 0（二進位 0）。

3. 節點 C (A 的右子節點)

   • 從 A 到 C 走右邊，因此 C 的 path 是 1（二進位 1）。

4. 節點 D (B 的左子節點)

   • 從 A 到 B 再到 D，走向為「左 -> 左」，因此 D 的 path 是 00（二進位 00，十進位是 0）。

5. 節點 E (B 的右子節點)

   • 從 A 到 B 再到 E，走向為「左 -> 右」，因此 E 的 path 是 01（二進位 01，十進位是 1）。

6. 節點 F (C 的左子節點)

   • 從 A 到 C 再到 F，走向為「右 -> 左」，因此 F 的 path 是 10（二進位 10，十進位是 2）。

7. 節點 G (C 的右子節點)

   • 從 A 到 C 再到 G，走向為「右 -> 右」，因此 G 的 path 是 11（二進位 11，十進位是 3）。

path 值總結

path 值的用途

在二元樹中，path 可以被用來快速確定從根到任意節點的走向。例如，透過判斷 path 的二進位值中的每個位，可以知道應該向左還是向右移動。

3. BinaryTree 類別

這是管理整個二元樹的核心類別，負責樹的建立、節點的添加、路徑查找等功能。主要成員包括：

• nodes: 用於儲存所有節點的列表。
• size: 樹中當前節點的數量。
• value_to_index: 將節點值對應到節點索引的字典，便於查找節點索引。

(1) add_node 方法

• 用來添加新節點。若為根節點，則 parent_idx 設為 -1，depth 設為 0。
• 否則，根據父節點的深度和路徑來計算新節點的 depth 和 path。
• 在節點列表 nodes 中新增這個節點，並更新 value_to_index 字典。

(2) find_node_index 方法

• 查找特定值的節點索引，如果找不到，則回傳 -1。

(3) find_lca_index 方法

• 查找兩個節點的最近公共祖先（Lowest Common Ancestor, LCA）。
• 使用迴圈，使兩個節點逐層往上尋找，直到它們相遇為止。

(4) generate_path 方法

• 根據兩個節點之間的關係生成路徑字符串：
  • 從起始節點一路向上到最近公共祖先（LCA），路徑為 "上" 。
  • 從 LCA 開始，沿著左右走向到達目標節點，路徑為 "左" 或 "右"。
  • 最後合併這兩部分路徑，並回傳最終的路徑字串。

(5) find_path_between_nodes 方法

• 查找指定節點之間的路徑，顯示從 start_val 到 end_val 的路徑。
• 若節點不存在，會提示使用者。

4. main() 函數

• 用來建立並測試二元樹的主程式。
• 以完全二元樹結構建立節點，節點的值從 A 開始，並依序增加。
• 使用 deque 進行廣度優先遍歷，將父節點依次出列，再添加其左右子節點（節點值字母超過 Z 時，進入 AA, AB 等雙字母模式）。
• 最後提供互動式功能，讓使用者輸入兩個節點的值來查找並顯示它們之間的路徑。

執行流程

1. BinaryTree 類別被初始化，並建立根節點。
2. 利用 deque 來按層構建完全二元樹，直到達到最大節點數量為止。
3. 用戶可以輸入兩個節點的值來查找它們之間的路徑。程式會利用最近公共祖先（LCA）來生成路徑，顯示從起始節點到目標節點的走向。

例子

假設樹的結構如下（僅展示部分）：

       A
     /   \
    B     C
   / \   / \
  D   E F   G

若使用者輸入從 D 到 G 的路徑：

• 程式會找到 D 和 G 的最近公共祖先 A。
• D 到 A 的路徑為 "上上"。
• A 到 G 的路徑為 "右左"。
• 結果輸出 "上上右左"。

這段程式提供了有效的方法來構建完全二元樹，並以位運算儲存節點路徑，方便查找節點間的路徑。

# 定義樹的最大深度
MAX_DEPTH = 5  # 為了方便展示，這裡設為5，可以根據需要調整


# 輔助函數：生成節點名稱
def get_next_node_value(index):
    letters = []
    while index >= 0:
        letters.append(chr(index % 26 + ord("A")))
        index = index // 26 - 1
    return "".join(reversed(letters))


# 節點類，表示樹中的每個節點
class Node:
    def __init__(self, value, parent_index, is_right, depth, path):
        self.value = value  # 節點值
        self.parent_index = parent_index  # 父節點索引
        self.is_right = is_right  # 標記是左子節點還是右子節點
        self.depth = depth  # 節點深度
        self.path = path  # 使用位運算表示的路徑


# 二元樹類，用於管理樹
class BinaryTree:
    def __init__(self):
        self.nodes = []  # 節點列表
        self.size = 0  # 當前節點數量
        self.value_to_index = {}  # 節點值到索引的映射

    # 向樹中添加節點
    def add_node(self, value, parent_idx, is_right):
        print(value)
        if self.size >= (1 << (MAX_DEPTH + 1)):
            return -1

        if parent_idx == -1:
            depth = 0
            path = 0
        else:
            depth = self.nodes[parent_idx].depth + 1
            if depth >= 64:  # 使用64位整數
                print("深度超過限制")
                return -1
            path = self.nodes[parent_idx].path | (is_right << depth)

        node = Node(value, parent_idx, is_right, depth, path)
        self.nodes.append(node)
        curr_idx = self.size
        self.size += 1

        # 更新節點值到索引的映射
        self.value_to_index[value] = curr_idx

        return curr_idx

    # 查找具有給定值的節點的索引
    def find_node_index(self, value):
        return self.value_to_index.get(value, -1)

    # 利用 path 和 depth 找到最近公共祖先的索引
    def find_lca_index(self, idx1, idx2):
        node1, node2 = self.nodes[idx1], self.nodes[idx2]
        while node1.path != node2.path:
            if node1.depth > node2.depth:
                idx1 = node1.parent_index
                node1 = self.nodes[idx1]
            elif node2.depth > node1.depth:
                idx2 = node2.parent_index
                node2 = self.nodes[idx2]
            else:
                idx1, idx2 = node1.parent_index, node2.parent_index
                node1, node2 = self.nodes[idx1], self.nodes[idx2]
        return idx1

    # 使用 path 屬性生成從 start_idx 到 end_idx 的路徑字符串
    def generate_path(self, start_idx, end_idx):
        if start_idx == end_idx:
            return ""

        # 找到最近公共祖先的索引
        lca_idx = self.find_lca_index(start_idx, end_idx)

        path_parts = []

        # 從起始節點向上到LCA
        current_idx = start_idx
        while current_idx != lca_idx:
            path_parts.append("上")
            current_idx = self.nodes[current_idx].parent_index

        # 從LCA向下到目標節點
        directions = []
        current_idx = end_idx
        while current_idx != lca_idx:
            node = self.nodes[current_idx]
            if node.is_right:
                directions.append("右")
            else:
                directions.append("左")
            current_idx = node.parent_index

        path_parts.extend(reversed(directions))
        return "".join(path_parts)

    # 查找兩個節點之間的路徑並輸出
    def find_path_between_nodes(self, start_val, end_val):
        start_idx = self.find_node_index(start_val)
        end_idx = self.find_node_index(end_val)

        if start_idx == -1 or end_idx == -1:
            print("節點不存在")
            return

        path = self.generate_path(start_idx, end_idx)
        print(f"從 {start_val} 到 {end_val} 的路徑: {path}")


# 主函數，測試二元樹功能
def main():
    tree = BinaryTree()

    # 建立完全二元樹
    from collections import deque

    max_nodes = 2 ** (MAX_DEPTH + 1) - 1  # 完全二元樹的節點總數
    node_queue = deque()
    value_ord = 0  # 節點索引從0開始，將被轉換為字母表示

    # 添加根節點
    root_value = get_next_node_value(value_ord)
    root_idx = tree.add_node(root_value, -1, 0)
    node_queue.append((root_idx, value_ord))
    value_ord += 1

    while node_queue and tree.size < max_nodes:
        parent_idx, parent_value_ord = node_queue.popleft()

        # 添加左子節點
        left_value = get_next_node_value(value_ord)
        left_idx = tree.add_node(left_value, parent_idx, 0)
        node_queue.append((left_idx, value_ord))
        value_ord += 1

        # 添加右子節點
        right_value = get_next_node_value(value_ord)
        right_idx = tree.add_node(right_value, parent_idx, 1)
        node_queue.append((right_idx, value_ord))
        value_ord += 1

    # 提供交互方式，允許用戶輸入任意兩個節點的值
    print("請輸入要查找路徑的節點，輸入 'exit' 退出程序。")
    while True:
        try:
            start_val = input("請輸入起始節點: ")
            if start_val.lower() == "exit":
                break
            end_val = input("請輸入目標節點: ")
            if end_val.lower() == "exit":
                break
            tree.find_path_between_nodes(start_val.strip(), end_val.strip())
        except KeyboardInterrupt:
            print("\n程序已退出。")
            break
        except Exception as e:
            print(f"發生錯誤: {e}")


if __name__ == "__main__":
    main()

find_lca_index 函數用於找到二元樹中兩個節點的最近公共祖先（LCA, Lowest Common Ancestor），即兩個節點共同的最深祖先節點。

基本邏輯

1. 比較兩個節點的 path 屬性，若不同則逐步向上回溯，直到兩者的 path 一致，即找到共同祖先。
2. 如果兩個節點深度不同，較深的節點會先回溯到淺層，直至兩者深度相同。
3. 如果兩者深度相同且路徑不同，則同時向上回溯父節點，直到路徑相同。

示例

假設一棵二元樹的結構如下，根節點為 A，左右子節點分別依序命名為 B, C, D, E, F, G：

         A
       /   \
      B     C
     / \   / \
    D   E F   G

示例：找節點 D 和 G 的最近公共祖先

1. D 的索引為 3，G 的索引為 6。
2. 使用 find_lca_index(3, 6) 時，首先比較兩個節點的 path 值。
3. 因 D 和 G 的深度相同，但 path 不同，因此兩者同時回溯到其父節點，分別是 B 和 C。
4. 接下來，B 和 C 的深度相同，但仍然 path 不同，繼續回溯到其父節點 A。
5. A 是 D 和 G 的最近公共祖先，因此返回 A 的索引 0。

此過程確認 find_lca_index 可以通過路徑和深度找到最靠近根的公共祖先。

當我們使用 find_lca_index 函數時，會利用每個節點的 path 值來加速找到兩個節點的最近公共祖先（LCA）。以下是一個完整說明，包括 path 值的計算方式、範例，以及加上 path 後提高效能的原因。

path 屬性的計算方式

path 屬性是一個整數，使用位運算來表示從根節點到當前節點的路徑：

• 根節點的 path 為 0。
• 對於每個子節點，若為左子節點，則 path 保持不變；若為右子節點，則將 path 的第 depth 位設為 1。
• 這樣，每個節點的 path 就可以唯一地表示從根節點出發的路徑。

例如：

1. 根節點 A 的 path = 0。
2. A 的左子節點 B 仍保持 path = 0（因為是左子節點）。
3. A 的右子節點 C 的 path 為 1（因為是右子節點）。
4. B 的左子節點 D 繼承 B 的 path = 0。
5. B 的右子節點 E 的 path 為 10（即 2，因為是 B 的右子節點，在第 2 位設為 1）。
6. 同理，C 的左子節點 F 的 path 為 01（即 1），C 的右子節點 G 的 path 為 11（即 3）。

樹結構的節點及其對應 path 值：

         A (path=0)
       /       \
   B (path=0)   C (path=1)
     /   \       /     \
D (0)   E (2)  F (1)   G (3)

find_lca_index 的示例與過程

假設要找 D 和 G 的最近公共祖先：

1. D 的索引為 3，path 為 0，深度為 2。
2. G 的索引為 6，path 為 3，深度也為 2。

我們在 find_lca_index 中的比較過程為：

1. D 和 G 的 path 不同，但深度相同，因此同時回溯到各自的父節點，分別是 B 和 C。
2. B 和 C 的 path 仍然不同，繼續回溯到 A。
3. 在 A 處，path 相同（均為 0），因此 A 是 D 和 G 的最近公共祖先，返回 A 的索引 0。

使用 path 提高效能的原因

傳統方法需要沿樹逐層回溯父節點以找到公共祖先，而 path 可以壓縮多層回溯的操作，提供更快速的判斷：

• path 用位元表示樹路徑，對比節點只需判斷 path 值是否一致，大幅減少比較操作。
• 當 path 不同且深度一致時，可以一次性向上找到公共祖先，而不必多層次逐步上溯。

這種方法利用了整數位元的快速比較特性，有效地優化了查找的速度，特別是在深度較大的樹中，可以顯著提升查找效率。

# 查找最近公共祖先的索引 **第一版**：
def find_lca_index(self, idx1, idx2):
    node1_idx = idx1
    node2_idx = idx2

    node1 = self.nodes[node1_idx]
    node2 = self.nodes[node2_idx]

    while node1_idx != node2_idx:
        if node1.depth > node2.depth:
            node1_idx = node1.parent_index
            node1 = self.nodes[node1_idx]
        elif node2.depth > node1.depth:
            node2_idx = node2.parent_index
            node2 = self.nodes[node2_idx]
        else:
            node1_idx = node1.parent_index
            node2_idx = node2.parent_index
            node1 = self.nodes[node1_idx]
            node2 = self.nodes[node2_idx

# 利用 path 和 depth 找到最近公共祖先的索引  **第二版**：
def find_lca_index(self, idx1, idx2):
    # 獲取兩個節點的初始節點對象
    node1, node2 = self.nodes[idx1], self.nodes[idx2]

    # 當兩個節點的 path 不相等時，進行回溯以找到公共祖先
    while node1.path != node2.path:
        # 如果 node1 深度大於 node2，則將 node1 向上移動至父節點
        if node1.depth > node2.depth:
            idx1 = node1.parent_index
            node1 = self.nodes[idx1]
        # 如果 node2 深度大於 node1，則將 node2 向上移動至父節點
        elif node2.depth > node1.depth:
            idx2 = node2.parent_index
            node2 = self.nodes[idx2]
        # 如果兩個節點的深度相同，則同時向上移動到各自的父節點
        else:
            idx1, idx2 = node1.parent_index, node2.parent_index
            node1, node2 = self.nodes[idx1], self.nodes[idx2]

    # 當 node1 和 node2 的 path 相等時，即找到了最近公共祖先
    return idx1

這裡是完整的 15 個節點樹狀結構 path 值表示，其中每個節點的 path 值根據從根節點 A 移動的方向來計算。0 表示向左移動，1 表示向右移動。

這些 path 值能夠在樹的深度和節點關係中提供快速查找功能，尤其是使用 path 值進行公共祖先查找時。

在這兩個版本的 find_lca_index 中，主要區別在於條件的檢查方式。第一個版本直接比較兩個節點的索引，利用索引回溯至同一節點；第二個版本則比較兩個節點的 path，而回溯流程上是類似的。

效能分析

1. 第一版：

   • 直接比對索引 (node1_idx 和 node2_idx)，當兩者相同即找到最近公共祖先。當兩者深度不同時，會將較深的節點上移至父節點，否則同時將兩者上移。
   • 效能優點：操作相對簡潔，直接使用索引對比，減少了對 path 的檢查操作。

2. 第二版：

   • 比較兩個節點的 path，當 path 不同時才進行回溯操作。
   • 效能優點：當樹具有多層且每層節點密集時，path 可以有效縮短查找最近公共祖先的步數。因為如果 path 不同，說明兩個節點在不同的分支中，能有效地排除分支差異，從而更快定位到共同的祖先。

效能結論

第二版使用 path 來進行篩選，尤其在多層大樹結構中，能夠減少冗餘的節點回溯數量，因此 在深層且節點數量多的樹結構中，會更具效能優勢。