preface

在写web后台时，像是前端的menu还有分类，这些都是树状结构的，但数据库查出来的结果都是数组，所以需要将vec转为树形结构再发送给前端

struct和trait定义

pub struct Node<T> {
    item: T,
    children: Option<Vec<Node<T>>>,
}
pub trait TreeNode {
    type Id: std::cmp::Eq + std::hash::Hash;
    fn key(&self) -> Self::Id;
    fn parent_key(&self) -> Option<Self::Id>;
}
pub struct Tree<T> {
    nodes: Option<Vec<Node<T>>>,
}

对于树的每一个节点，都有本身节点的数据和字节点两项，对于 node中children字段，使用Option<Vec<T>>而不是直接使用Vec<T>是为了序列化的结果中不会多出一个children:[]字段，存粹强迫症需求。

TreeNode是作为节点的数据结构需要实现的trait,主要是获得`id`和`parentId`用于计算层级结构。

Tree 的作用是包装Option<Vec<Node<T>>> 类型，因为trait的“孤儿规则”，所以要使用NewTypes模式才能为实现外部trait。

实现部分

impl<T> From<Vec<T>> for Tree<T>
where
    T: TreeNode+Debug,
{
    fn from(value: Vec<T>) -> Self {
        let mut map = std::collections::HashMap::new();
        for item in value {
            map.entry(item.parent_key())
                .or_insert_with(Vec::new)
                .push(Node {
                    item,
                    children: None,
                });
        }
        let nodes=build(&mut map,None);
        Tree{
            nodes
        }
    }
}

fn build<T>(map:&mut HashMap<Option<T::Id>,Vec<Node<T>>>,root:Option<T::Id>)->Option<Vec<Node<T>>>
where
    T:TreeNode
{
    map.remove(&root).map(|mut children|{
        for child in &mut children  {
            child.children=build(map,Some(child.item.key()))
        }
        children
    })
}

上述代码中首先声明了一个空的HashHap ,它的主要作用是做一个结构的转换，以Node 的Id 作为key,然后以key对应的子Node 作为value。

然后通过build函数生成属性结构，这部分用了dfs,build中的map.remove(&root)取出根节点的Node,然后然后将该node下的子节点的children更换为使用递归build(map,Some(child.item.key())) 得到的值。