< 返回版块

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

Joey 发表于

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)的

评论区

Pslydhh 2018-08-26T18:25:33.737304

你的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()语义还是有点问题的...

Pslydhh 2018-08-26T18:28:14.052976

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

作者 Joey 2018-08-27T03:39:39.960954

感谢,确实是这样的,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>>;, 不过你懂意思就行...

Krys 2018-08-31T02:49:16.163807

我觉得应该不要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>>;, 不过你懂意思就行...

Krys 2018-08-31T02:50:56.358170

想简化代码的话,首先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-31T05:29:11.353769

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); }

作者 Joey 2018-08-31T11:19:10.871995

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

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); }

作者 Joey 2018-08-31T13:24:47.117995

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

Krys 2018-09-01T09:27:50.809697

对于爆栈问题我是这样看的,如果不是平衡树的话估计就需要堆内存分配来解决这个问题,但是申请堆内存又有失败的情况。所以真要想弄一个比较好的二叉树实现应该需要去平衡才行。当然,我回的那个代码的重点是如何写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); }

1 共 9 评论, 共 1 页