如何在Rust中为递归数据结构Tree实现fmt::Display trait

你需要为以下递归定义的Tree结构体实现Display trait，使其输出特定的树形格式：

#[derive(Debug)]
struct Tree<'a> {
    node: (&'a str, Vec<Tree<'a>>)
}

impl<'a> Tree<'a> {
   fn new(str: &'a str) -> Tree<'a> {
    Tree {node: (str, Vec::new())}
   }

   pub fn merge_sub (&mut self, sub: Tree<'a>) {
    self.node.1.push(sub); 
   }
}

fn main(){
 
    let ta = Tree::new("a");
    let mut tb = Tree::new("b");
    tb.merge_sub(ta);

    let tc = Tree::new("c");
    let mut td = Tree::new("d");
    td.merge_sub(tc);

    let te = Tree::new("e");
    let mut tf = Tree::new("f");
    tf.merge_sub(te);


    let mut tg = Tree::new("g");
    tg.merge_sub(tb);
    tg.merge_sub(td);
    tg.merge_sub(tf);
    println!("sub tree g: {:#?}.", tg);
    println!("Display: {}.", tg);
}

期望输出格式：

|--b--a
   |
g--|--d--c
   |
   |--f--e

当前的Display实现卡在递归处理部分，以下是完整的解决方案：

要实现这种自定义树形输出，需要在递归时跟踪当前的前缀格式，区分不同层级的对齐符号。可以通过添加辅助递归函数来处理上下文信息（比如当前前缀、是否为最后一个子节点），完整的Display实现如下：

use std::fmt;

#[derive(Debug)]
struct Tree<'a> {
    node: (&'a str, Vec<Tree<'a>>)
}

impl<'a> Tree<'a> {
   fn new(str: &'a str) -> Tree<'a> {
    Tree {node: (str, Vec::new())}
   }

   pub fn merge_sub (&mut self, sub: Tree<'a>) {
    self.node.1.push(sub); 
   }
}

impl<'a> fmt::Display for Tree<'a>{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result{
        // 先输出根节点值
        write!(f, "{}", self.node.0)?;
        let children = &self.node.1;
        if !children.is_empty() {
            for (i, child) in children.iter().enumerate() {
                writeln!(f)?;
                let is_last = i == children.len() - 1;
                // 根节点子节点的前缀：非最后一个用"   |"，最后一个用"    "
                let prefix = if is_last { "    " } else { "   |" };
                write!(f, "{}--", prefix)?;
                // 递归处理子节点，传递前缀和是否为最后一个节点的标记
                child.fmt_tree(f, prefix, is_last)?;
            }
        }
        Ok(())
    }
}

impl<'a> Tree<'a> {
    // 辅助递归函数：处理子节点的格式化逻辑
    fn fmt_tree(&self, f: &mut fmt::Formatter, parent_prefix: &str, is_last: bool) -> fmt::Result {
        write!(f, "{}", self.node.0)?;
        let children = &self.node.1;
        if !children.is_empty() {
            for (i, child) in children.iter().enumerate() {
                writeln!(f)?;
                // 根据父节点是否为最后一个，生成当前节点的对齐前缀
                let current_prefix = if is_last { "    " } else { "   |" };
                let full_prefix = format!("{}{}", parent_prefix, current_prefix);
                write!(f, "{}--", full_prefix)?;
                // 递归调用，更新前缀和是否为最后一个节点的标记
                child.fmt_tree(f, &full_prefix, i == children.len() - 1)?;
            }
        }
        Ok(())
    }
}

fn main(){
    let ta = Tree::new("a");
    let mut tb = Tree::new("b");
    tb.merge_sub(ta);

    let tc = Tree::new("c");
    let mut td = Tree::new("d");
    td.merge_sub(tc);

    let te = Tree::new("e");
    let mut tf = Tree::new("f");
    tf.merge_sub(te);

    let mut tg = Tree::new("g");
    tg.merge_sub(tb);
    tg.merge_sub(td);
    tg.merge_sub(tf);
    println!("sub tree g: {:#?}.", tg);
    println!("Display:\n{}.", tg);
}

关键逻辑说明： #

• 根节点处理：先输出根节点字符串，再遍历子节点，每个子节点前换行并添加对应前缀与连接符。
• 辅助递归函数fmt_tree：
  • 接收父节点的前缀和是否为最后一个节点的标记，生成当前节点的对齐前缀；
  • 若父节点是最后一个子节点，当前节点前缀用空格填充，避免多余竖线；若不是，则保留竖线维持树形连贯性。
• 连接符与换行：每个子节点前添加--连接符，子节点的子节点换行后对齐，保证树形层次感。

运行代码后，println!("Display:\n{}.", tg);会输出符合预期的格式。

内容的提问来源于stack exchange，提问作者Theodora