2020-03-19

class Node {
constructor(ele, parent) {
this.left = null;
this.right = null;
this.parent = parent;
this.element = ele;
}
isLeaf() {
return !(this.left && this.right);
}
hasTwoChild() {
return !!(this.left && this.right)
}
}

class BinaryTree {
constructor(visitor) {
this.size = 0;
this.root = null;
this.visitor = visitor;
}
// 获取节点个数（size）
size() {
return this.size;
}
// 判断是否为空树
isEmpty() {
return this.size === 0;
}
// 清空树
clear() {
this.root = null;
this.size = 0;
}
// 前序遍历
preOrder(node) {
if (!node) return;
if (this.visitor(node.element)) return;
this.preOrder(node.left);
this.preOrder(node.right);
}
// 前序遍历非递归
preOrderByMap() {
if (this.size === 0 || !this.visitor) return;
let queue = [];
queue.unshift(this.root)
while (queue.length !== 0) {
let node = queue.shift();
if (this.visitor(node.element)) return;
if (node.right) {
queue.unshift(node.right);
}

        if (node.left) {
            queue.unshift(node.left);
        }
    }
}
// 中序遍历
inOrder(node) {
    if (!node) return;
    this.inOrder(node.left);
    if (this.visitor(node.element)) return;
    this.inOrder(node.right);
}
// 中序遍历非递归
inOrderByMap() {
    if (this.size === 0 || !this.visitor) return;
    let queue = [],
        node = this.root;
    queue.unshift(this.root)
    while (queue.length !== 0) {
        if (node.left) {
            queue.unshift(node.left)
            node = node.left
        } else {
            if (this.visitor(node.element)) return;
            node = node.right
        }
    }
}
// 后序遍历
postOrder(node) {
    if (!node) return;
    this.postOrder(node.left);
    this.postOrder(node.right);
    if (this.visitor(node.element)) return;
}
// 后序遍历非递归
postOrderByMap() {
    if (this.size === 0 || !this.visitor) return;
    let queue = [];
    queue.unshift(this.root)
    while (queue.length !== 0) {
        let node = queue.shift();
        if (this.visitor(node.element)) return;

        if (node.left) {
            queue.unshift(node.left);
        }

        if (node.right) {
            queue.unshift(node.right);
        }
    }
}
// 层序遍历
levelOrder() {
    // 如果是空树或者没有传遍历回调器就返回
    if (this.size === 0 || !this.visitor) return;
    // 利用队列来实现层序遍历
    let queue = [];
    queue.push(this.root);

    while (queue.length !== 0) {
        // 从队列中取出node，如果有left则继续放入队列，再看是否有right，如果有就继续放入,直到队列为空为止
        let node = queue.shift();
        // 每一个node去执行传入的回调
        if (this.visitor(node.element)) return;
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
}
// 判断是否为完全二叉树
isComplete() {
    if (this.size === 0) return false;
    let queue = [],
        leaf = false;
    queue.push(this.root);

    while (queue.length !== 0) {
        let node = queue.shift();
        // 如果开启leaf说明之后的node都必须是叶子节点
        if (leaf && !node.isLeaf()) return false;

        // 如果node没有left有right，说明不是完全二叉树
        if (node.left) {
            queue.push(node.left);
        } else if (node.right) {
            return false;
        }

        // 如果node没有right但是有left，说明之后的node都必须是叶子节点才行，开启leaf开关
        if (node.right) {
            queue.push(node.right);
        } else {
            leaf = true;
        }
    }

    return true;
}