在 javascript 中遍历对象树

Question

所以我在 VueJs 中制作了一个类似结构的文件夹列表，我的问题是遍历这个对象树。这是我的树：

    var data= {
      name:"root"
      id:0,
      isLeaf:false,
      parents:null,
      children:[
          {
        type: "TEST",
        linkageId: {},
        linkageWebProfileId: {},
        isActive: true,
        isLeaf: false,
        name: "TESTDATA",
        id: "1000",
        children:[
          {
            type: "TEST",
            linkageId: {},
            linkageWebProfileId: {},
            isActive: true,
            isLeaf: false,
            name: "TESTDATA",
            id: "1001",
          },
          {
            type: "TEST",
            linkageId: {},
            linkageWebProfileId: {},
            isActive: true,
            isLeaf: false,
            name: "TESTDATA",
            id: "1002",
          }
        ]
      },
      {
        type: "TEST",
        linkageId: {},
        linkageWebProfileId: {},
        isActive: true,
        isLeaf: false,
        name: "TESTDATA",
        id: "1003",
        children:[
          {
            type: "TEST",
            linkageId: {},
            linkageWebProfileId: {},
            isActive: true,
            isLeaf: false,
            name: "TESTDATA",
            id: "1004",
          },
          {
            type: "TEST",
            linkageId: {},
            linkageWebProfileId: {},
            isActive: true,
            isLeaf: true,
            name: "TESTDATA",
            id: "1005",
          }
        ]
      },
    
    ]
    
 }

我已经做了一个函数，从新叶子到根之前的最后一个祖先的路径，我可以通过引用随时访问根 'data'。

function makePath() {
 let ids=[];
        let treePointer=params //params is just a pointer to the newly created leaf

        while(treePointer.name!=="root"){
          ids.push(treePointer.id)
          treePointer=treePointer.parent
        } //traverses up to the root
}

如果我要在文件夹 1002 中插入，它将 return:

[1649689828862, '1002', '1000']  //the first one is the auto generated id

children: null
id: 1649731709654
isLeaf: true
name: "New Leaf"
parent: A
children: Array(0)
    id: "1002"
    isActive: true
    isLeaf: false
    linkageId: Object
    linkageWebProfileId: Object
    name: "TESTDATA"
      parent: A
      children: Array(2)
      id: "1000"
      isActive: true
      isLeaf: false
      linkageId: Object
      linkageWebProfileId: Object
      name: "TESTDATA"
         parent: A
         children: Array(2)
         id: 0
         isLeaf: false
         name: "root"
         parent: null    
//This is the generated object that insert leaf creates, an inverted tree with the new leaf at the top

在此之后，我删除了数组的第一个索引，将其反转，因此新叶子的父级是最后一个索引，并将新生成的 id 保存在另一个变量中我现在的问题是当我想从根向下遍历时树并寻找新的叶子父级它不会 return 预期的结果，这是当我想在同一文件夹中插入一个新文件时

 treePointer=this.data //resets treePointer to the root  

 ids.shift() //remove the leaf from the path

 ids.reverse() //make the path left to right the last one being the parent's leaf

 const children = [...this.data.children]  //gets the children of the root

        while(treePointer.id !== ids[ids.length-1]) {  //short circuit when the pointer is at leaf's parent
          treePointer= children.find(obj=>{ // keep reassigning treePointer until it traverses to the leaf's parent
            let node;
            for(var x =0; obj.id!== ids[x] && x < ids.length;x++, node=x) //traverses through the path and gets the correct id of the current array of children
            return obj.id === ids[node] //returns the obj in the treePointer's array of children that has the correct id
          })
        }

我已经重新评估了该代码，从逻辑上讲它是合理的，但是我没有得到的是 while 循环内的 treePointer 似乎没有被重新分配发现它只是在我控制台记录它时保留在根目录下但最终 treePointer 到达一个没有属性 'id' 的节点，这意味着它误入了错误的路径并且没有短路并继续向下遍历，这是没有意义的。是我的查找函数有问题还是我的语法错误？

整个组件的代码

<template>
  <div class="py-8 px-5" style="min-height: calc(100vh - (112px + 2.75rem))">
    <div class="flex flex-col w-full">
      <button class="cursor-pointer relative flex flex-row items-center h-10 focus:outline-none " @click="addNode">
        <span class="text-sm tracking-wide truncate ml-6">Add Folder</span>
      </button>
    </div>
    <VueTreeList
      @click="onClick"
      @change-name="onChangeName"
      @delete-node="onDel"
      @add-node="onAddNode"
      ref="tree"
      :model="data"
      default-tree-node-name="New Folder"
      default-leaf-node-name="New File"
      v-bind:default-expanded="false"
    >
      <span class="icon" slot="addTreeNodeIcon"></span>
      <span class="icon" slot="addLeafNodeIcon">＋</span>
      <span class="icon" slot="editNodeIcon"></span>
      <span class="icon" slot="delNodeIcon">✂️</span>
      <span class="icon" slot="leafNodeIcon"></span>
      <span class="icon" slot="treeNodeIcon"></span>
    </VueTreeList>
  </div>
  
