问：

所遇到问题的上下文和描述

目前我正在学习 Rust 编程语言，上周末我发现自己实现了一个通用的 n-Ary 加权树数据结构，其节点类型和边类型为 。NE

我正在浏览 std 文档并发现了该特征，并很想为这个数据结构实现它。但有一点需要注意：有几种合理的方法可以遍历我想要实现的树数据结构：Iterator

• 预购
• 后购
• 顺序

此外，我希望一个迭代器产生 &引用，一个产生所有先前命名的遍历选项的独占引用 &mut;，因此必须实现 6 个迭代器，其中 3 个迭代器的可变性与其他 3 个迭代器的可变性不同。此外，如果可能的话，我想远离宏（尽管我可以想象它们在这里很有帮助）！

自然而然地，这会导致一些（最小？对我的口味来说有点太多）代码重复。

当前实施

泛型节点数据结构有两种相关方法：

pub fn traverse_ref(&self, traverse: Traverse) -> Box<dyn Iterator<Item = &Self> + '_>

pub fn traverse_mut(&mut self, traverse: Traverse) -> Box<dyn Iterator<Item = &mut Self> + '_>

其中是一个枚举，其中包含遍历树的所有受支持方式。Traverse

它们分别返回正确迭代器结构体和 的框， 其中 和 是树的泛型，是指定发生哪种遍历的类型。Traversal<'t, N, E, M>TraversalMut<'t, N, E, M>NEM

我试图减少重复的尝试在于，我添加了一个特征，其方法处理各种迭代，因此在我的两个实现中，对于给定的遍历方法，只需调用该特征的正确方法。TravellerIterator

这似乎是重复的。

API 示例 （main.rs）

mod tree;

fn main() {
    use std::num::NonZeroU8;
    use tree::Node;

    let mut tree = Node::new(NonZeroU8::new(1));

    tree.add_children(NonZeroU8::new(2), true);
    tree.add_children(NonZeroU8::new(3), false);

    tree.get_children_mut()[0]
        .0
        .add_children(NonZeroU8::new(4), true);
    tree.get_children_mut()[0]
        .0
        .add_children(NonZeroU8::new(5), false);

    for node in tree.traverse_ref(tree::Traverse::PreOrder) {}
}

tree.rs

请注意，为了提高可读性，省略了遍历算法的实际实现，因为它们与面临的问题无关紧要。相反，我提供了一个简单的.todo!()

use std::marker::PhantomData;

mod internal {
    pub trait Sealed {}
}

#[derive(Debug)]
pub struct Node<N, E> {
    value: N,
    children: Vec<(Node<N, E>, E)>,
}

impl<N, E> Node<N, E> {
    pub fn new(value: N) -> Self {
        Self {
            value,
            children: vec![],
        }
    }

    pub fn add_children(&mut self, value: N, edge: E) {
        self.children.push((Node::new(value), edge));
    }

    pub fn get_children_mut(&mut self) -> &mut Vec<(Self, E)> {
        &mut self.children
    }

    pub fn get_value_mut(&mut self) -> &mut N {
        &mut self.value
    }

    pub fn set_value(&mut self, new_value: N) {
        self.value = new_value;
    }

    pub fn traverse_ref(&self, traverse: Traverse) -> Box<dyn Iterator<Item = &Self> + '_> {
        match traverse {
            Traverse::InOrder => Box::new(Traversal::<N, E, InOrder>::new(self)),
            Traverse::PostOrder => Box::new(Traversal::<N, E, PostOrder>::new(self)),
            Traverse::PreOrder => Box::new(Traversal::<N, E, PreOrder>::new(self)),
        }
    }

    pub fn traverse_mut(&mut self, traverse: Traverse) -> Box<dyn Iterator<Item = &mut Self> + '_> {
        match traverse {
            Traverse::InOrder => Box::new(TraversalMut::<N, E, InOrder>::new(self)),
            Traverse::PostOrder => Box::new(TraversalMut::<N, E, PostOrder>::new(self)),
            Traverse::PreOrder => Box::new(TraversalMut::<N, E, PreOrder>::new(self)),
        }
    }
}

