class Node {
    constructor(data, left, right) {
        // 节点保存的数据
        this.data = data;
        // 节点的左子节点
        this.left = left;
        // 节点的右子节点
        this.right = right;
        // 该节点保存的数据出现的次数
        this.count = 1;

    }
    // show：显示当前节点的值
    show() {
        console.log(this.data+'出现了'+this.count+'次');
        return this.data;
    }
}
//  树
class BST {
    constructor() {
        this.root = null;
        // 边数
        this.sides = 0;
    }
    // insert：插入节点函数
    insert(data) {
        var node = new Node(data, null, null);
        if (this.root === null) {
            this.root = node;
            return;
        }
        var hasNode = this.find(data);
        if (hasNode) {
            // 更新计数
            this.update(hasNode);
            return;
        }
        var current = this.root;
        var parent;
        while (true) {
            parent = current;
            if (data < current.data) {
                current = current.left;
                if (current === null) {
                    parent.left = node;
                    break;
                }
            }
            else {
                current = current.right;
                if (current === null) {
                    parent.right = node;
                    break;
                }
            }
        }
    }
    // update：更新节点计算
    update(node){
        node.count++;
    }
    // inOrder：中序遍历
    inOrder(node) {
        if (node !== null) {
            this.inOrder(node.left);
            console.log(node.show());
            this.inOrder(node.right);
        }
    }
    // preOrder：先序遍历
    preOrder(node) {
        if (node !== null) {
            console.log(node.show());
            this.preOrder(node.left);
            this.preOrder(node.right);
        }
    }
    // postOrder: 后序遍历
    postOrder(node) {
        if (node !== null) {
            this.preOrder(node.left);
            this.preOrder(node.right);
            console.log(node.show());
        }
    }
    // max：查找最大值
    max() {
        var current = this.root;
        while (current.right !== null) {
            current = current.right;
        }
        return current.data;
    }
    // min：查找最小值
    min() {
        var current = this.root;
        while (current.left !== null) {
            current = current.left;
        }
        return current.data;
    }
    // find：查找给定值
    find(data) {
        var current = this.root;
        while (current !== null) {
            if (current.data === data) {
                return current;
            }
            else if (current.data < data) {
                current = current.right;
            }
            else { current = current.left }

        }
        return null
    }
    // remove：删除节点
    remove(data) {
        this.root =  this.removeNode(this.root,data);
    }
    //removeNode：实际操作删除的方法
    removeNode(node,data) {
        if (node === null) {
            return null;
        }
        if (data === node.data) {
            // 没有子节点
            if(node.left === null && node.right === null) {
                return null;
            }
            // 没有左节点
            if (node.left === null) {
                return node.right;
            } 
            // 没有右节点
            if(node.right === null) {
                return node.left;
            }
            // 有两个节点
            var tempNode = this.getMax(node.left);
            node.data = tempNode.data;
            node.left = this.removeNode(node.left,tempNode.data);
            return node;
        }
        else if (data < node.data) {
            node.left = this.removeNode(node.left,data);
            return node;
        }
        else {
            node.right = this.removeNode(node.right,data);
            return node;
        }
    }
    // getMax：获取左子树上的最大值
    getMax(node) {
        var current = node;
        while (current.right !== null) {
            current = current.right;
        }
        return current.data;
    }
    // 统计边
    getSides() {
        // 统计边的实际操作函数
        this.countSides(this.root);
        return this.sides;        
    }
    countSides(node) {
        if (node !== null) {
            if (node.left) {
                this.sides++;
            }
            if (node.right) {
                this.sides++;
            }
            this.countSides(node.left);
            this.countSides(node.right);
        }
    }
}


// 案例：新增一个方法，统计出树中有多少条边
// 解析：博客中我已经说了，如果节点的left或者right不为null，那么就算是有边的。
// 我们只需要遍历树，统计出有多少left和right就知道有多少条边了
var bst = new BST();
bst.insert(3);
bst.insert(4);
bst.insert(5);
bst.insert(6);
bst.insert(1);
console.log(bst.getSides());