< 返回版块

二叉树 非递归 插入 遇到所有权的问题

Military-axe 发表于 2021-06-18 18:17

Tags：二叉树,非递归,所有权

我是一个新手，我想写一个二叉树。定义的结构体如下

use std::{cell::RefCell, rc::Rc};

type Tree<K> = Option<Rc<RefCell<Node<K>>>>;
#[derive(Debug)]
struct Node<K: Copy+PartialOrd>{
    l: Tree<K>,
    r: Tree<K>,
    v: K,
}

因为要有一个指针指向各个节点来对比，还要有一个头节点。出现了两个指针指向同一个，所以要Rc。又Rc内部不可以变，我却需要改变数值，所以在Rc中包裹RefCell.

问题出现在我写插入函数上，根节点是root，我定义一个指针ptr指向根节点，随着对比数值大小，开始走向左子树，右子树，本来应该ptr指向下一个节点，但是ptr却出现了无法赋值的现象，请大佬们帮帮忙🥺

impl <K: Copy+PartialOrd+Eq>Node<K> {
    pub fn new(val: K) -> Self{
        Node{
            l: None,
            r: None,
            v: val,
        }
    }

    fn insert(root: Tree<K>,val: K) -> Tree<K>{
        if let Some(mut _root) = root{
            let mut ptr = _root.clone();
            loop{
                if ptr.borrow().v < val {
                    // 右子树
                    if let Some(right) = &ptr.borrow().r{
                        ptr = right.clone(); // 报错 cannot assign to `ptr` because it is borrowed
                    }else{
                        ptr.borrow_mut().r = Some(Rc::new(RefCell::new(Node::new(val))));
                        return Some(_root);
                    }
                }else {
                    // 左子树
                    // to do 
                }
            }
        }else {
            return Some(Rc::new(RefCell::new(Node::new(val))));
        }
    }
}

评论区

写评论
jamesmarva 2021-06-25 01:47

用一个临时的变量可以解决这个问题，希望下面的代码可以给你提供参考：

pub fn insert_into_bst(mut root: Option<Rc<RefCell<TreeNode>>>, val: i32) -> Option<Rc<RefCell<TreeNode>>> {
    if root.is_none() {
        return Some(Rc::new(RefCell::new(TreeNode::new(val))));
    }
    let mut curr = Rc::clone(root.as_ref().unwrap());
    loop {
        let tmp_curr;
        if curr.borrow().val > val {
            let lt = &mut (curr.borrow_mut().left);
            if lt.is_none() {
                *lt = Some(Rc::new(RefCell::new(TreeNode::new(val))));
                break;
            } 
            tmp_curr = Rc::clone(lt.as_ref().unwrap())
        } else {
            let rt = &mut curr.borrow_mut().right;
            if rt.is_none() {
                *rt = Some(Rc::new(RefCell::new(TreeNode::new(val))));
                break;
            }
            tmp_curr = Rc::clone(rt.as_ref().unwrap());
        }
        curr = tmp_curr;
    }
    root
}

经过简化可以变成下面的代码：

pub fn insert_into_bst(mut root: Option<Rc<RefCell<TreeNode>>>, val: i32) -> Option<Rc<RefCell<TreeNode>>> {
    if root.is_none() {
        return Some(Rc::new(RefCell::new(TreeNode::new(val))));
    }
    let mut curr = Rc::clone(root.as_ref().unwrap());
    loop {
        curr = if curr.borrow().val > val {
            let lt = &mut (curr.borrow_mut().left);
            if lt.is_none() {
                *lt = Some(Rc::new(RefCell::new(TreeNode::new(val))));
                break;
            } 
            Rc::clone(lt.as_ref().unwrap())
        } else {
            let rt = &mut curr.borrow_mut().right;
            if rt.is_none() {
                *rt = Some(Rc::new(RefCell::new(TreeNode::new(val))));
                break;
            }
            Rc::clone(rt.as_ref().unwrap())
        };
    }
    root
}
作者 Military-axe 2021-06-20 10:42

确实是现成的二叉树库在rust里面的，我最近是在看一些基础的东西想用rust实现，顺便熟悉一下rust。总之谢谢师傅提供的这个信息

--
👇
chenge: 这里有一个算法库，好像写法看上去要好很多。

https://github.com/TheAlgorithms/Rust

use std::cmp::Ordering;
use std::ops::Deref;

/// This struct implements as Binary Search Tree (BST), which is a
/// simple data structure for storing sorted data
pub struct BinarySearchTree<T>
where
    T: Ord,
{
    value: Option<T>,
    left: Option<Box<BinarySearchTree<T>>>,
    right: Option<Box<BinarySearchTree<T>>>,
}
作者 Military-axe 2021-06-20 10:39

box是把数据放堆上，不允许有两个指针指向他，用Rc就可以有两个指针执行同一个内存地址了。但是Rc要求同时包装后的数据内部是不可以变动的，为了防止内存泄漏，这就要再Rc里面包装一个RefCell。RefCell可以使得Rc内部可变

--
👇
munpf: 我记得树这种只有一个父节点的数据结构，用Box就可以了吧，这里面有说明：https://rustcc.cn/article?id=2402b3fe-0180-4126-a8e3-90cfd837c476，用Rc和RefCell有其他好处吗？

munpf 2021-06-18 23:22

我记得树这种只有一个父节点的数据结构，用Box就可以了吧，这里面有说明：https://rustcc.cn/article?id=2402b3fe-0180-4126-a8e3-90cfd837c476，用Rc和RefCell有其他好处吗？

chenge 2021-06-18 20:30

这里有一个算法库，好像写法看上去要好很多。

https://github.com/TheAlgorithms/Rust

use std::cmp::Ordering;
use std::ops::Deref;

/// This struct implements as Binary Search Tree (BST), which is a
/// simple data structure for storing sorted data
pub struct BinarySearchTree<T>
where
    T: Ord,
{
    value: Option<T>,
    left: Option<Box<BinarySearchTree<T>>>,
    right: Option<Box<BinarySearchTree<T>>>,
}
chenge 2021-06-18 20:20

这个写法也太难看了吧，严重打击学习的信心。

作者 Military-axe 2021-06-18 20:00

谢谢师傅，牛啊牛啊

--
👇
ywxt: ``` // 右子树 let right = ptr.borrow().r.clone(); if let Some(right) = right { ptr = right; } else { ptr.borrow_mut().r = Some(Rc::new(RefCell::new(Node::new(val)))); return Some(_root); }

ywxt 2021-06-18 19:45 
// 右子树
let right = ptr.borrow().r.clone();
if let Some(right) = right {
    ptr = right; 
} else {
    ptr.borrow_mut().r = Some(Rc::new(RefCell::new(Node::new(val))));
    return Some(_root);
}
1 共 8 条评论, 1 页