#[derive(Debug)]
pub enum Traverse {
    PreOrder,
    PostOrder,
    InOrder,
}

pub trait TraverseMethod: internal::Sealed {}

#[derive(Debug)]
struct PreOrder {}
impl internal::Sealed for PreOrder {}
impl TraverseMethod for PreOrder {}

#[derive(Debug)]
struct InOrder {}
impl internal::Sealed for InOrder {}
impl TraverseMethod for InOrder {}

#[derive(Debug)]
struct PostOrder {}
impl internal::Sealed for PostOrder {}
impl TraverseMethod for PostOrder {}

#[derive(Debug)]
pub struct Traversal<'t, N, E, M>
where
    M: TraverseMethod,
{
    tree: &'t Node<N, E>,
    _marker: PhantomData<M>,
}

impl<'t, N, E, M> Traversal<'t, N, E, M>
where
    M: TraverseMethod,
{
    fn new(tree: &'t Node<N, E>) -> Self {
        Self {
            tree,
            _marker: PhantomData {},
        }
    }
}

#[derive(Debug)]
pub struct TraversalMut<'t, N, E, M>
where
    M: TraverseMethod,
{
    tree: &'t mut Node<N, E>,
    _marker: PhantomData<M>,
}

impl<'t, N, E, M> TraversalMut<'t, N, E, M>
where
    M: TraverseMethod,
{
    fn new(tree: &'t mut Node<N, E>) -> Self {
        Self {
            tree,
            _marker: PhantomData {},
        }
    }
}

trait Traveller {
    type Item;

    fn travel_preorder(&mut self) -> Option<Self::Item> {
        todo!()
    }

    fn travel_postorder(&mut self) -> Option<Self::Item> {
        todo!()
    }

    fn travel_inorder(&mut self) -> Option<Self::Item> {
        todo!()
    }
}

impl<'t, N, E> Traveller for Traversal<'t, N, E, PreOrder> {
    type Item = &'t Node<N, E>;
}

impl<'t, N, E> Iterator for Traversal<'t, N, E, PreOrder> {
    type Item = &'t Node<N, E>;

    fn next(&mut self) -> Option<Self::Item> {
        self.travel_preorder()
    }
}

impl<'t, N, E> Traveller for TraversalMut<'t, N, E, PreOrder> {
    type Item = &'t mut Node<N, E>;
}

impl<'t, N, E> Iterator for TraversalMut<'t, N, E, PreOrder> {
    type Item = &'t mut Node<N, E>;

    fn next(&mut self) -> Option<Self::Item> {
        self.travel_preorder()
    }
}

impl<'t, N, E> Traveller for Traversal<'t, N, E, PostOrder> {
    type Item = &'t Node<N, E>;
}

impl<'t, N, E> Iterator for Traversal<'t, N, E, PostOrder> {
    type Item = &'t Node<N, E>;

    fn next(&mut self) -> Option<Self::Item> {
        self.travel_postorder()
    }
}

impl<'t, N, E> Traveller for TraversalMut<'t, N, E, PostOrder> {
    type Item = &'t mut Node<N, E>;
}

impl<'t, N, E> Iterator for TraversalMut<'t, N, E, PostOrder> {
    type Item = &'t mut Node<N, E>;

    fn next(&mut self) -> Option<Self::Item> {
        self.travel_postorder()
    }
}

impl<'t, N, E> Traveller for Traversal<'t, N, E, InOrder> {
    type Item = &'t Node<N, E>;
}

impl<'t, N, E> Iterator for Traversal<'t, N, E, InOrder> {
    type Item = &'t Node<N, E>;

    fn next(&mut self) -> Option<Self::Item> {
        self.travel_inorder()
    }
}

impl<'t, N, E> Traveller for TraversalMut<'t, N, E, InOrder> {
    type Item = &'t mut Node<N, E>;
}

impl<'t, N, E> Iterator for TraversalMut<'t, N, E, InOrder> {
    type Item = &'t mut Node<N, E>;

    fn next(&mut self) -> Option<Self::Item> {
        self.travel_inorder()
    }
}