Сбор рекурсивных функциональных ответов в массиве - PullRequest
Новая
       3

Сбор рекурсивных функциональных ответов в массиве

0 голосов
/ 19 марта 2020

Короче, мой вопрос: как собрать промежуточные ответы / выходные данные рекурсивной функции / метода в массиве, а затем распечатать этот массив где-нибудь еще?

Предположим, у меня есть класс Node: 

class Node {
  constructor (data) {
    this.data = data
    this.left = null
    this.right = null
    this.parent = null
  }
}

И класс BST 

class BST {
  constructor () {
    this.root = null
    this.nodeCount = 0
  }
  insert (data) {
    const node = new Node(data)
    this.nodeCount++
    if (this.root == null) {
      this.root = node
    } else {
      this.insertNode(this.root, node)
    }
    return this.search(data)
  }
  insertNode (node, newNode) {
    if (newNode.data < node.data) {
      if (node.left === null) {
        newNode.parent = node
        node.left = newNode
      } else {
        this.insertNode(node.left, newNode)
      }
    } else {
      if (node.right === null) {
        newNode.parent = node
        node.right = newNode
      } else {
        this.insertNode(node.right, newNode)
      }
    }
  }
  inOrder (node) {
    if (node !== null) {
      this.inOrder(node.left)
      console.log(node.data)
      this.inOrder(node.right)
    }
  }
  createTree (bst, arr = []) {
    for (let item of arr) {
      bst.insert(item)
    }
    return bst
  }
}

Теперь, когда у меня есть эти два класса, я могу создать двоичное дерево: 

const bst = new BST()
const tree = bst.createTree(bst, [15, 25, 10, 7, 22, 17, 13, 5, 9, 27])
const root = tree.getRootNode()

И затем пройти: 

console.log('Traversing tree (InOrder): ')
bst.inOrder(root)

Что я хочу сделать, так это при обходе я хочу записать sh все значения в массиве, а не распечатать его. В результате выполнения bst.inOrder () я получу массив со всеми элементами в дереве. Как я могу это сделать? Заранее спасибо за помощь.

1 Ответ

0 голосов
/ 29 марта 2020

Наконец-то я нашел способ решить эту проблему. Ниже приведен метод, который делает In Order Depth First Traverse, который дает мне отсортированный массив в ответ: 

traverse(cb) {
  function dfs(node) {
    if (node === null) return
    dfs(node.left)
    cb(node)
    dfs(node.right)
    return node
   }
   dfs(this.root)
   return this
}
Этот метод должен быть в классе BST. В основной функции после вставки элементов в дерево (код написан в вопросе) я должен написать следующий код: 

const inOrderData = []
bst.traverse(function (node) {
  inOrderData.push(node.data)
})
console.log("Tree data: ", inOrderData)

Итак, в основном я отправил функцию обратного вызова в метод обхода в качестве параметра, и эта функция обратного вызова принимает узел в качестве параметра. Тогда внутри основной функции я просто пу sh данных узла в массив.

...