Vue 原理 - 继承 - karynsong|BMFE|eros

算法

二叉树

interface Node {
    key: number,
    left: any,
    right: any
}

class Tree {
    private root:any = null;
    private getNode(key:number):Node{
        return {
            key,
            left: null,
            right: null
        }
    }
    private inserNode(oldNode:Node, newNode:Node){
        if(oldNode.key > newNode.key){
            if(oldNode.left === null){
                oldNode.left = newNode;
            }else{
                this.inserNode(oldNode.left, newNode);
            }
        }else{
            if(oldNode.right === null){
                oldNode.right = newNode;
            }else{
                this.inserNode(oldNode.right, newNode);
            }
        }
    }
    public insert(key:number){
        var node = this.getNode(key);
        if(!this.root){
            this.root = node;
        }else{
            this.inserNode(this.root, node);
        }
    }
    public search(key:number, searchNode?:Node){
        var node = searchNode || this.root;
        while(node !== null && node.key !== key){
            if(node.key > key){
                node = node.left;
            }else{
                node = node.right;
            }
        }
        if(node === null){
            return false;
        }
        return node;
    }
    public min(_node?:Node){
        var node = _node || this.root;
        if(this.root === null){
            return false;
        }
        while(node.left !== null){
            node = node.left;
        }
        return node.key;
    }
    public max(_node?:Node){
        var node = _node || this.root;
        if(this.root === null){
            return false;
        }
        while(node.right !== null){
            node = node.right;
        }
        return node.key;
    }
    public remove(key:number, removeNode?:Node){
        var node = removeNode || this.root;
        if(node.key > key){
            node.left = this.remove(key, node.left);
        }else if(node.key < key){
            node.right = this.remove(key, node.right);
        }else{
            if( node.left === null && node.right === null){
                node = null;
            }else if(node.left && node.right === null){
                node = node.left;
            }else if(node.right && node.left === null){
                node = node.right;
            }else{
                var minKey = this.min(node.right);
                node.key = minKey;
                node.right = this.remove(minKey, node.right);
            }
        }
        return node
    }
    public inOrderTraverse(_node?:Node){
        if(_node === null){
            return
        }
        var node = _node || this.root;
        this.inOrderTraverse(node.left);
        console.log(node.key)
        this.inOrderTraverse(node.right);
    }
    public preOrderTraverse(_node?:Node){
        if(_node === null){
            return
        }
        var node = _node || this.root;
        console.log(node.key)
        this.preOrderTraverse(node.left);
        this.preOrderTraverse(node.right);
    }
    public postOrderTraverse(_node?:Node){
        if(_node === null){
            return
        }
        var node = _node || this.root;
        this.postOrderTraverse(node.left);
        this.postOrderTraverse(node.right);
        console.log(node.key)
    }
}

var tree = new Tree();
tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.insert(20);
tree.insert(18);
tree.insert(25);
tree.insert(6);
console.log(tree)
console.log(tree.search(6))
console.log(tree.min())
console.log(tree.max())
console.log(tree.inOrderTraverse())
console.log(tree.preOrderTraverse())
console.log(tree.postOrderTraverse())
console.log(tree.remove(15))

平衡二叉树

interface Node {
    key: number,
    left: any,
    right: any
}

class AVLTree{
    private root:any = null;
    private getNode(key:number):Node{
        return {
            key,
            left: null,
            right: null
        };
    }
    private getNodeHeight(node:Node){
        if(node === null){
            return 0;
        }
        var leftHeight = this.getNodeHeight(node.left);
        var rightHeight = this.getNodeHeight(node.right);
        return 1 + Math.max(leftHeight, rightHeight);
    }
    private isBalance(node:Node){
        var leftHeight = this.getNodeHeight(node.left);
        var rightHeight = this.getNodeHeight(node.right);
        if(leftHeight - rightHeight >= 2){
            return node;
        }else if(rightHeight - leftHeight >= 2){
            return node;
        }else{
            var leftIsBalance = node.left ? this.isBalance(node.left) : null;
            if(leftIsBalance){
                return leftIsBalance
            }
            var rightIsBalance = node.right ? this.isBalance(node.right) : null;
            if(rightIsBalance){
                return rightIsBalance
            }
            return null;
        }
    }
    private getDirection(node:Node):string{
        var left = this.getNodeHeight(node.left);
        var right = this.getNodeHeight(node.right);
        return left > right ? 'left' : 'right'
    }
    private findParentNode(parentNode:Node, targetNode:Node){
        if(parentNode.left && parentNode.left.key === targetNode.key || parentNode.right && parentNode.right.key === targetNode.key ){
            return parentNode;
        }
        if(parentNode.key > targetNode.key && parentNode.left){
            return this.findParentNode(parentNode.left, targetNode);
        }
        if(parentNode.key < targetNode.key && parentNode.right){
            return this.findParentNode(parentNode.right, targetNode);
        }
    }
    private rotate (balanceNode:Node){
        var direction = this.getDirection(balanceNode);
        var nextNode = balanceNode[direction];
        var nextNodeLeft = nextNode.left;
        var nextNodeRight = nextNode.right;
        if(direction === 'left'){
            if((!nextNodeLeft && nextNodeRight) || (nextNodeLeft && nextNodeRight && this.getNodeHeight(nextNodeLeft) < this.getNodeHeight(nextNodeRight))){
                nextNodeRight.left = nextNode;
                nextNode.right = null;
                nextNode = nextNodeRight;
            }
            if(!nextNode.right){
                balanceNode.left = null;
                nextNode.right = balanceNode;
            }else{
                balanceNode.left = nextNode.right;
                nextNode.right = balanceNode;
            }
        }else{
            if((nextNodeLeft && !nextNodeRight) && (nextNodeRight && nextNodeLeft && this.getNodeHeight(nextNodeLeft) > this.getNodeHeight(nextNodeRight))){
                nextNodeLeft.right = nextNode;
                nextNode.left = null;
                nextNode = nextNodeLeft;
            }
            if(!nextNode.left){
                balanceNode.right = null;
                nextNode.left = balanceNode;
            }else{
                balanceNode.right = nextNode.left;
                nextNode.left = balanceNode;
            }
        }
        if(this.root === balanceNode){
            this.root = nextNode;
        }else{
            this.findParentNode(this.root, balanceNode)[direction] = nextNode;
        }
        this.balanceTree();
    }
    private balanceTree(){
        var isBalance = this.isBalance(this.root);
        if(isBalance){
            this.rotate(isBalance);
        }
    }
    private insertNode(node:Node, parentNode:Node){
        if(node.key < parentNode.key){
            if(parentNode.left === null){
                parentNode.left = node;
                this.balanceTree();
            }else{
                this.insertNode(node, parentNode.left);
            }
        }else{
            if(parentNode.right === null){
                parentNode.right = node;
                this.balanceTree();
            }else{
                this.insertNode(node, parentNode.right);
            }
        }
    }
    public insert(key:number){
        var node = this.getNode(key);
        if(this.root === null){
            this.root = node;
        }else{
            this.insertNode(node, this.root);
        }
    }
    public search(key:number, _node?:Node){
        var node = _node === undefined ? this.root : _node;
        if(!node){
            return false;
        }
        if(node.key === key){
            return true;
        }
        if(node.key > key){
            return this.search(key, node.left);
        }
        if(node.key < key){
            return this.search(key, node.right);
        }
    }
    public min(_node?:Node){
        var node = _node === undefined ? this.root : _node;
        if(node.left){
            return this.min(node.left);
        }
        return node.key
    }
    public max(_node?:Node){
        var node = _node === undefined ? this.root : _node;
        if(node.right){
            return this.max(node.right);
        }
        return node.key
    }
    public inOrderTraverse(_node?:Node){
        var node = _node === undefined ? this.root : _node;
        node.left && this.inOrderTraverse(node.left);
        console.log(node.key);
        node.right && this.inOrderTraverse(node.right);
    }
    public preOrderTraverse(_node?:Node){
        var node = _node === undefined ? this.root : _node;
        console.log(node.key);
        node.left && this.preOrderTraverse(node.left);
        node.right && this.preOrderTraverse(node.right);
    }

