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

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);
}

playground

flat_c 的输出:

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

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

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

Answer 1

最好熟悉常见的数据结构。你有一个 tree ，有几种方法to traverse a tree .您没有准确指定使用哪种方法，所以我随意选择了一种易于实现的方法。

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

一旦有了迭代器，就可以将其收集到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 值似乎很愚蠢，所以我将它们排除在外并直接返回 String。

我还把它变成了按值迭代器。您可以按照相同的模式创建一个迭代器，该迭代器返回对 B/String 的引用，并且只在需要时克隆它们。

另见:

• How to implement Iterator and IntoIterator for a simple struct?
• Implement IntoIterator for binary tree
• Cannot obtain a mutable reference when iterating a recursive structure: cannot borrow as mutable more than once at a time
• Recursive inorder traversal of a binary search tree