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, с4, 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); 
} 

Answer 2

Вот копия ответа Альнитак, но абстрагировать с шаблоном для посетителей.

function traverse(obj, cb) { 
    cb(obj); 
    if (obj.left) { 
     traverse(obj.left, cb); 
    } 
    if (obj.right) { 
     traverse(obj.right, cb); 
    } 
} 

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 } } } 

traverse(melody2_mus, function(node) { 
    if (node.pitch) { 
     console.log(node.pitch); 
    } 
}); 

http://jsfiddle.net/E2ZEB/3/