如何使用递归迭代器展平递归结构？

Question

我正在尝试展平递归结构，但我在递归迭代器方面遇到了麻烦。

该结构如下所示：

#[derive(Debug, Clone)]
pub struct C {
    name: String,
    vb: Option<Vec<B>>,
}

#[derive(Debug, Clone)]
pub struct B {
    c: Option<C>,
}

#[derive(Debug, Clone)]
pub struct A {
    vb: Option<Vec<B>>,
    flat_c: Option<Vec<C>>,
}

我的计划是遍历vb向量并将其展平为flat_c. 我希望它看起来像这样，或者至少是Vec<String>：

Some([
    C {
        name: "foo",
        vb: None,
    },
    C {
        name: "bar",
        vb: None,
    },
    C {
        name: "fizz",
        vb: None,
    },
    C {
        name: "buzz",
        vb: None,
    },
])

这里我设法做的，稍微扁平化结构，但仅限于最后一个元素，因为未实现递归。

impl A {
    fn flat_c(self) -> Self {
        let fc: Vec<C> = self
            .vb
            .clone()
            .unwrap()
            .iter()
            .flat_map(|x| x.c.as_ref().unwrap().vb.as_ref().unwrap().iter())
            .cloned()
            .map(|x| x.c.unwrap())
            .collect();

        Self {
            flat_c: Some(fc),
            ..self
        }
    }
}

fn main() {
    let a = A {
        vb: Some(vec![
            B {
                c: Some(C {
                    name: "foo".to_string(),
                    vb: Some(vec![B {
                        c: Some(C {
                            name: "bar".to_string(),
                            vb: None,
                        }),
                    }]),
                }),
            },
            B {
                c: Some(C {
                    name: "fiz".to_string(),
                    vb: Some(vec![B {
                        c: Some(C {
                            name: "buzz".to_string(),
                            vb: None,
                        }),
                    }]),
                }),
            },
        ]),
        flat_c: None,
    };

    let a = a.flat_c();
    println!("a: {:#?}", a);
}

操场

的输出flat_c：

Some([
    C {
        name: "bar",
        vb: None,
    },
    C {
        name: "buzz",
        vb: None,
    },
])

我还没有深入研究Iterator这个问题可能需要的特征实现。

我该如何解决这个问题？也许使用fold? 也许甚至不需要递归方法？我不知所措。

Answer 1

熟悉常见的数据结构是个好主意。您有一棵树，并且有多种方法可以遍历这棵树。你没有明确指定使用哪种方法，所以我随意选择了一种易于实现的方法。

这里的关键是实现一个迭代器来跟踪某些状态：所有尚未访问的节点。每次调用 时Iterator::next，我们都会获取下一个值，保存要访问的所有新节点，然后返回该值。

一旦你有了迭代器，你就可以把collect它变成一个Vec.

use std::collections::VecDeque;

impl IntoIterator for A {
    type IntoIter = IntoIter;
    type Item = String;

    fn into_iter(self) -> Self::IntoIter {
        IntoIter {
            remaining: self.vb.into_iter().flatten().collect(),
        }
    }
}

struct IntoIter {
    remaining: VecDeque<B>,
}

impl Iterator for IntoIter {
    type Item = String;

    fn next(&mut self) -> Option<Self::Item> {
        self.remaining.pop_front().and_then(|b| {
            b.c.map(|C { name, vb }| {
                self.remaining.extend(vb.into_iter().flatten());

                name
            })
        })
    }
}

fn to_strings(a: A) -> Vec<String> {
    a.into_iter().collect()
}

#[derive(Debug, Clone)]
struct A {
    vb: Option<Vec<B>>,
}

#[derive(Debug, Clone)]
struct B {
    c: Option<C>,
}

#[derive(Debug, Clone)]
struct C {
    name: String,
    vb: Option<Vec<B>>,
}

fn main() {
    let example: A = A {
        vb: Some(vec![
            B {
                c: Some(C {
                    name: "Hello ".to_string(),
                    vb: None,
                }),
            },
            B {
                c: Some(C {
                    name: "World!".to_string(),
                    vb: None,
                }),
            },
        ]),
    };
    println!("The example struct: {:?}", example);
    //clone a copy for a second example, because to_strings() takes ownership of the example A struct
    let receipt: A = example.clone();
    println!("Iterated: {:?}", to_strings(example));
    // another example of using to_strings()
    println!(
        "As a string: {:?}",
        to_strings(receipt).into_iter().collect::<String>()
    );
}

B从这里开始，如果您需要的话，创建一个迭代器应该很简单。拥有所有None值似乎很愚蠢，所以我将它们省略并直接返回Strings。

我还将其设为按值迭代器。您可以遵循相同的模式来创建一个迭代器，该迭代器返回对B/的引用String，并且仅根据需要克隆它们。

也可以看看：

• 如何为简单的结构实现 Iterator 和 IntoIterator？
• 为二叉树实现 IntoIterator
• 迭代递归结构时无法获取可变引用：一次不能多次借用可变引用
• 二叉搜索树的递归中序遍历