SOURCE

/**
 * 树的节点
 * @param  data  节点的数值
 * @param  left  该节点的左子节点
 * @param  right 该节点的右子节点
 */
function TreeNode(data, left, right) {
    this.data = data;
    this.left = left || null;
    this.right = right || null;
}

/**
 * 二叉查找树
 * @param  rootNode 根节点
 */
function BinarySearchTree(rootNode) {
    this.rootNode = rootNode || null;
}

BinarySearchTree.prototype = {
    insert: function (data) {
        // 生成新的节点
        var newNode = new TreeNode(data);
        // 判断根节点是否存在
        if (!this.rootNode) {
            this.rootNode = newNode;
            return;
        }
        var currentNode = this.rootNode;
        var parent = null;
        while (true) {
            parent = currentNode;
            if (data < currentNode.data) {
                currentNode = currentNode.left;
                if (!currentNode) {
                    parent.left = newNode;
                    return;
                }
            } else if (data > currentNode.data) {
                currentNode = currentNode.right;
                if (!currentNode) {
                    parent.right = newNode;
                    return;
                }
            } else {
                console.log("该节点已存在");
                return;
            }
        }
    },
    // 查找节点
    find: function (data) {
        // 判断根节点是否存在
        if (!this.rootNode) {
            return;
        }
        var currentNode = this.rootNode;
        while (true) {
            if (!currentNode) {
                console.log("该节点不存在");
                return;
            }
            if (data < currentNode.data) {
                currentNode = currentNode.left;
            } else if (data > currentNode.data) {
                currentNode = currentNode.right;
            } else {
                return currentNode;
            }
        }
    },
    // 删除目标节点
    removeNode: function (data) {
        // 判断根节点是否存在
        if (!this.rootNode) {
            return;
        }
        // 目标节点的父节点
        var parent = null;
        // 目标节点
        var currentNode = this.rootNode;
        // 目标节点位于父节点的位置
        var place = null;
        while (true) {
            if (!currentNode) {
                console.log("该节点不存在");
                return;
            }
            if (data < currentNode.data) {
                parent = currentNode;
                currentNode = currentNode.left;
                place = "left";
            } else if (data > currentNode.data) {
                parent = currentNode;
                currentNode = currentNode.right;
                place = "right";
            } else {
                // 找到对应节点跳出循环
                break;
            }
        }

        if (!currentNode.left) {
            // 删除的节点没有左孩子的情况
            parent[place] = currentNode.right || null;
        } else if (!currentNode.right) {
            // 删除的节点没有右孩子的情况
            parent[place] = currentNode.left || null;
        } else {
            // 用于代替的节点
            var replaceNode = currentNode.left;
            // 代替节点的父节点
            var replaceNodeParent = null;
            // 循环找出左子树中最大的节点（即用于代替的节点）
            while (replaceNode.right) {
                replaceNodeParent = replaceNode;
                replaceNode = replaceNode.right;
            }
            // 代替原位置
            parent[place] = replaceNode;
            // 当代替节点就是删除的节点的左子节点时无需赋左子树
            if (replaceNodeParent) {
                replaceNodeParent.right = replaceNode.left || null;
                parent[place].left = currentNode.left;
            }
            // 获取删除的节点的右子树
            parent[place].right = currentNode.right;
        }
        return;
    },
    preOrder: function (curNode) {
        if (curNode !== null) {
            console.log(curNode.data);
            this.preOrder(curNode.left);
            this.preOrder(curNode.right);
        }
    },
    inOrder: function (curNode) //三种遍历的差别是打印结点Key的语句的位置不同
    {
        if (curNode !== null) {
            this.inOrder(curNode.left);
            console.log(curNode.data);
            this.inOrder(curNode.right);
        }
    },
    postOrder: function (curNode) {
        if (curNode !== null) {
            this.postOrder(curNode.left);
            this.postOrder(curNode.right);
            console.log(curNode.data);
        }
    },
    customOrder: function (curNode) {
        if (curNode !== null) {
            let result = [];
            let queue = [];
            queue.push(curNode);
            let pointer = 0;
            while (pointer < queue.length) {
                let curNode = queue[pointer++]
                result.push(curNode.data);
                console.log("current:"+curNode.data)
                if (curNode.left) {
                    console.log("left:" + curNode.left.data)
                    queue.push(curNode.left)
                }
                if (curNode.right) {
                    console.log("right:" + curNode.right.data)
                    queue.push(curNode.right)
                }
            }
            console.log(result)
            return result;
        }
    }
}

function printTree(tree) {
    tree.customOrder(tree.rootNode)
}

var arr = [9, 8, 5, 0, 1, 6, 2]
console.log(arr)
var tree = new BinarySearchTree();

arr.map((item) => {
    tree.insert(item)
})
console.log(tree)
printTree(tree)
let result = [];
let stack = [tree.rootNode]; // 先将要遍历的树压入栈
let count = 0; // 用来记录执行到第一层
let bfs = function () {
    let node = stack[count];
    if (node) {
        result.push(node.data);
        if (node.left) stack.push(node.left);
        if (node.right) stack.push(node.right);
        count++;
        bfs();
    }
}
bfs();
console.log(result)