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

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);