二叉树前序遍历的非递归实现

二叉树前序遍历的非递归实现：

function Node (data, left, right) {
    this.data = data
    this.left = left || null
    this.right = right || null
}

function BST () {
    this.root = null
}

function insertNode (parentNode, newNode) {
    if (newNode.data < parentNode.data) {
        if (parentNode.left === null) {
            parentNode.left = newNode
        } else {
            insertNode(parentNode.left, newNode)
        }
    } else {
        if (parentNode.right === null) {
            parentNode.right = newNode
        } else {
            insertNode(parentNode.right, newNode)
        }
    }
}

BST.prototype.insert = function (data) {
    const node = new Node(data, null, null)
    if (this.root === null) {
        this.root = node
    } else {
        insertNode(this.root, node)
    }
}

const bst = new BST();
[23, 45, 16, 37, 3, 99, 22].forEach((item) => {
    bst.insert(item)
})

function preTraverseBST (bst) {
    let node = bst.root
    let arr = [node] // 作为一个栈来使用，只用它的shift和unshift方法
    while (node !== null && arr.length > 0) {
        console.log(node.data)
        if (node.left !== null) {
            arr.unshift(node.left)
            node = node.left
        } else {
            node = arr.shift()
            while (node.right === null && arr.length > 0) {
                node = arr.shift()
            }
            node = node.right
            arr.unshift(node)
        }
    }
}

preTraverseBST(bst)