rust - Rust 二叉树实现的困难

Question

我正在尝试在 Rust 中实现一个简单的二叉搜索树，但我很难确定插入节点的问题。我正在使用以下数据结构和函数。

enum BinaryTree<T> {
    Leaf(T),
    Branch(T, Box<BinaryTree<T>>, Box<BinaryTree<T>>),
    Null,
}

fn createBinarySearchTree(vector: Vec<int>) -> BinaryTree<int> {        
    fn insertNode(val: int, btree: &BinaryTree<int>) -> BinaryTree<int> {
        match btree {
            &Leaf(tval) if val > tval => Branch(tval, box Null, box Leaf(val)),     
            &Leaf(tval) if val < tval => Branch(tval, box Leaf(val), box Null),
            &Branch(tval, box ref left, box ref right) if val > tval => insertNode(val,right),
            &Branch(tval, box ref left, box ref right) if val < tval => insertNode(val,left),
            &Null => Leaf(val),
            &Leaf(lval) if val == lval => Leaf(val),
            &Branch(lval, box ref left, box ref right) if val == lval => fail!("already has a node with {}", lval),
            _ => Null,
        }
    }

    let mut tree = Null;
    for v in vector.iter() {
        tree = insertNode(*v, &tree);
    }

    let immuTree = tree;
    immuTree
}

fn printTree(tree: &BinaryTree<int>) {
    fn innerPrint(prefix: &str, tree: &BinaryTree<int>, level: int) {
        let lvDesc = format!("lv {}", level);
        match tree {
            &Leaf(val) => println!("{}-{} leaf: {}", lvDesc, prefix, val),
            &Branch(val, box ref left, box ref right) => {
                println!("{}-{} node: {}", lvDesc, prefix, val);
                innerPrint("left branch <-", left, level + 1);
                innerPrint("right branch ->", right, level + 1);
            },
            &Null => println!("end"),
        }
    }
    innerPrint("root", tree, 0);
}

调用 printTree(&createBinarySearchTree(vec![43,2,45,7,72,28,34,33])) 树只打印出 33,34 不幸的是我无法调试，因为使用调试信息进行编译会导致编译器错误。当我在插入时匹配分支时，我也尝试返回一个分支，但这需要我以我还无法理解的方式克隆叶子/赋予所有权。所以任何帮助将不胜感激

干杯

Answer 1

我认为这些分支有过错:

&Branch(tval, box ref left, box ref right) if val > tval => insertNode(val, right),
&Branch(tval, box ref left, box ref right) if val < tval => insertNode(val, left),

由于您正在改变原始树，因此每个分支都会失去原始树根。假设修复(未经测试):

&Branch(tval, box ref left, box ref right) if val > tval => Branch(tval, left, insertNode(val, right)),
&Branch(tval, box ref left, box ref right) if val < tval => Branch(tval, insertNode(val, left), right),

编辑

嗯，这个想法是对的，但你是对的，Rust 提示从模式守卫后面的 & 指针移出，所以我不得不在里面再做一次匹配(结果更好)。我也不能忽略命名，所以我按照 Rust 编码风格清理了它:

use std::fmt::Show;

enum BinaryTree<T> {
    Leaf(T),
    Branch(T, Box<BinaryTree<T>>, Box<BinaryTree<T>>),
    Null,
}

fn create_binary_search_tree(vector: Vec<int>) -> BinaryTree<int> {
    fn insert_node<T: Copy + Ord + Show>(val: T, btree: BinaryTree<T>) -> BinaryTree<T> {
        match btree {
            Leaf(tval) if val > tval => Branch(tval, box Null, box Leaf(val)),   
            Leaf(tval) if val < tval => Branch(tval, box Leaf(val), box Null),
            Branch(tval, left, right) => match val.cmp(&tval) {
                Greater => Branch(tval, left, box insert_node(val, *right)),
                Less    => Branch(tval, box insert_node(val, *left), right),
                Equal   => fail!("already has a node with {}", tval),
            },
            Null => Leaf(val),
            Leaf(lval) if val == lval => Leaf(val),
            _ => Null,
        }
    }

    let mut tree = Null;
    for v in vector.iter() {
        tree = insert_node(*v, tree);
    }

    let immuTree = tree;
    immuTree
}


fn print_tree(tree: &BinaryTree<int>) {
    fn inner_print(prefix: &str, tree: &BinaryTree<int>, level: int) {
        let lvDesc = format!("lv {}", level);
        match tree {
            &Leaf(val) => println!("{}-{} leaf: {}", lvDesc, prefix, val),
            &Branch(val, box ref left, box ref right) => {
                println!("{}-{} node: {}", lvDesc, prefix, val);
                inner_print("left branch <-", left, level + 1);
                inner_print("right branch ->", right, level + 1);
            },
            &Null => println!("end"),
        }
    }
    inner_print("root", tree, 0);
}

fn main() {
    print_tree(&create_binary_search_tree(vec![43, 2, 45, 7, 72, 28, 34, 33]));
}

我验证了这段代码可以在“http://play.rust-lang.org/”中工作