数据结构-二叉树实验

发表于 更新于 从0开始的rust之旅

二叉树的建立与遍历

[问题描述]
建立一棵二叉树，并对其进行遍历(先序、中序、后序)，打印输出遍历结果。
[基本要求]
从键盘接受输入(先序)，以二叉链表作为存储结构，建立二叉树(以先序来建立)，并采用递归算法对其进行遍历(先序、中序、后序)，将遍历结果打印输出

第一轮，先定义数据结构与创建：

struct BinaryTree {
    data : Option<char>,
    left : Option<Box<BinaryTree>>,
    right : Option<Box<BinaryTree>>
}

impl BinaryTree {
    fn init() -> BinaryTree {
        BinaryTree{
            data : None,
            left : None,
            right : None
        }
    }

    fn create(&mut self, data: &mut &str) {
        let d = data.chars().nth(0).unwrap();
        *data = &data[1..];
        if d == ' ' {
            println!("return");
            return;
        }

        self.data = Some(d);
        println!("insert: {}",d);

        let mut left = Self::init();
        left.create(data);
        self.left = Some(Box::from(left));

        let mut right = Self::init();
        right.create(data);
        self.right = Some(Box::from(right));
    }
}

#[cfg(test)]
mod tests {
    use crate::BinaryTree;

    #[test]
    fn test_create() {
        let mut t = BinaryTree::init();
        let mut s = "ABC  DE G  F   ";
        t.create(&mut s);
    }
}

把data字段设计为可以为空了，实际上是不必要的，init函数也完全可以把data作为参数……不管了就这么设计了

传递data参数很有说法，最初想的是每次递归舍弃第一位，只传递剩余的切片，但是涉及右子树行不通，于是把data改为可变的，然后每次create都删去一位，类似于全局变量效果

运行测试看到输出：

running 1 test
insert: A
insert: B
insert: C
return
return
insert: D
insert: E
return
insert: G
return
return
insert: F
return
return
return
test tests::test_create ... ok

第二轮，递归完成遍历

fn pre_order_traverse(&self) {
    if self.data == None {
        return;
    }
    println!("{}",self.data.unwrap());
    if let Some(l) = &self.left {
        l.pre_order_traverse();
    }

    if let Some(r) = &self.right {
        r.pre_order_traverse();
    }
}

fn post_order_traverse(&self) {
    if self.data == None {
        return;
    }
    if let Some(l) = &self.left {
        l.post_order_traverse();
    }


    if let Some(r) = &self.right {
        r.post_order_traverse();
    }

    println!("{}",self.data.unwrap());
}

fn in_order_traverse(&self) {
    if self.data == None {
        return;
    }
    if let Some(l) = &self.left {
        l.in_order_traverse();
    }

    println!("{}",self.data.unwrap());

    if let Some(r) = &self.right {
        r.in_order_traverse();
    }
}

……
#[test]
fn test_trans(){
    let mut t = BinaryTree::init();
    let mut s = "ABC  DE G  F   ";
    t.create(&mut s);
    t.in_order_traverse();
    t.post_order_traverse();
    t.pre_order_traverse();
}

很常规的递归写法，由于self不需要可变，一切都很顺利，测试结果也符合预期

打印二叉树结构

按凹入表形式横向打印二叉树结构，即二叉树的根在屏幕的最左边，二叉树的左子树在屏幕的下边，二叉树的右子树在屏幕的上边。

[实现提示]
利用 RDL 遍历方法;(中序遍历右子树、根节点、中序遍历左子树 RDL)利用结点的深度控制横向位置。

要解决的问题是确定凹入表中每个节点的横纵坐标，根据提示，横向坐标用特定的遍历方式（右、中、左），每次打印一行确定，纵向坐标依据节点深度确定，那思路就很清晰了：

    fn print(&self, depth : usize) {
        if self.data == None {
            return;
        }

        if let Some(r) = &self.right {
            r.print(depth + 1);
        }

        let spaces = " ".repeat(depth * 2);
        println!("{}{}", spaces, self.data.unwrap());

        if let Some(l) = &self.left {
            l.print(depth + 1);
        }
    }

//测试

    #[test]
    fn test_print(){
        let mut t = BinaryTree::init();
        let mut s = "ABD  E  CF  G  ";
        t.create(&mut s);

        t.print(0);
    }

结果:

running 1 test
    G
  C
    F
A
    E
  B
    D
test tests::test_print ... ok

采用非递归算法实现二叉树的遍历

非递归，需要借助一点技巧，也就是栈。正常递归时会将下一个要执行的指令地址入栈，由于前序遍历先访问当前节点，所以可以模拟这个过程

fn pre_order(&self) {
    let mut stack : Vec<&BinaryTree> = Vec::new();

    if self.data == None {
        return;
    }

    stack.push(self);

    while let Some(node) = stack.pop() {
        if let Some(data) = node.data {
            println!("{}",data);
            if let Some(right) = &node.right {
                stack.push(right);
            }

            if let Some(left) = &node.left {
                stack.push(left);
            }
        }
    }
}

先把下一个要访问的节点入栈（右子树），再访问当前节点及（左子树）

后序遍历先访问的节点后输出，所以可以再用一个栈来模拟

fn post_order(&self) {
    let mut stack1 = Vec::new();
    let mut stack2 = Vec::new();

    stack1.push(self);

    while let Some(node) = stack1.pop() {
        stack2.push(node);

        if let Some(left) = &node.left {
            stack1.push(left);
        }
 
        if let Some(right) = &node.right {
            stack1.push(right);
        }
    }

    // stack2中的顺序就是后序遍历的逆序
    while let Some(node) = stack2.pop() {
        if let Some(data) = node.data {
            println!("{}",data);
        }
    }
}

优先输出的是左下方的，所以先访问右子树，左子树先入栈

中序遍历，左中右。沿着左子树走到叶节点，将过程中访问的节点入栈，然后访问该叶节点，往上追溯访问上一个节点，访问其右子树，如果遇到None则重新从栈pop

fn in_order(&self) {
    let mut stack = Vec::new();
    let mut current = Some(self);

    while current.is_some() || !stack.is_empty() {
        while let Some(node) = current {
            stack.push(node);
            current = node.left.as_ref().map(|n| &**n);
        }

        if let Some(node) = stack.pop() {
            if let Some(data) = node.data {
                println!("{}",data);
            }
            current = node.right.as_ref().map(|n| &**n);
        }
    }
}

测试：

#[test]
fn test_pre_order(){
    let mut t = BinaryTree::init();
    let mut s = "ABC  DE G  F   ";
    t.create(&mut s);
    //t.pre_order();
    //t.post_order();
    t.in_order();
}
# rust