求教我这个rust实现的二叉树哪里出错了

Joey 发表于 2018-08-27 01:25

use std::cmp::PartialOrd;
use std::fmt::Debug;

struct Node<T: PartialOrd + Debug> {
    elem: T,
    left: Link<T>,
    right: Link<T>,
}

type Link<T> = Option<Box<Node<T>>>;

pub struct Tree<T: PartialOrd + Debug> {
    root: Link<T>,
}

impl<T: PartialOrd + Debug> Node<T> {
    pub fn new(t: T) -> Self {
        Node {
            elem: t,
            left: None,
            right: None,
        }
    }

    pub fn insert(&mut self, t: T) {
        if self.elem > t {
            // 往左插入
            match self.left.take() {
                None => {
                    // 左子树为空，直接设置左子树
                    self.left = Some(Box::new(Node::new(t)));
                }
                Some(mut node) => {
                    (*node).insert(t);
                }
            }
        } else {
            match self.right.take() {
                None => {
                    self.right = Some(Box::new(Node::new(t)));
                }
                Some(mut node) => {
                    (*node).insert(t);
                }
            }
        }
    }
}

impl<T: PartialOrd + Debug + Copy> Tree<T> {
    pub fn new() -> Self {
        Tree { root: None }
    }

    pub fn insert(&mut self, t: T) {
        // 查找到合适的位置插入t
        match self.root.take() {
            None => {
                let root_node = Box::new(Node::new(t));
                self.root = Some(root_node);
                println!("insert into root {:?}", t);
            }
            Some(node) => {
                let mut node = *node;
                &node.insert(t);
                println!("cur node {:?}, insert elem {:?}", node.elem, t.clone());
            }
        }
    }

    pub fn peek(&self) -> Option<&T> {
        // self.root.as_ref().map(|node| &node.elem)
        match self.root.as_ref().take() {
            None => None,
            Some(t) => {
                // (*t.right.clone()).as_ref().map(|node| &node.elem)
                t.right.as_ref().map(|node| &node.elem)
            }
        }
    }
}

fn main() {
    let mut t = Tree::new();
    t.insert(1);
    t.insert(2);
    let root_elem = t.peek();
    println!("root_elem {:?}", root_elem);
}

在学习使用rust实现基本的数据结构，但是写到这里就卡住了，我想打印树的根节点元素，但是一直显示是None，预期应该是Some(&1)的

评论区

写评论

Krys 2018-09-01 17:27

对于爆栈问题我是这样看的，如果不是平衡树的话估计就需要堆内存分配来解决这个问题，但是申请堆内存又有失败的情况。所以真要想弄一个比较好的二叉树实现应该需要去平衡才行。当然，我回的那个代码的重点是如何写insert写得优雅又不出错。

@Joey 我们的写法差不多，不过我发现一个问题，我们都是递归实现的，在递归次数较多的时候会爆栈，用你的代码： fn main() { let mut t = Tree::new(); for i in 1..100000 { t.insert(i); } }

thread 'main' has overflowed its stack fatal runtime error: stack overflow

@Krys PS: 后来我又想了一下，改了改，发现代码量其实可以继续减少,当然，我把peek给去掉了，想加可以加上。 #![feature(nll)] use std::cmp::PartialOrd; use std::fmt::Debug; struct Node<T: PartialOrd + Debug> { elem: T, left: Tree, right: Tree, } struct Tree<T: PartialOrd + Debug> { data: Option<Box>, } impl<T: PartialOrd + Debug> Tree { fn insert(&mut self, data: T) { match self.data { Some(ref mut node) => if node.elem > data { node.left.insert(data) } else { node.right.insert(data) }, None => self.data = Some(Box::new(Node::new(data))), } } fn new() -> Tree { Tree { data: None } }

} impl<T: PartialOrd + Debug> Node { pub fn new(t: T) -> Self { Node { elem: t, left: Tree::new(), right: Tree::new(), } } } fn main() { let mut t = Tree::new(); t.insert(1); t.insert(2); }

