高考申論題
115年
[資訊處理] 資料結構
第 鿩 題
📖 題組：
給定一棵二元搜尋樹（binary search tree），且該樹同時也是一棵 AVL 樹。 樹的節點在 C 語言中宣告如下： ```c typedef struct Node { int key; // 節點的鍵值，所有節點的鍵值皆互不相同 int size; // 以該節點為根的子樹節點總數 (包含自己) struct Node *left; // 指向左子節點 struct Node *right; // 指向右子節點 } Node; ``` 並定義以下函式： `int size (Node *node)`： 若傳入的 node 為 NULL，則回傳 0；否則回傳 node -> size。 `int count_less_equal (Node *node, int val)`： 回傳以 node 為根的子樹中，所有鍵值小於等於 val 的節點總數。 `Node* select (Node *node, int r)`： 回傳以 node 為根的子樹中，第 r 小的節點指標，r 從 1 開始算。 `Node* greater_k_smallest (Node *root, int val, int k)`： 找出以 root 為根的整棵樹中，所有鍵值大於 val 的節點裡，第 k 小的節點，k 從 1 開始算。若第 k 小的節點不存在，則回傳 NULL。
給定一棵二元搜尋樹（binary search tree），且該樹同時也是一棵 AVL 樹。 樹的節點在 C 語言中宣告如下： ```c typedef struct Node { int key; // 節點的鍵值，所有節點的鍵值皆互不相同 int size; // 以該節點為根的子樹節點總數 (包含自己) struct Node *left; // 指向左子節點 struct Node *right; // 指向右子節點 } Node; ``` 並定義以下函式： `int size (Node *node)`： 若傳入的 node 為 NULL，則回傳 0；否則回傳 node -> size。 `int count_less_equal (Node *node, int val)`： 回傳以 node 為根的子樹中，所有鍵值小於等於 val 的節點總數。 `Node* select (Node *node, int r)`： 回傳以 node 為根的子樹中，第 r 小的節點指標，r 從 1 開始算。 `Node* greater_k_smallest (Node *root, int val, int k)`： 找出以 root 為根的整棵樹中，所有鍵值大於 val 的節點裡，第 k 小的節點，k 從 1 開始算。若第 k 小的節點不存在，則回傳 NULL。
完成下列程式碼的空格。（20 分）
```c
int count_less_equal(Node *node, int val) {
if (node == NULL) return 0;
if (node->key > val)
return count_less_equal(node->left, val);
else return size(node->left)+ (1) ;
}
Node* select(Node *node, int r) {
int left_size = size(node->left);
if (r == (2) ) return node;
else if (r <= left_size)
return select(node->left, r);
else return (3) ;
}
Node* greater_k_smallest(Node *root, int val, int k){
int x = count_less_equal(root, val);
int y = (4) ;
if (y > size(root)) return NULL;
return select(root, y);
}
```
```c
int count_less_equal(Node *node, int val) {
if (node == NULL) return 0;
if (node->key > val)
return count_less_equal(node->left, val);
else return size(node->left)+ (1) ;
}
Node* select(Node *node, int r) {
int left_size = size(node->left);
if (r == (2) ) return node;
else if (r <= left_size)
return select(node->left, r);
else return (3) ;
}
Node* greater_k_smallest(Node *root, int val, int k){
int x = count_less_equal(root, val);
int y = (4) ;
if (y > size(root)) return NULL;
return select(root, y);
}
```
📝 此題為申論題
思路引導 VIP
本題測試擴充的二元搜尋樹（Order Statistic Tree）操作。
(1) count_less_equal 中，若 current key <= val，則該節點及其左子樹所有點都 <= val。故數量應為 左子樹大小 + 1(自己) + 尋找右子樹中符合條件的數量。因此 (1) 應為 1 + count_less_equal(node->right, val)。
🤖
AI 詳解
AI 專屬家教
【考點分析】 二元搜尋樹（BST）的階序統計（Order Statistics）擴充，利用子樹大小（Size）來實作快速尋找第 K 小元素及區間計數。 【理論/法規依據】
▼ 還有更多解析內容