Отображение двоичного дерева поиска по трансверсалям на Javascript (рекурсивный путь)

Question

Я пытаюсь разрешить все данные в двоичном дереве. Моя основная проблема заключается в том, что я хочу реализовать рекурсивным образом. В принципе у меня есть этот код до сих пор:

this.levelOrder = function (root) { 
    if (root.data != null) { 
     console.log(root.data); 

     if (root.left != null) { 
      this.levelOrder(root.left); 
     } 

     if (root.right != null) { 
      this.levelOrder(root.right) 
     } 
    } else { 
     return; 
    } 
}; 

Выход 3 2 1 5 4 7

Но это должно быть 3 2 5 1 4 7. Так что в основном я обращаюсь к первому потомку узла, а не сначала печатаю все дети. Есть идеи?

Answer 1

Предполагая, что дерево, как это,

 4 
    2  6 
1 3 5 7 

и литерал объекта

tree = { 
    data: 4, 
    left: { 
     data: 2, 
     left: { 
      data: 1, 
      left: null, 
      right: null 
     }, 
     right: { 
      data: 3, 
      left: null, 
      right: null 
     } 
    }, 
    right: { 
     data: 6, 
     left: { 
      data: 5, 
      left: null, 
      right: null 
     }, 
     right: { 
      data: 7, 
      left: null, 
      right: null 
     } 
    } 
}; 

можно вызвать функцию рекурсивно и получить первую левую часть, а затем в правой части дерева. Алгоритм называется depth-first search.

Эта функция использует одну проверку, поскольку этого достаточно, чтобы сначала проверить, а затем перейти.

var depthFirth = function (node) { 
 
     if (node) { 
 
      console.log(node.data); 
 
      depthFirth(node.left); 
 
      depthFirth(node.right) 
 
     } 
 
    }, 
 
    tree = { data: 4, left: { data: 2, left: { data: 1, left: null, right: null }, right: { data: 3, left: null, right: null } }, right: { data: 6, left: { data: 5, left: null, right: null }, right: { data: 7, left: null, right: null } } }; 
 

 
depthFirth(tree); // 4 2 1 3 6 5 7

Для breadth-first search, алгоритм, итерация каждый уровень дерева первых, вы можете использовать этот код с теми же данными дерева, как описано выше.

var breadthFirst = function (node) { 
 

 
     function bf(queue) { 
 
      var newQueue = []; 
 
      queue.forEach(function (node) { 
 
       console.log(node.data); 
 
       node.left && newQueue.push(node.left); 
 
       node.right && newQueue.push(node.right); 
 
      }); 
 
      newQueue.length && bf(newQueue); 
 
     } 
 

 
     bf([node]); 
 
    }, 
 
    tree = { data: 4, left: { data: 2, left: { data: 1, left: null, right: null }, right: { data: 3, left: null, right: null } }, right: { data: 6, left: { data: 5, left: null, right: null }, right: { data: 7, left: null, right: null } } }; 
 

 
breadthFirst(tree); // 4 2 6 1 3 5 7