rotate_tree.rs

#[deriving(Show)]
struct Node {
    value: uint,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

impl Node {
    fn new(val: uint) -> Box<Node> {
        box Node {
            value: val,
            left: None,
            right: None,
        }
    }
}

trait BoxNode {
    fn add_left(&mut self, newleft: Box<Node>) -> Option<Box<Node>>;
    fn add_right(&mut self, newright: Box<Node>) -> Option<Box<Node>>;
}

impl BoxNode for Box<Node> {
    fn add_left(&mut self, newleft: Box<Node>) -> Option<Box<Node>> {
        let oldleft = self.left.take();
        self.left = Some(newleft);
        oldleft
    }
    
    fn add_right(&mut self, newright: Box<Node>) -> Option<Box<Node>> {
        let oldright = self.right.take();
        self.right = Some(newright);
        oldright
    }
    
}

// thanks to eddyb, we have rotation
fn rotate_right(mut root: Box<Node>) -> Box<Node> {
    let mut left = root.left.take().unwrap();
    root.left = left.right.take();
    left.right = Some(root);
    left
}

fn main() {
    let mut root = Node::new(0);
    let mut left = Node::new(1);
    left.add_left(Node::new(3));
    left.add_right(Node::new(4));
    root.add_right(Node::new(2));
    root.add_left(left);
    println!("{}", root)
    let root = rotate_right(root);
    println!("{}", root);
}