121 lines
3.3 KiB
Rust
121 lines
3.3 KiB
Rust
use std::alloc::{alloc, dealloc, Layout};
|
|
use std::io::{self, BufRead};
|
|
use std::ptr;
|
|
|
|
struct Node {
|
|
val: i32,
|
|
left: *mut Node,
|
|
right: *mut Node,
|
|
}
|
|
|
|
impl Node {
|
|
unsafe fn new(val: i32) -> *mut Node {
|
|
let layout = Layout::new::<Node>();
|
|
let ptr = alloc(layout) as *mut Node;
|
|
if !ptr.is_null() {
|
|
ptr::write(ptr, Node { val, left: ptr::null_mut(), right: ptr::null_mut() });
|
|
}
|
|
ptr
|
|
}
|
|
}
|
|
|
|
unsafe fn insert(root: *mut Node, val: i32) -> *mut Node {
|
|
if root.is_null() {
|
|
return Node::new(val);
|
|
}
|
|
if val < (*root).val {
|
|
(*root).left = insert((*root).left, val);
|
|
} else if val > (*root).val {
|
|
(*root).right = insert((*root).right, val);
|
|
}
|
|
root
|
|
}
|
|
|
|
unsafe fn find_min(root: *mut Node) -> i32 {
|
|
let mut curr = root;
|
|
while !(*curr).left.is_null() {
|
|
curr = (*curr).left;
|
|
}
|
|
(*curr).val
|
|
}
|
|
|
|
unsafe fn delete(root: *mut Node, val: i32) -> *mut Node {
|
|
if root.is_null() { return ptr::null_mut(); }
|
|
|
|
if val < (*root).val {
|
|
(*root).left = delete((*root).left, val);
|
|
} else if val > (*root).val {
|
|
(*root).right = delete((*root).right, val);
|
|
} else {
|
|
if (*root).left.is_null() {
|
|
let temp = (*root).right;
|
|
dealloc(root as *mut u8, Layout::new::<Node>());
|
|
return temp;
|
|
} else if (*root).right.is_null() {
|
|
let temp = (*root).left;
|
|
dealloc(root as *mut u8, Layout::new::<Node>());
|
|
return temp;
|
|
} else {
|
|
let min_val = find_min((*root).right);
|
|
(*root).val = min_val;
|
|
(*root).right = delete((*root).right, min_val);
|
|
}
|
|
}
|
|
root
|
|
}
|
|
|
|
unsafe fn inorder(root: *mut Node, out: &mut String) {
|
|
if root.is_null() { return; }
|
|
inorder((*root).left, out);
|
|
out.push_str(&(*root).val.to_string());
|
|
out.push(' ');
|
|
inorder((*root).right, out);
|
|
}
|
|
|
|
unsafe fn preorder(root: *mut Node, out: &mut String) {
|
|
if root.is_null() { return; }
|
|
out.push_str(&(*root).val.to_string());
|
|
out.push(' ');
|
|
preorder((*root).left, out);
|
|
preorder((*root).right, out);
|
|
}
|
|
|
|
fn main() {
|
|
let stdin = io::stdin();
|
|
let mut reader = stdin.lock();
|
|
let mut line = String::new();
|
|
|
|
if reader.read_line(&mut line).is_err() { return; }
|
|
let n: i32 = line.trim().parse().unwrap_or(0);
|
|
|
|
let mut root: *mut Node = ptr::null_mut();
|
|
|
|
unsafe {
|
|
for _ in 0..n {
|
|
line.clear();
|
|
if reader.read_line(&mut line).unwrap_or(0) == 0 { break; }
|
|
let mut parts = line.split_whitespace();
|
|
let cmd = parts.next().unwrap_or("");
|
|
let val_str = parts.next().unwrap_or("");
|
|
if let Ok(val) = val_str.parse::<i32>() {
|
|
if cmd == "Insert" {
|
|
root = insert(root, val);
|
|
} else if cmd == "Remove" {
|
|
root = delete(root, val);
|
|
}
|
|
}
|
|
}
|
|
|
|
if !root.is_null() {
|
|
let mut out = String::with_capacity(1024 * 1024);
|
|
inorder(root, &mut out);
|
|
println!("{}", out.trim_end());
|
|
|
|
println!();
|
|
|
|
out.clear();
|
|
preorder(root, &mut out);
|
|
println!("{}", out.trim_end());
|
|
}
|
|
}
|
|
} |