javascript使递归数组遍历并更新一些内部值(指针)

Question

我得到了以下数组:

let arr = [
{
    children: [
        {
            children: [],
            current: true //pointer is at the first element with no children
        },
        {
            children: [
                {
                    children: [],
                    current: false  //if the pointer is here, next item should be the next parent`s first child (without children)
                },
                {
                    children: [
                               {
                                  current: false,
                                  children: []
                               },
                               {
                                current: false,
                                children: []
                               }
                              ],

                },
                {
                    children: [],
                    current: false 
                }               
            ]
        },
        {
            children: [],
            current: false
        },      
    ]

},
{
    children: [],
    current: false
},
{
    children: [],
    current: false
},
{
    children: [],
    current: false
},
];

我正在创建一个数组遍历器(树遍历器)，以便用户可以来回遍历它。例如，当用户点击前进按钮时，指针 (current) 移动到数组中子元素中的下一个位置，使该元素 current 指针 false 和下一个元素 current 指针为 true。如果当前父级中不再有子级，则指针将移动到下一个父级，并使 current 成为那里的第一个子级(没有子级)。用户只能在没有子项的子项之间移动(它们的 children 元素为空或根本没有子项)，无法选择有子项的父项并将其设置为当前 。我的代码如下:

makeNextQuestionCurrent = (arr, currentChanged = false) => {
    arr.some(
        (item, index) => {
            if(item.children && item.children.length > 1){
                if(!currentChanged){
                    this.makeNextQuestionCurrent(item.children);
                }
            }else{
                  if(item.current && !currentChanged){
                     item.current = false;
                     if(arr[index + 1]){      
                         arr[index + 1].current = true;
                                currentChanged  = true;
                     }else{
                           //some logic should be here...
                          }
                }
            }
        }
    );
}

所以当我到达 parent 的 child 的末尾时，我的问题就开始了。当 child 是最后一个时，我无法跳到下一个 parent child 。任何如何修复它的想法都将受到欢迎。谢谢。

Answer 1

我认为您回答了自己的问题:

So my problem begins when I reach the end of children of a parent. When the child is last, I cannot jump to next parent children.

当你走完 Twig 时，你需要一种方法从 Twig 上退下来。有两种方法可以做到这一点:

1. 为每个子项添加一个指向其父项的指针，或者
2. 让您的树步行者使用堆栈数据结构跟踪父级(及其父级)。

如果您想维持当前的策略，将行走状态保持在树本身内，则可以选择选项 1。 但这是一个非常糟糕的主意:

• 它使数据结构与本应独立的程序状态变得困惑。
• 它会产生复杂的代码，就像您的代码一样。
• 内存和 CPU 效率都很低。
• 它一次只允许一名树木步行者运行。

如果您决定按照我的建议将步行者状态与树数据分开，则可以选择选项 1 或选项 2。

这是选项 2 树遍历器的实现:

class TreeWalker {
  currentNode
  currentChildIdx
  parentStack

  constructor (treeRoot) {
    this.currentNode = treeRoot
    this.currentChildIdx = -1
    this.parentStack = []
  }

  next () {
    // walk until a leaf node is found or we hit the end (terminal conditions are return stmts inside the loop)
    while (true) {
      const currentNode = this.currentNode
      const currentChildIdx = ++this.currentChildIdx
      if (currentNode.children && currentChildIdx < currentNode.children.length) {
        // we have more children; advance to the nex
        const child = currentNode.children[currentChildIdx]
        if (child.children) {
          // the next child itself has children; save state at this level, then descend
          this.parentStack.push({ node: currentNode, childIdx: currentChildIdx })
          this.currentNode = child
          this.currentChildIdx = -1
        } else {
          // the next child is a leaf; return it
          return child
        }
      } else if (this.parentStack.length > 0) {
        // no more children; back out to a parent.
        let p = this.parentStack.pop()
        this.currentNode = p.node
        this.currentChildIdx = p.childIdx
      } else {
        // back at root, all done
        return null
      }
    }
  }

  previous () {
    // I'll leave this one for you.
  }

}

TreeWalker 假定一致的树结构，包括具有与任何其他节点结构相同的根节点。我没有在树中存储行走状态，因此current:全部被删除。

let root = {
  val: 'branch a',
  children: [
    {
      val: 'leaf 1'
    },
    {
      val: 'branch b',
      children: [
        {
          val: 'leaf 2'
        }
      ]
    },
    {
      val: 'branch c',
      children: [
        {
          val: 'leaf 3'
        }
      ]
    }
  ]
}

我给你留了一些工作:;)

• 上一个()
• 如果根节点也是叶节点，则返回根节点。