asyn c рекурсивная функция карты в машинописном тексте с изменениями родительских данных, начиная с листового узла

Question

Проблема, с которой я столкнулся, состоит в том, чтобы найти листовой узел в дереве (не в двоичном дереве), который необходимо изменить; Я должен вычислить blake2b ha sh из данных листа, передать это родителю, а затем вычислить blake2b ha sh этого и так далее, пока я не достигну узла root, затем я вычислю то же самое для root node.

Начальные интерфейсы и конечный интерфейс приведены ниже:

interface sto {
  name: string
  children: sto[]
}

interface stoWithIds {
  id: string // blake2b(data)
  data: {
    name: string
    children: stoWithIds[]
  }
}

функции, которые мне нужны:

function transformSto (op: sto): stoWithIds {
  const { children, ...rest } = op
  return { id: '', data: { ...rest, children: [] } }
}

async function visitNode (node: sto, parent: stowithId) {
  // this will start executing when the leaf is found then go upwards
  node.children.map(async c => await visitNode(node, parent))

  // here be creating the ids
  parent.children.push(/* our calculation, but this doesn't work for children on the same level*/)
}

, тогда я бы назвал его

const sto: sto = {
  name: 'Root',
  children: [
    {
      name: 'child 1',
      children: [
        {
          name: 'child2',
          children: []
        },

        {
          name: 'child3',
          children: []
        }
      ]
    }
  ]
}
await visitNode(sto, transformSto(sto))

то, что я могу получить после того, как это будет выполнено, это следующее:

const stowithId: stoWithIds = {
  id: 'blake2b(data)',
  data: {
    name: 'Root',
    children: [
      {
        id: 'blake2b(data)',
        data: {
          name: 'child 1',
          children: [
            {
              id: 'blake2b(data)',
              data: {
                name: 'child2',
                children: []
              }
            },
            {
              id: 'blake2b(data)',
              data: {
                name: 'child3',
                children: []
              }
            }
          ]
        }
      }
    ]
  }
}

Я боролся с этим много часов. Я уверен, что есть простое решение этой проблемы, но я не вижу его. Я не очень хорошо знаком с обходом деревьев, поэтому большую часть воскресенья я читал об этом, но до сих пор не могу этого понять. Любая помощь приветствуется.

Answer 1

Для истории и справки вот решение, оно довольно элегантное.

/**
 * Walks the tree and finds the leaf then starts from there going upwards
 * @param ops 
 */
export async function walkTheTreeFromLeafAndMakeChanges (ops: sto[]): Promise<stoWithIds[]> {
  async function visitNode (node: sto): Promise<stoWithIds> {
    async function visit (node: sto): Promise<stoWithIds> {
      // this is the way how to use _unusedWithCamelCase
      const { children: _unusedChildren, ...rest } = node

      const newNode: stoWithIds = { id: '', data: { ...rest, children: [] } }

      // if we put this firs we will get the leaf executed first then the same level leaf
      newNode.data.children = await Promise.all(
        node.children.map(async o => await visitNode(o))
      )

      return { id: blake2b(newNode), data: newNode.data }
    }

    return await visit(node)
  }

  const t = await Promise.all(
    ops.map(async o => {
      return await visitNode(o)
    })
  )
  // console.log('END', JSON.stringify(t))
  return t
}

Надеюсь, это поможет вам rnet людей