日期：2025年8月28日
ZeroJudge 題目連結：d526. Binary Search Tree (BST)
解題想法
這題要自訂二元樹類別，遞迴版比較簡潔。
Python 程式碼
遞迴版，使用時間約為 0.7 s，記憶體約為 4 MB，通過測試。
class Node: # 自訂節點類別
def __init__(self, data):
self.data = data # 資料
self.left = None # 左子樹
self.right = None # 右子樹
class BST: # 自訂二元搜尋樹類別
def __init__(self):
self.root = None # 根節點
def insert(self, data): # 插入節點
if self.root is None: # 如果沒有根節點
self.root = Node(data) # 設定根節點
else: # 如果有根節點
self._insert(data, self.root) # 遞迴，代入 data 及 self.root
def _insert(self, data, current): # 內部使用的插入方法
if data < current.data: # 如果要插入的資料小於目前節點的資料
if current.left is None: # 如果沒有左子樹
current.left = Node(data) # data 放在左子樹
else: # 如果有左子樹
self._insert(data, current.left) # 遞迴，代入 data 及左子樹
elif data > current.data: # 如果要插入的資料大於目前節點的資料
if current.right is None: # 如果沒有右子樹
current.right = Node(data) # data 放在右子樹
else: # 如果有右子樹
self._insert(data, current.right) # 遞迴，代入 data 及右子樹
def delete(self, data): # 刪除資料
self.root = self._delete(self.root, data)
def _delete(self, current, data): # 內部使用的刪除資料方法
if current is None: # 如果 current 是空的
return current # 回傳 current 並離開函式
# 找要刪除的節點
if data < current.data: # 如果要刪除的資料小於目前節點的資料
current.left = self._delete(current.left, data) # 遞迴，代入左子樹及 data
elif data > current.data: # 如果要刪除的資料大於目前節點的資料
current.right = self._delete(current.right, data) # 遞迴，代入右子樹及 data
else: # 找到要刪除的節點
if current.left is None: # 如果左子樹是空的
return current.right # 用右子樹取代 node
elif current.right is None: # 如果右子樹是空的
return current.left # 用左子樹取代 node
# 有左、右子樹
temp = self._findMin(current.right) # 找右子樹中最小資料的節點
current.data = temp.data # current 的資料改成 temp 的資料
current.right = self._delete(current.right, temp.data) # 刪除右子樹中最小資料的節點
return current
def _findMin(self, current): # 內部使用的找最小值方法
while current.left is not None: # 向下找左子樹直到空節點為止
current = current.left
return current
def preorder(self): # 前序走訪
self._preorder(self.root)
print()
def _preorder(self, current): # 內部使用的前序走訪
if current: # 如果 current 不是 None
print(current.data, end=' ') # 印出 current.data
self._preorder(current.left) # 遞迴，代入左子樹
self._preorder(current.right) # 遞迴，代入右子樹
import sys
for line in sys.stdin:
n = int(line) # 一行有 n 個數字
tree = BST() # 建立 BST 物件
for data in map(int, input().split()): # 依序讀取此行的數字
tree.insert(data) # 將資料插入 tree 之中
tree.preorder() # 前序走訪
非遞迴版，使用時間約為 0.5 s，記憶體約為 4 MB，通過測試。
class Node: # 自訂節點類別
def __init__(self, data):
self.data = data # 資料
self.left = None # 左子樹
self.right = None # 右子樹
class BST: # 自訂二元搜尋樹類別
def __init__(self):
self.root = None # 根節點
def insert(self, data): # 插入節點
if self.root is None: # 如果沒有根節點
self.root = Node(data) # 設定根節點
return # 離開函式
# 如果有根節點
current = self.root # 目前走訪的節點，預設為根節點
parent = None # 父節點，預設為 None
while current is not None: # 往下找直到 current 是 None 為止
parent = current # 父節點設定為 current
if data < current.data: # 如果要插入的資料小於目前節點的資料
current = current.left # 走到左子樹
elif data > current.data: # 如果要插入的資料大於目前節點的資料
current = current.right # 走到右子樹
else: # BST 的節點值不能重複
print("該值已存在於樹中")
return # 離開函式
# 找到要插入的位置，與父節點的資料比大小
if data < parent.data: # data 較小，放在左子樹
parent.left = Node(data)
else: # 反之，放在右子樹
parent.right = Node(data)
def preorder(self): # 前序走訪
if self.root is None: return # 如果沒有根節點，離開函式
st = [self.root] # 堆疊，先放入根節點
while st: # 如果 st 有資料繼續執行
current = st.pop() # 讀取並移除堆疊最上方的節點
print(current.data, end=' ') # 印出 current.data
# 先放入右子樹，再放入左子樹，從堆疊取出資料時才會先讀到左子樹
if current.right: # 如果有右子樹
st.append(current.right) # 右子樹加到 st
if current.left: # 如果有左子樹
st.append(current.left) # 左子樹加到 st
print() # 換行
import sys
for line in sys.stdin:
n = int(line) # 一行有 n 個數字
tree = BST() # 建立 BST 物件
for data in map(int, input().split()): # 依序讀取此行的數字
tree.insert(data) # 將資料插入 tree 之中
tree.preorder() # 前序走訪
C++ 程式碼
遞迴版，使用時間約為 44 ms，記憶體約為 356 kB，通過測試。
#include <iostream>
using namespace std;
class Node { // 自訂節點類別
public:
int data; // 資料
Node* left; // 左子樹
Node* right; // 右子樹
Node(int val) : data(val), left(nullptr), right(nullptr) {} // 建構子
};
class BST { // 自訂二元搜尋樹類別
private:
Node* root; // 根節點
Node* insertHelper(Node* node, int data) { // 內部使用的插入資料輔助函式
if (node == nullptr) { // 如果 node 是空的
return new Node(data); // 回傳以 data 為資料建立的新節點
}
if (data < node->data) { // 如果要插入的資料小於目前節點的資料
node->left = insertHelper(node->left, data); // 遞迴，代入左子樹及 data
} else if (data > node->data) { // 如果要插入的資料大於目前節點的資料
node->right = insertHelper(node->right, data); // 遞迴，代入右子樹及 data
} else { // BST 的值不能重複
cout << "該值已存在於樹中: " << data << "\n";
}
return node; // 回傳 node 並離開函式
}
Node* findMin(Node* node) { // 內部使用的找最小資料節點函式
while(node->left != nullptr) { // 向下找左子樹直到是空的為止
node = node->left;
}
return node;
}
Node* deleteHelper(Node* node, int data) { // 內部使用的刪除資料輔助函式
if (node == nullptr) return node; // 如果 node 是空的，回傳 node 並離開函式
if (data < node->data) { // 如果要刪除的資料小於目前節點的資料
node->left = deleteHelper(node->left, data); // 遞迴，代入左子樹及 data
} else if (data > node->data) { // 如果要刪除的資料大於目前節點的資料
node->right = deleteHelper(node->right, data); // 遞迴，代入右子樹及 data
} else { // 找到要刪除的資料
if (node->left == nullptr) { // 如果左子樹是空的
Node* temp = node->right; // 暫存右子樹
delete node; // 刪除 node
return temp; // 用原來的右子樹取代被刪除的 node
} else if (node->right == nullptr) { // 如果右子樹是空的
Node* temp = node->left; // 暫存左子樹
delete node; // 刪除 node
return temp; // 用原來的左子樹取代被刪除的 node
}
// 有兩個子樹的狀況
Node* temp = findMin(node->right); // 找左子樹中最小值的節點
node->data = temp->data; // node 的資料改成 temp 的資料
node->right = deleteHelper(node->right, temp->data); // 刪除右子樹中最小值的節點
}
return node; // 回傳 node 並離開函式
}
void preorderHelper(Node* node) { // 內部使用的前序走訪輔助函式
if (node == nullptr) return; // 如果 node 是空的，離開函式
cout << node->data << " "; // 印出 node->data
preorderHelper(node->left); // 遞迴，代入左子樹
preorderHelper(node->right); // 遞迴，代入右子樹
}
void clearHelper(Node* node) { // 內部使用的刪除 BST 輔助函式
if (node == nullptr) return; // 如果 node 是空的，離開函式
clearHelper(node->left); // 遞迴，代入左子樹
clearHelper(node->right); // 遞迴，代入右子樹
delete node; // 刪除 node
}
public:
BST() : root(nullptr) {} // 建構子
~BST() { // 解構子
clearHelper(root);
}
void insert(int data) { // 插入資料
root = insertHelper(root, data);
}
void preorder() { // 前序走訪
preorderHelper(root);
cout << "\n";
}
};
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n; // 一行有 n 個數字
while(cin >> n) {
BST tree; // 建立 BST 物件
for(int i=0; i<n; i++) { // 讀取 n 個數字
int data; cin >> data;
tree.insert(data); // 將資料插入 tree 之中
}
tree.preorder(); // 前序走訪
}
return 0;
}
非遞迴版，使用時間約為 39 ms，記憶體約為 388 kB，通過測試。
#include <iostream>
#include <stack>
using namespace std;
class Node { // 自訂節點類別
public:
int data; // 資料
Node* left; // 左子樹
Node* right; // 右子樹
Node(int val) : data(val), left(nullptr), right(nullptr) {} // 建構子
};
class BST { // 自訂二元搜尋樹類別
private:
Node* root; // 根節點
public:
BST() : root(nullptr) {} // 建構子
void insert(int data) { // 插入資料
Node* newNode = new Node(data); // 建立新的節點
if (root == nullptr) { // 如果根節點是空的
root = newNode; // 以新節點作為根節點
return; // 離開函式
}
Node* current = root; // 目前走訪的節點，預設為根節點
Node* parent = nullptr; // 父節點，預設為空的
while(current != nullptr) { // 找要插入的節點位置
parent = current;
if (data < current->data) { // 如果要插入的資料小於目前節點的資料
current = current->left; // 走到左子樹
} else if (data > current->data) { // 如果要插入的資料右於目前節點的資料
current = current->right; // 走到右子樹
} else { // BST 的資料不能重複
cout << "該值已存在於樹中: " << data << "\n";
delete newNode; // 釋放記憶體
return; // 離開函式
}
}
if (data < parent->data) { // 如果要插入的資料小於父節點的資料
parent->left = newNode; // 新節點當作左子樹
} else { // 反之，當作右子樹
parent->right = newNode;
}
}
void preorder() { // 前序走訪
if (root == nullptr) return; // 如果根節點是空的，離開函式
stack<Node*> st; // 待走訪的節點
st.push(root); // 先放入根節點
while(!st.empty()) { // 如果 st 還有節點繼續執行
Node* current = st.top(); // 取出 st 最上面的節點
st.pop(); // 移除 st 最上面的節點
cout << current->data << " "; // 印出目前節點的值
// 先放入右子樹，再放入左子樹，取出節點時順序反過來
if (current->right != nullptr) {
st.push(current->right);
}
if (current->left != nullptr) {
st.push(current->left);
}
}
cout << "\n";
}
~BST() { // 解構子
clear(root);
}
private:
void clear(Node* node) { // 釋放記憶體
if (node == nullptr) return;
clear(node->left);
clear(node->right);
delete node;
}
};
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n; // 一行有 n 個數字
while(cin >> n) {
BST tree; // 建立 BST 物件
for(int i=0; i<n; i++) { // 讀取 n 個數字
int data; cin >> data;
tree.insert(data); // 將資料插入 tree 之中
}
tree.preorder(); // 前序走訪
}
return 0;
}
沒有留言:
張貼留言