@Krys 想简化代码的话，首先NLL给的帮助会很大，第二就是插入应该对准link，对准node会写一堆的match。 #![feature(nll)] use std::cmp::PartialOrd; use std::fmt::Debug; struct Node<T: PartialOrd + Debug> { elem: T, left: Link, right: Link, } type Link = Option; pub struct Tree<T: PartialOrd + Debug> { root: Link, } fn insert_link<T: PartialOrd + Debug> (link: &mut Link, data: T) { match link { Some(ref mut node) => if node.elem > data { insert_link(&mut node.left, data) } else { insert_link(&mut node.right, data) }, None => *link = Some(Box::new(Node::new(data))) } } impl<T: PartialOrd + Debug> Node { pub fn new(t: T) -> Self { Node { elem: t, left: None, right: None, } } } impl<T: PartialOrd + Debug + Copy> Tree { pub fn new() -> Self { Tree { root: None } } pub fn insert(&mut self, data: T) { insert_link(&mut self.root, data) } pub fn peek(&self) -> Option<&T> { // self.root.as_ref().map(|node| &node.elem) match self.root.as_ref() { None => None, Some(t) => { // (*t.right.clone()).as_ref().map(|node| &node.elem) t.right.as_ref().map(|node| &node.elem) } } } } fn main() { let mut t = Tree::new(); t.insert(1); t.insert(2); let root_elem = t.peek(); println!("root_elem {:?}", root_elem); }

作者 Joey 2018-08-31 21:24

@Krys 又看了一下，还是有点差别的，你的left和right都是struct，我的left, right是一个指针

作者 Joey 2018-08-31 19:19

我们的写法差不多，不过我发现一个问题，我们都是递归实现的，在递归次数较多的时候会爆栈，用你的代码：

fn main() {
    let mut t = Tree::new();
    for i in 1..100000 {
        t.insert(i);
    }
}

thread 'main' has overflowed its stack fatal runtime error: stack overflow

@Krys PS: 后来我又想了一下，改了改，发现代码量其实可以继续减少,当然，我把peek给去掉了，想加可以加上。 #![feature(nll)] use std::cmp::PartialOrd; use std::fmt::Debug;

struct Node<T: PartialOrd + Debug> { elem: T, left: Tree, right: Tree, }

struct Tree<T: PartialOrd + Debug> { data: Option<Box<Node>>, }

impl<T: PartialOrd + Debug> Tree { fn insert(&mut self, data: T) { match self.data { Some(ref mut node) => if node.elem > data { node.left.insert(data) } else { node.right.insert(data) }, None => self.data = Some(Box::new(Node::new(data))), } }
fn new() -> Tree<T> {
    Tree { data: None }
}
}

impl<T: PartialOrd + Debug> Node { pub fn new(t: T) -> Self { Node { elem: t, left: Tree::new(), right: Tree::new(), } } }

fn main() { let mut t = Tree::new(); t.insert(1); t.insert(2); }

@Krys 想简化代码的话，首先NLL给的帮助会很大，第二就是插入应该对准link，对准node会写一堆的match。 #![feature(nll)] use std::cmp::PartialOrd; use std::fmt::Debug; struct Node<T: PartialOrd + Debug> { elem: T, left: Link, right: Link, } type Link = Option<Box>; pub struct Tree<T: PartialOrd + Debug> { root: Link, } fn insert_link<T: PartialOrd + Debug> (link: &mut Link, data: T) { match link { Some(ref mut node) => if node.elem > data { insert_link(&mut node.left, data) } else { insert_link(&mut node.right, data) }, None => *link = Some(Box::new(Node::new(data))) } } impl<T: PartialOrd + Debug> Node { pub fn new(t: T) -> Self { Node { elem: t, left: None, right: None, } } } impl<T: PartialOrd + Debug + Copy> Tree { pub fn new() -> Self { Tree { root: None } } pub fn insert(&mut self, data: T) { insert_link(&mut self.root, data) }

pub fn peek(&self) -> Option<&T> { // self.root.as_ref().map(|node| &node.elem) match self.root.as_ref() { None => None, Some(t) => { // (*t.right.clone()).as_ref().map(|node| &node.elem) t.right.as_ref().map(|node| &node.elem) } } }

} fn main() { let mut t = Tree::new(); t.insert(1); t.insert(2); let root_elem = t.peek(); println!("root_elem {:?}", root_elem); }

