Rust 二叉树前中后序遍历通用代码！！你知道是什么吗？？？

最新推荐文章于 2024-04-27 19:43:42 发布

「已注销」

最新推荐文章于 2024-04-27 19:43:42 发布

阅读量358

点赞数

分类专栏： Java 文章标签：二叉树 java 编程语言编译器 jvm

本文链接：https://blog.csdn.net/shayukaifa/article/details/117266575

版权

Java 专栏收录该内容

106 篇文章

订阅专栏

本文介绍了如何使用 Rust 实现二叉树的前序、中序和后序遍历，并利用 Iterator 特性进行转换，强调了 Iterator 的惰性求值和堆内存消耗特点。提供了一个名为 TreeNodeIterator 的实现。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

把文章下方的代码直接放到题解中，然后就可以方便地把 root: Option<Rc<RefCell>> 转换成 Iterator { Item = Rc<RefCell>; }，然后通过 Iterator 的 map 和 collect 功能转换成 Vec。

Iterator 是惰性求值的。

Iterator 采用 DFS，迭代过程中会生成额外的迭代器，有 O(h) 的堆内存消耗。

使用方法

1. 二叉树的前序遍历

impl Solution {
    pub fn preorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let iter = TreeNodeIterator::new(TreeNodeIteratorOrder::PreOrder, root);
        iter.map(|node| node.borrow().val).collect()
    }
}

2. 二叉树的中序遍历

impl Solution {
    pub fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let iter = TreeNodeIterator::new(TreeNodeIteratorOrder::InOrder, root);
        iter.map(|node| node.borrow().val).collect()
    }
}

3. 二叉树的后序遍历

impl Solution {
    pub fn postorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let iter = TreeNodeIterator::new(TreeNodeIteratorOrder::PostOrder, root);
        iter.map(|node| node.borrow().val).collect()
    }
}

TreeNodeIterator

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }

#[derive(Copy, Clone)]
enum TreeNodeIteratorOrder {
    PreOrder,
    InOrder,
    PostOrder,
}

#[derive(Clone)]
enum TreeNodeIteratorState {
    New,
    Left(Rc<RefCell<TreeNodeIterator>>),
    Val,
    Right(Rc<RefCell<TreeNodeIterator>>),
    Finished,
}

struct TreeNodeIterator {
    order: TreeNodeIteratorOrder,
    root: Option<Rc<RefCell<TreeNode>>>,
    state: TreeNodeIteratorState,
}
//加入Java开发交流君样：756584822一起吹水聊天
impl TreeNodeIterator {
    pub fn new(order: TreeNodeIteratorOrder, root: Option<Rc<RefCell<TreeNode>>>) -> Self {
        TreeNodeIterator {
            order,
            root,
            state: TreeNodeIteratorState::New,
        }
    }
}

impl Iterator for TreeNodeIterator {
    type Item = Rc<RefCell<TreeNode>>;

    fn next(&mut self) -> Option<Self::Item> {
        match self.state.clone() {
            TreeNodeIteratorState::New => {
                if self.root.is_some() {
                    match self.order {
                        TreeNodeIteratorOrder::PreOrder => {
                            self.state = TreeNodeIteratorState::Val;
                        }//加入Java开发交流君样：756584822一起吹水聊天
                        TreeNodeIteratorOrder::InOrder | TreeNodeIteratorOrder::PostOrder => {
                            self.state = TreeNodeIteratorState::Left(Rc::new(RefCell::new(TreeNodeIterator::new(self.order, self.root.as_ref().unwrap().borrow().left.clone()))));
                        }
                    }
                } else {
                    self.state = TreeNodeIteratorState::Finished;
                }
                self.next()
            }
            TreeNodeIteratorState::Left(iter) => {
                if let Some(item) = iter.borrow_mut().next() {
                    Some(item)
                } else {
                    match self.order {
                        TreeNodeIteratorOrder::PreOrder | TreeNodeIteratorOrder::PostOrder => {
                            self.state = TreeNodeIteratorState::Right(Rc::new(RefCell::new(TreeNodeIterator::new(self.order, self.root.as_ref().unwrap().borrow().right.clone()))));
                        }
                        TreeNodeIteratorOrder::InOrder => {
                            self.state = TreeNodeIteratorState::Val;
                        }
                    }
                    self.next()
                }
            }
            TreeNodeIteratorState::Val => {
                match self.order {
                    TreeNodeIteratorOrder::PreOrder => {
                        self.state = TreeNodeIteratorState::Left(Rc::new(RefCell::new(TreeNodeIterator::new(self.order, self.root.as_ref().unwrap().borrow().left.clone()))));
                    }
                    TreeNodeIteratorOrder::InOrder => {
                        self.state = TreeNodeIteratorState::Right(Rc::new(RefCell::new(TreeNodeIterator::new(self.order, self.root.as_ref().unwrap().borrow().right.clone()))));
                    }
                    TreeNodeIteratorOrder::PostOrder => {
                        self.state = TreeNodeIteratorState::Finished;
                    }
                }
                Some(self.root.clone().unwrap())
            }
            TreeNodeIteratorState::Right(iter) => {
                if let Some(item) = iter.borrow_mut().next() {
                    Some(item)
                } else {
                    match self.order {
                        TreeNodeIteratorOrder::PreOrder | TreeNodeIteratorOrder::InOrder => {
                            self.state = TreeNodeIteratorState::Finished;
                        }
                        TreeNodeIteratorOrder::PostOrder => {
                            self.state = TreeNodeIteratorState::Val;
                        }
                    }
                    self.next()
                }
            }
            TreeNodeIteratorState::Finished => {
                None//加入Java开发交流君样：756584822一起吹水聊天
            }
        }
    }
}