    public postOrderTraverse(_node?:Node){
        var node = _node === undefined ? this.root : _node;
        node.left && this.postOrderTraverse(node.left);
        node.right && this.postOrderTraverse(node.right);
        console.log(node.key);
    }
    public remove(key:number, _node?:Node){
        var node = _node === undefined ? this.root : _node;
        if(node.key > key && node.left){
            node.left = this.remove(key, node.left);
        }else if(node.key < key && node.right){
            node.right = this.remove(key, node.right);
        }else if(node.key === key){
            if(node.left === null && node.right === null){
                node = null;
            }else if(node.left === null && node.right){
                node = node.right;
            }else if(node.right === null && node.left){
                node = node.left;
            }else{
                node.key = this.max(node.left);
                node.left = this.remove(node.key, node.left);
            }
        }
        if(_node === undefined){
            this.balanceTree();
        }
        return node;
    }
}

var tree = new AVLTree();
tree.insert(3);
tree.insert(5);
tree.insert(6);
tree.insert(7);
tree.insert(8);
tree.insert(9);
tree.insert(10);
tree.insert(11);
tree.insert(12);
tree.insert(13);
tree.insert(14);
tree.insert(15);
tree.insert(18);
tree.insert(20);
tree.insert(25);
console.log(tree)
console.log(tree.search(6))
console.log(tree.min())
console.log(tree.max())
console.log(tree.inOrderTraverse())
console.log(tree.preOrderTraverse())
console.log(tree.postOrderTraverse())
console.log(tree.remove(8))
console.log(tree)

继承

js 的集成基于原型链，弄清楚几个概念：object、Object、prototype、constructor、proto

常见的几种继承

借用构造器

function Super(arg){
    // constructor do something
}

Super.prototype = {}

function Sub(){
    Super.call(this, arguments);
}

var sub = new Sub();

原型继承

function Super(arg){
    // constructor do something
}

Super.prototype = {}

function Sub(){}

Sub.prototype = new Super();

var sub = new Sub();

组合继承

function Super(arg){
    // constructor do something
}

Super.prototype = {}

function Sub(){
    Super.call(this, arguments);
}

Sub.prototype = new Super();

var sub = new Sub();

寄生继承

function createAnother(original){
    var clone = Object.create(original);
    clone.xxx = function(){};
    return clone;
}

function Super(arg){
    // constructor do something
}

function Sub(){
    Super.call(this, arguments);
}

Sub.prototype = createAnother(Super);

var sub = new Sub();

寄生组合式继承

function inheritPrototype(sub, super){
    var clone = Object.create(Super.prototype);
    clone.constructor = sub;
    sub.prototype = clone;
}

function Super(){}
Super.prototype = {};

function Sub(){
    Subper.call(this, arguments);
}
inheritPrototype(Sub, Super);
Sub.prototype.xxx = {}

class 继承

class Super{}

class Sub extends Super{
    constructor(){
        super();
    }
    // Getter
    get aaa(){
        return 'xxx'
    }
    // Setter
    set bbb(){
        return 'xxx'
    }
    // 静态方法
    stati ccc(){
        
    }
}

var sub = new Sub();
sub.aaa             // xxx
sub.bbb = 'yyy'     // xxx
Sub.ccc()           // 静态方法调用