Javascript:迭代二叉树？

Question

如果我想按顺序打印所有音高,以便左边首先然后右边,我该如何迭代以下内容.对于以下第一段代码; 答案应该是a4,b4,c4,d4.我如何以编程方式实现此目的？

var melody2_mus = 
    { tag: 'seq',
      left: 
       { tag: 'seq',
         left: { tag: 'note', pitch: 'a4', dur: 250 },
         right: { tag: 'note', pitch: 'b4', dur: 250 } },
      right:
       { tag: 'seq',
         left: { tag: 'note', pitch: 'c4', dur: 500 },
         right: { tag: 'note', pitch: 'd4', dur: 500 } } }

另一个例子:

 var melody2_mus = 
        { tag: 'seq',
          left: { tag: 'note', pitch: 'b4', dur: 250 } },
          right:
           { tag: 'seq',
             left: { tag: 'note', pitch: 'c4', dur: 500 },
             right: { tag: 'note', pitch: 'd4', dur: 500 } } }

应该打印b4,c4,d4

谢谢

Answer 1

递归函数最简单:

function traverse(obj) {
    // always follow left branch first
    if (obj.left) {
        traverse(obj.left);
    }

    // do stuff for leaf nodes
    if (obj.pitch) {
        console.log(obj.pitch);
    }

    // then the right branch if it exists
    if (obj.right) {
        traverse(obj.right);
    }
}

见http://jsfiddle.net/alnitak/E2ZEB/

或者更一般地说:

function traverse(obj, func) {
    if (!obj) return;

    traverse(obj.left, func);
    func(obj);
    traverse(obj.right, func);
}