Rust中二叉树的广度优先遍历

vlurs2pr 于 2023-01-13 发布在其他

关注(0)|答案(1)|浏览(162)

我刚接触Rust，但从C++开始，我发现类型系统的体操有点麻烦。我用LeetCode中的问题自学Rust。以下面的二叉树定义为例：

pub struct TreeNode {
  pub val: i32,
  pub left: Option<Rc<RefCell<TreeNode>>>,
  pub right: Option<Rc<RefCell<TreeNode>>>,
}

好吧，这已经有点难看了，但我有点理解其中的原因（尽管我不清楚为什么我们不能有一个单一的类型来组合Option、Rc和RefCell的功能，当这些功能似乎经常一起出现时）。
总之，下面是我实现的BFS算法（它没有做任何有趣的事情，重点是总体布局）：

use std::collections::VecDeque;

fn bfs(root: Option<Rc<RefCell<TreeNode>>>) {
    let mut queue = VecDeque::new();
    queue.push_back((root, 0));
    while queue.len() > 0 {
        // 'pos' measures how far out to the left or right the given node is.
        let (node, pos) = queue.pop_front().unwrap();
        if node.is_none() { continue; }
        let subtree = node.unwrap();
        queue.push_back((subtree.borrow().left.clone(), pos - 1));
        queue.push_back((subtree.borrow().right.clone(), pos + 1));
    }
}

我的问题是：这真的是《铁 rust 》里的做法吗？难道没有更特别的（更简洁）的方式？我的意思是，代码使用unwrap()、borrow()和clone()中的一个来获取左右树指针。至少可以说，这感觉有点麻烦。这可能是Rust中的一般做法，但我很好奇这是正常现象还是例外

rust

来源：https://stackoverflow.com/questions/73553178/breadth-first-traversal-of-binary-tree-in-rust

1条答案

按热度按时间

aiazj4mn1#

这里的unwrap()确实是非惯用的，可以替换，第一个unwrap()可以替换为while let，第二个可以替换为if let：

while let Some((node, pos)) = queue.pop_front() {
    // 'pos' measures how far out to the left or right the given node is.
    if let Some(subtree) = node {
        queue.push_back((subtree.borrow().left.clone(), pos - 1));
        queue.push_back((subtree.borrow().right.clone(), pos + 1));
    }
}

不得不用if let Package 整个循环体是很不幸的，实验特性let_else将解决这个问题（在Rust 1.65.0中稳定）：

#![feature(let_else)]

while let Some((node, pos)) = queue.pop_front() {
    // 'pos' measures how far out to the left or right the given node is.
    let Some(subtree) = node else {
        continue;
    };
    
    queue.push_back((subtree.borrow().left.clone(), pos - 1));
    queue.push_back((subtree.borrow().right.clone(), pos + 1));
}

但是borrow()和clone()是因为您试图绕过Rc<RefCell>的所有权规则。如果你认为你需要使用它，再想想。2可能有更多的Rusty做事方式。3有时它很简单，有时需要重新设计你的数据结构（例如，用Rust中通常用索引表示的图表）。
更简单的树也将具有更简单的搜索函数：

pub struct TreeNode {
    pub val: i32,
    pub left: Option<Box<TreeNode>>,
    pub right: Option<Box<TreeNode>>,
}

fn bfs(root: Option<&TreeNode>) {
    let mut queue = VecDeque::new();
    queue.push_back((root, 0));
    while let Some((node, pos)) = queue.pop_front() {
        // 'pos' measures how far out to the left or right the given node is.
        let Some(subtree) = node else {
            continue;
        };
        
        queue.push_back((subtree.left.as_deref(), pos - 1));
        queue.push_back((subtree.right.as_deref(), pos + 1));
    }
}

赞(0）回复(0）举报 2023-01-13

我来回答

Rust中二叉树的广度优先遍历

1条答案

相关问题

热门标签

最新问答