JavaScript/ typescript : Created Doubly-Sorted Tree from List

Question

我有一个数组，表示根据以下模型的展平树:

export interface TreeModel {
  id: number;
  parent: number;
  value: string;
  children?: Array<TreeModel>;
}

示例数据如下:

[
  { id: 1,  parent: 5,  value: 'Apple' },
  { id: 2,  parent: 7,  value: 'Carrot' },
  { id: 3,  parent: 10, value: 'Lettuce' },
  { id: 4,  parent: 5,  value: 'Orange' },
  { id: 5,  parent: 0,  value: 'Fruit' },
  { id: 6,  parent: 0,  value: 'Condiments' },
  { id: 7,  parent: 0,  value: 'Vegetables' },
  { id: 8,  parent: 6,  value: 'Salt' },
  { id: 9,  parent: 6,  value: 'Pepper' }
  { id: 10, parent: 7,  value: 'Green Vegetables' },
  { id: 11, parent: 0,  value: 'Microwave' },
  { id: 12, parent: 0,  value: 'Utensils' }
]

数据可以有任意数量的嵌套子项。

我想创建一棵具有类似于以下结构的树:

在此结构中，所有内容均按字母顺序排序，并且具有子节点的节点列在顶部。

使用示例数据，这将提供以下结构:

[
  {
    "id": 6, "parent": 0, "value": "Condiments", "children": [
      {
        "id": 9, "parent": 6, "value": "Pepper"
      }, {
        "id": 8, "parent": 6, "value": "Salt"
      }
    ]
  }, {
    "id": 5, "parent": 0, "value": "Fruit", "children": [
      {
        "id": 1, "parent": 5, "value": "Apple"
      }, {
        "id": 4, "parent": 5, "value": "Orange"
      }
    ]
  }, {
    "id": 7, "parent": 0, "value": "Vegetables", "children": [
      {
        "id": 10, "parent": 7, "value": "Green Vegetables", "children": [
          {
            "id": 3, "parent": 10, "value": "Lettuce"
          }
        ]
      },
      {
        "id": 2, "parent": 7, "value": "Carrot"
      }
    ]
  },
  {
    "id": 11, "parent": 0, "value": "Microwave"
  }, {
    "id": 12, "parent": 0, "value": "Utensils"
  }
]

如何使用 JavaScript/Typescript/RxJS 以最有效的方式实现这一点？

这是我到目前为止所尝试过的，尽管域与我的示例不同:

  processSavedTrends(savedTrends) {
    const mappedTrends: Array<TreeModel> = this.getMappedTrends(savedTrends);
    from(mappedTrends)
      .pipe(
        groupBy(trend => trend.parent),
        mergeMap(trendGroup => trendGroup.pipe(toArray())),
        map(parentGroup => parentGroup.sort((firstItem, secondItem) => {
          const cleanFirstItem = firstItem.value.trim().toLowerCase();
          const cleanSecondItem = secondItem.value.trim().toLowerCase();
          if (cleanFirstItem < cleanSecondItem) {
            return -1;
          } else if (cleanFirstItem > cleanSecondItem) {
            return 1;
          } else {
            return 0;
          }
        }))
      )
      .subscribe(trendGroup => {
        const trendGroups = [];
        trendGroups.push(trendGroup);
        this.createTreeFromTrendGroups(trendGroups);
      });
  }

  createTreeFromTrendGroups(trendGroups) {
    trendGroups.forEach(group => console.log(group));
  }

  getMappedTrends(savedTrends: Array<SavedTrendModel>): Array<TreeModel> {
    return savedTrends.map((savedTrend: SavedTrendModel) => {
      return {
        id: savedTrend.objectID,
        parent: savedTrend.parentID,
        value: savedTrend.name
      };
    });
  }

这提供了一个数组数组，其中嵌套数组按父级分组。

非常感谢您的帮助，谢谢!

Answer 1

这是我所拥有的https://es6console.com/jjs2nq9p/

interface TreeModel {
  id: number;
  parent: number;
  value: string;
  children?: Array<TreeModel>;
}

const oData : TreeModel[] = [
  { id: 1,  parent: 5,  value: 'Apple' },
  { id: 2,  parent: 7,  value: 'Carrot' },
  { id: 3,  parent: 10, value: 'Lettuce' },
  { id: 4,  parent: 5,  value: 'Orange' },
  { id: 5,  parent: 0,  value: 'Fruit' },
  { id: 6,  parent: 0,  value: 'Condiments' },
  { id: 7,  parent: 0,  value: 'Vegetables' },
  { id: 8,  parent: 6,  value: 'Salt' },
  { id: 9,  parent: 6,  value: 'Pepper' },
  { id: 10, parent: 7,  value: 'Green Vegetables' }
]

const build = (pid) => {
  oData.filter(d => d.parent === pid).forEach(d => {
    d.children = oData.filter(c => c.parent === d.id);
    build(d.id);
    if (d.children.length > 0) {
      oData = oData.filter(c => c.parent !== d.id);
      d.children.forEach(c => build(c.id));
    } else {
      delete d.children;
    }
  });
}
build(0);
console.log(JSON.stringify(oData));