是否可以以非递归方式遍历JavaScript中的对象？

Question

例如，我们有一个 JavaScript 对象，它可以包含具有任意嵌套深度的其他对象。是否可以不使用递归遍历此对象的每个元素？

如果不是，那么使用非递归迭代遍历数据结构的最低要求是什么？

Answer 1

正如SLaks 上面所写，任何递归都可以表示为带有堆栈的循环。所以经过一段时间的思考，我想到了下一个解决方案：

var myobj = {
    one: "hello",
    two: "world",
    three: {
        one: 1,
        two: 2,
        three: 4,
        four: {
            one: true,
            two: false
        }
    },
    four: "!"
};

function traverse(obj) {
    var stack = [];

    stack.push(obj);

    while (stack.length) {
        for (var j in stack[0]) {
            if (typeof stack[0][j] === 'object') {
                stack.push(stack[0][j]);
            } else {
                console.log('%s: %s', j, stack[0][j]);
            }
        }
        stack.shift();
    }
}

traverse(myobj);

Answer 2

遍历任意对象需要支持原始类型和复杂类型（包括数组），以及防止循环引用。以下是一个示例非递归函数，它应该遍历和字符串化任何对象：

function FlatStringify( Arg )
{
   var ToString = '', ArgObject, Resume, nStartIndex, Stack = [], Processed = []

   do
   {
      if( Array.isArray( Arg ) )
      {
         var nIndex, nLen = Arg.length

         if( Resume )
         {
            nStartIndex = Resume[1] + 1
            ArgObject = Resume[2]
            Resume = undefined

            if( nStartIndex < nLen )
            {
               ToString += ', '
            }
         }
         else
         {
            if( Processed.indexOf( ArgObject ? ArgObject : Arg ) >= 0 )
            {
               ToString += '{ <cyclic>'
               nStartIndex = nLen
            }
            else
            {
               Processed.push( ArgObject ? ArgObject : Arg )
               nStartIndex = 0
               ToString += '{'
            }
         }

         nIndex = nStartIndex
         if( nIndex < nLen )
         {
            // Save our Array and loop position
            Stack.push( [ Arg, nIndex, ArgObject ] )

            // Restore Object Context if any!
            if( ArgObject )
            {
               ToString += ' ' + Arg[ nIndex ] + ': '
               Arg = ArgObject[ Arg[ nIndex ] ]
            }
            else
            {
               ToString += ' '
               Arg = Arg[ nIndex ]
            }

            nIndex++
         }

         if( nIndex >= nLen )
         {
            ToString += ' }'
            ArgObject = undefined
         }
         else
         {
            // Skip to the while( ... )
            continue
         }
      }
      else if( typeof Arg === 'object' )
      {
        if( Arg == null )
        {
           ToString += 'null'
        }
        else
        {
           ArgObject = Arg
           Arg = Object.keys( ArgObject )
           continue
        }
     }
     else if( typeof Arg === 'string' )
     {
        ToString += "'" + Arg + "'"
     }
     else if( typeof Arg === 'function' )
     {
        ToString += 'function ' +  Arg.name + '(){...}'
     }
     else if( typeof Arg === 'number' )
     {
        ToString += Arg
     }
     else if( typeof Arg === 'boolean' )
     {
        ToString += Arg
     }
     else
     {
        //console.log( typeof Arg )
        ToString += typeof Arg//String( Arg )
     }

     if( Stack.length )
     {
        //console.log( 'Resuming: ' + Stack.length + '(' + nLoops + ')' )
        Resume = Stack.pop()
        Arg = Resume[0]
     }
   }
   while( Resume || ArgObject || Stack.length )

   return ToString
}

是否可以以非递归方式遍历JavaScript中的对象？

Is it possible to traverse object in JavaScript in non-recursive way?

javascript

computer-science

data-structures