Krys 2018-08-31 13:29

PS: 后来我又想了一下，改了改，发现代码量其实可以继续减少,当然，我把peek给去掉了，想加可以加上。

#![feature(nll)]
use std::cmp::PartialOrd;
use std::fmt::Debug;

struct Node<T: PartialOrd + Debug> {
    elem: T,
    left: Tree<T>,
    right: Tree<T>,
}

struct Tree<T: PartialOrd + Debug> {
    data: Option<Box<Node<T>>>,
}

impl<T: PartialOrd + Debug> Tree<T> {
    fn insert(&mut self, data: T) {
        match self.data {
            Some(ref mut node) => if node.elem > data {
                node.left.insert(data)
            } else {
                node.right.insert(data)
            },
            None => self.data = Some(Box::new(Node::new(data))),
        }
    }

    fn new() -> Tree<T> {
        Tree { data: None }
    }
}

impl<T: PartialOrd + Debug> Node<T> {
    pub fn new(t: T) -> Self {
        Node {
            elem: t,
            left: Tree::new(),
            right: Tree::new(),
        }
    }
}

fn main() {
    let mut t = Tree::new();
    t.insert(1);
    t.insert(2);
}

@Krys 想简化代码的话，首先NLL给的帮助会很大，第二就是插入应该对准link，对准node会写一堆的match。 #![feature(nll)] use std::cmp::PartialOrd; use std::fmt::Debug;

struct Node<T: PartialOrd + Debug> { elem: T, left: Link, right: Link, }

type Link = Option<Box<Node>>;

pub struct Tree<T: PartialOrd + Debug> { root: Link, }

fn insert_link<T: PartialOrd + Debug> (link: &mut Link, data: T) { match link { Some(ref mut node) => if node.elem > data { insert_link(&mut node.left, data) } else { insert_link(&mut node.right, data) }, None => *link = Some(Box::new(Node::new(data))) } }

impl<T: PartialOrd + Debug> Node { pub fn new(t: T) -> Self { Node { elem: t, left: None, right: None, } } }

impl<T: PartialOrd + Debug + Copy> Tree { pub fn new() -> Self { Tree { root: None } }
pub fn insert(&mut self, data: T) {
    insert_link(&mut self.root, data)
}

pub fn peek(&self) -> Option<&T> {
    // self.root.as_ref().map(|node| &node.elem)
    match self.root.as_ref() {
        None => None,
        Some(t) => {
            // (*t.right.clone()).as_ref().map(|node| &node.elem)
            t.right.as_ref().map(|node| &node.elem)
        }
    }
}
}

fn main() { let mut t = Tree::new(); t.insert(1); t.insert(2); let root_elem = t.peek(); println!("root_elem {:?}", root_elem); }

Krys 2018-08-31 10:50

想简化代码的话，首先NLL给的帮助会很大，第二就是插入应该对准link，对准node会写一堆的match。

#![feature(nll)]
use std::cmp::PartialOrd;
use std::fmt::Debug;

struct Node<T: PartialOrd + Debug> {
    elem: T,
    left: Link<T>,
    right: Link<T>,
}

type Link<T> = Option<Box<Node<T>>>;

pub struct Tree<T: PartialOrd + Debug> {
    root: Link<T>,
}

fn insert_link<T: PartialOrd + Debug> (link: &mut Link<T>, data: T) {
    match link {
        Some(ref mut node) => 
        if node.elem > data {
            insert_link(&mut node.left, data)
        }
        else {
            insert_link(&mut node.right, data)
        },
        None =>  *link =  Some(Box::new(Node::new(data)))
    }
}

impl<T: PartialOrd + Debug> Node<T> {
    pub fn new(t: T) -> Self {
        Node {
            elem: t,
            left: None,
            right: None,
        }
    }
}

impl<T: PartialOrd + Debug + Copy> Tree<T> {
    pub fn new() -> Self {
        Tree { root: None }
    }

    pub fn insert(&mut self, data: T) {
        insert_link(&mut self.root, data)
    }