</template>

<script>
import { VueTreeList, Tree } from 'vue-tree-list'

const dummyData = [
  {
    type: "TEST",
    linkageId: {},
    linkageWebProfileId: {},
    isActive: true,
    isLeaf: false,
    name: "TESTDATA",
    id: "1000",
    children:[
      {
        type: "TEST",
        linkageId: {},
        linkageWebProfileId: {},
        isActive: true,
        isLeaf: false,
        name: "TESTDATA",
        id: "1001",
      },
      {
        type: "TEST",
        linkageId: {},
        linkageWebProfileId: {},
        isActive: true,
        isLeaf: false,
        name: "TESTDATA",
        id: "1002",
      }
    ]
  },
  {
    type: "TEST",
    linkageId: {},
    linkageWebProfileId: {},
    isActive: true,
    isLeaf: false,
    name: "TESTDATA",
    id: "1003",
    children:[
      {
        type: "TEST",
        linkageId: {},
        linkageWebProfileId: {},
        isActive: true,
        isLeaf: false,
        name: "TESTDATA",
        id: "1004",
      },
      {
        type: "TEST",
        linkageId: {},
        linkageWebProfileId: {},
        isActive: true,
        isLeaf: true,
        name: "TESTDATA",
        id: "1005",
      }
    ]
  },
]


const dummyData2= {
    type: "TEST",
    linkageId: {},
    linkageWebProfileId: {},
    isActive: true,
    isLeaf: true,
    name: "NEWTEST",
    id: "4",
    children:[]
}

export default {
    components: {
      VueTreeList
    },
    data() {
      return {
        data: new Tree([]),
      }
    },
    async mounted(){
      const parsedData = (dummyData) ? ([...dummyData]) : []
      this.data=new Tree([
        ...parsedData
      ])
    },

    methods: {

      onDel(node) {
        console.log('deletedNode',node)
        node.remove()
      },

      onChangeName(params) {
        console.log(params)
      },

      onAddNode(params) {
        if(params.isLeaf==true){
        let ids=[];
        let treePointer=params
        console.log('paramsContent', params)

        while(treePointer.name!=="root"){
          ids.push(treePointer.id)
          treePointer=treePointer.parent
        }

        console.log('pathLeaf to root', ids)

        this.onDel(params)  //delete the new leaf since the package immediately inserts it 

        treePointer=this.data //let pointer point to the local tree inside this component
        ids.shift()
        ids.reverse()
        const children = [...this.data.children]

        
        console.log('pathRoot to leafParent', ids)

        while(treePointer.id !== ids[ids.length-1]) {
          treePointer= children.find(obj=>{
            let node;
            for(var x =0;obj.id!== ids[x] && x< ids.length;x++, node=x)
            return obj.id === ids[node]
          })
        }

        treePointer.addChildren(dummyData2) //dummyData2 is the new data that is inputted by user
        }

      },


      onClick(params) {
        console.log(params)
      },

      addNode() {

      },

      
      addChild() {

      },
      
    }
  }
</script>

<!-- Add "scoped" attribute to limit CSS to this component only -->
<style scoped lang="scss"></style>

Answer 1

以下代码问题不大

while(treePointer.id !== ids[ids.length-1]) {
  treePointer= children.find(obj => {
    let node;
    for(var x = 0; obj.id !== ids[x] && x < ids.length; x++, node=x)
      return obj.id === ids[node]
  })
}

第一个问题 obj.id !== ids[x] 这个条件永远不会让 for 循环运行如果它相等，所以循环永远不会检查 obj.id === ids[node] 所以 find 总是会得到 undefined 等于 false
第二个问题是节点将保持 undefined 直到第二次迭代，因为增量部分在第一次迭代后仅运行s 而不是节点你可以使用 x 的 for 循环
第三个问题是 children 永远不会更新到下一组子节点，所以即使它在第一次迭代中找到叶子，它在第二次迭代中也找不到任何东西，所以 while 循环将运行连续
第四个问题是，即使在删除 obj.id !== ids[x] 条件并更新子项后，它在第二次迭代中也会失败，因为 foor 循环将在第一次迭代中 return 并且当移动到第二次时它永远找不到叶子 obj.id

要解决问题，您可以更新代码如下：

let children = [...this.data.children];
while(treePointer.id !== ids[ids.length-1]) {
  treePointer = children.find(obj => {
    let result = false;
    for(var x = 0; x < ids.length; x++) {
      if (obj.id === ids[x]) {
        result = true;
        break;
      }
    }
    return result;
  });
  children = treePointer.children;
}

Working Example

重构版本

因为我们已经知道 ids 是从根开始排序的到我们想要找到的叶节点，我们可以更新代码如下;

let children = [...this.data.children];
idx = 0;
while(treePointer.id !== ids[ids.length-1]) {
  treePointer = children.find(obj => ids[idx] == obj.id);
  children = treePointer.children;
  idx += 1;
}

Working Example

在 javascript 中遍历对象树

Traversing an object tree in javascript

javascript

algorithm

tree

data-structures

vue.js

重构版本