120 lines
3.2 KiB
Rust
120 lines
3.2 KiB
Rust
use std::io::{self, BufRead};
|
|
|
|
struct BST {
|
|
val: i32,
|
|
left: Option<Box<BST>>,
|
|
right: Option<Box<BST>>,
|
|
}
|
|
|
|
impl BST {
|
|
fn new(val: i32) -> Self {
|
|
BST {
|
|
val,
|
|
left: None,
|
|
right: None,
|
|
}
|
|
}
|
|
|
|
fn insert(&mut self, val: i32) {
|
|
if val < self.val {
|
|
match self.left.as_mut() {
|
|
Some(left) => left.insert(val),
|
|
None => self.left = Some(Box::new(BST::new(val))),
|
|
}
|
|
} else if val > self.val {
|
|
match self.right.as_mut() {
|
|
Some(right) => right.insert(val),
|
|
None => self.right = Some(Box::new(BST::new(val))),
|
|
}
|
|
}
|
|
}
|
|
|
|
fn find_min(&self) -> i32 {
|
|
match self.left.as_ref() {
|
|
Some(left) => left.find_min(),
|
|
None => self.val,
|
|
}
|
|
}
|
|
|
|
fn delete(node: Option<Box<BST>>, val: i32) -> Option<Box<BST>> {
|
|
let mut node = node?;
|
|
|
|
if val < node.val {
|
|
node.left = Self::delete(node.left.take(), val);
|
|
} else if val > node.val {
|
|
node.right = Self::delete(node.right.take(), val);
|
|
} else {
|
|
if node.left.is_none() {
|
|
return node.right;
|
|
} else if node.right.is_none() {
|
|
return node.left;
|
|
} else {
|
|
let min_right = node.right.as_ref().unwrap().find_min();
|
|
node.val = min_right;
|
|
node.right = Self::delete(node.right.take(), min_right);
|
|
}
|
|
}
|
|
Some(node)
|
|
}
|
|
|
|
fn inorder(&self, res: &mut Vec<String>) {
|
|
if let Some(left) = self.left.as_ref() {
|
|
left.inorder(res);
|
|
}
|
|
res.push(self.val.to_string());
|
|
if let Some(right) = self.right.as_ref() {
|
|
right.inorder(res);
|
|
}
|
|
}
|
|
|
|
fn preorder(&self, res: &mut Vec<String>) {
|
|
res.push(self.val.to_string());
|
|
if let Some(left) = self.left.as_ref() {
|
|
left.preorder(res);
|
|
}
|
|
if let Some(right) = self.right.as_ref() {
|
|
right.preorder(res);
|
|
}
|
|
}
|
|
}
|
|
|
|
fn main() {
|
|
let stdin = io::stdin();
|
|
let mut reader = stdin.lock();
|
|
let mut line = String::new();
|
|
|
|
reader.read_line(&mut line).unwrap();
|
|
let n: i32 = line.trim().parse().unwrap_or(0);
|
|
|
|
let mut bst: Option<Box<BST>> = None;
|
|
|
|
for _ in 0..n {
|
|
line.clear();
|
|
reader.read_line(&mut line).unwrap();
|
|
let parts: Vec<&str> = line.split_whitespace().collect();
|
|
if parts.len() < 2 { continue; }
|
|
|
|
let val = parts[1].parse::<i32>().unwrap();
|
|
if parts[0] == "Insert" {
|
|
if let Some(tree) = bst.as_mut() {
|
|
tree.insert(val);
|
|
} else {
|
|
bst = Some(Box::new(BST::new(val)));
|
|
}
|
|
} else {
|
|
bst = BST::delete(bst, val);
|
|
}
|
|
}
|
|
|
|
if let Some(tree) = bst {
|
|
let mut in_res = Vec::new();
|
|
tree.inorder(&mut in_res);
|
|
println!("{} ", in_res.join(" "));
|
|
|
|
println!();
|
|
|
|
let mut pre_res = Vec::new();
|
|
tree.preorder(&mut pre_res);
|
|
println!("{} ", pre_res.join(" "));
|
|
}
|
|
} |