    pub fn peek(&self) -> Option<&T> {
        // self.root.as_ref().map(|node| &node.elem)
        match self.root.as_ref() {
            None => None,
            Some(t) => {
                // (*t.right.clone()).as_ref().map(|node| &node.elem)
                t.right.as_ref().map(|node| &node.elem)
            }
        }
    }
}

fn main() {
    let mut t = Tree::new();
    t.insert(1);
    t.insert(2);
    let root_elem = t.peek();
    println!("root_elem {:?}", root_elem);
}

Krys 2018-08-31 10:49

我觉得应该不要take，直接在引用上match，然后直接改，既然NLL已经出来了，就用NLL好了

@Joey 感谢，确实是这样的，take之后原root节点就变为None了，调用Node里面的insert方法生成新的树之后需要再赋值回去给self.root，要对抗rust的编译器真费劲，写个简单的树都这么麻烦 https://github.com/xcaptain/rust-algorithms/blob/master/data-structures/src/tree/binary_tree.rs

@Pslydhh 诶，我发出来的代码好像断了type Link = Option>>;，不过你懂意思就行...

作者 Joey 2018-08-27 11:39

感谢，确实是这样的，take之后原root节点就变为None了，调用Node里面的insert方法生成新的树之后需要再赋值回去给self.root，要对抗rust的编译器真费劲，写个简单的树都这么麻烦

https://github.com/xcaptain/rust-algorithms/blob/master/data-structures/src/tree/binary_tree.rs

@Pslydhh 诶，我发出来的代码好像断了type Link = Option>>;，不过你懂意思就行...

Pslydhh 2018-08-27 02:28

诶，我发出来的代码好像断了type Link = Option>>;，不过你懂意思就行...

Pslydhh 2018-08-27 02:25

你的Node跟Tree里的insert方法，调用的是take()，而take会直接消耗掉这个Option，也就是说take()之后self.left,self.right,self.root都变为了None,你需要在 Some(mut node) => 的时候把这三个重新设置回来，给出我的能执行版本：


use std::cmp::PartialOrd;
use std::fmt::Debug;

struct Node {
    elem: T,
    left: Link,
    right: Link,
}

type Link = Option>>;

pub struct Tree {
    root: Link,
}

impl Node {
    pub fn new(t: T) -> Self {
        Node {
            elem: t,
            left: None,
            right: None,
        }
    }

    pub fn insert(&mut self, t: T) {
        if self.elem > t {
            // 往左插入
            match self.left.take() {
                None => {
                    // 左子树为空，直接设置左子树
                    self.left = Some(Box::new(Node::new(t)));
                }
                Some(mut node) => {
                    (*node).insert(t);
					self.left = Some(node);
                }
            }
        } else {
            match self.right.take() {
                None => {
                    self.right = Some(Box::new(Node::new(t)));
                }
                Some(mut node) => {
                    (*node).insert(t);
					self.right = Some(node);
                }
            }
        }
    }
}

impl Tree {
    pub fn new() -> Self {
        Tree { root: None }
    }

    pub fn insert(&mut self, t: T) {
        // 查找到合适的位置插入t
        match self.root.take() {
            None => {
                let root_node = Box::new(Node::new(t));
                self.root = Some(root_node);
                println!("insert into root {:?}", t);
            }
            Some(node) => {
                let mut node = *node;
                &node.insert(t);
                println!("cur node {:?}, insert elem {:?}", node.elem, t.clone());
                self.root = Some(Box::new(node));
            }
        }
    }

    pub fn peek(&self) -> Option<&T> {
        // self.root.as_ref().map(|node| &node.elem)
        match self.root.as_ref().take() {
            None => None,
            Some(t) => {
                // (*t.right.clone()).as_ref().map(|node| &node.elem)
                t.right.as_ref().map(|node| &node.elem)
            }
        }
    }
}

fn main() {
    let mut t = Tree::new();
    t.insert(1);
    t.insert(2);
    let root_elem = t.peek();
    println!("root_elem {:?}", root_elem);
}

不过我认为你的peek()语义还是有点问题的...

1 共 9 条评论, 1 页