算法
平衡二叉树
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)
图
interface BfsPathNode {
key: string,
str: string
}
class Graph {
private vertices: string[] = [];
private adjList: object = {};
private isShowMap: object = {};
private isTraverseMap: object = {};
private bfsPath: object = {};
private dfsPath: object = {};
public addVertex(v: string) {
this.vertices.push(v);
this.adjList[v] = {};
}
public addEdge(v: string, w: string) {
// 无向图
if (!this.adjList[v][w]) {
this.adjList[v][w] = 0;
}
// 有向图注释下面
if (!this.adjList[w][v]) {
this.adjList[w][v] = 0;
}
this.adjList[v][w]++;
this.adjList[w][v]++;
}
public tostring() {
var s = '';
this.vertices.map(item => {
s += item + ' -> ';
for (var i in this.adjList[item]) {
s += i + ' ';
}
s += '\n';
});
return s;
}
private printSort(key: string) {
if (!this.isShowMap[key]) {
console.log(`Visited Vertex：${key}`)
this.isShowMap[key] = true;
}
}
private printPathTo(start: string, stop: string, path: object) {
var minPathNum, minPath,
str = `${start} 到 ${stop} 的所有路径：`;
for (var i in this.bfsPath) {
if (!minPathNum || minPathNum > this.bfsPath[i]) {
minPathNum = this.bfsPath[i];
minPath = i;
}
str += i + '、';
}
console.log(str.slice(0, -1))
console.log(`最短路径是：${minPath}；长度为：${minPathNum}`);
}
private bfsSort(arr: string[]) {
if (arr.length === 0) {
return;
}
var queue = [];
arr.map(item => {
this.isTraverseMap[item] = true;
this.printSort(item);
for (var i in this.adjList[item]) {
if (!this.isTraverseMap[i]) {
queue.push(i);
}
this.printSort(i);
}
});
this.bfsSort(queue);
}
public bfs(start: string) {
this.isShowMap = {};
this.isTraverseMap = {};
this.bfsSort([start]);
}
private bfsPathToSort(bfsPathNodeArr: BfsPathNode[], stop: string) {
if (bfsPathNodeArr.length === 0) {
return;
}
var queue = [];
bfsPathNodeArr.map(item => {
this.isTraverseMap[item.key] = true;
item.str += item.key;
if (stop === item.key) {
this.bfsPath[item.str] = item.str.length;
}
for (var i in this.adjList[item.key]) {
if (!this.isTraverseMap[i]) {
queue.push({
key: i,
str: item.str
});
}
}
});
this.bfsPathToSort(queue, stop);
}
public bfsPathTo(start: string, stop: string) {
this.isTraverseMap = {};
this.bfsPath = {};
this.bfsPathToSort([{
key: start,
str: ''
}], stop);
this.printPathTo(start, stop, this.bfsPath);
}
private dfsSort(arr: string[]) {
if (arr.length === 0) {
return;
}
var queue = [];
arr.map(item => {
this.printSort(item);
this.isTraverseMap[item] = true;
Object.keys(this.adjList[item]).map(_item => {
if (!this.isTraverseMap[_item]) {
queue.push(_item);
}
})
this.dfsSort(queue);
});
}
public dfs(start: string) {
this.isShowMap = {};
this.isTraverseMap = {};
this.dfsSort([start]);
}
private dfsPathToSort(bfsPathNodeArr: BfsPathNode[], stop: string) {
if (bfsPathNodeArr.length === 0) {
return;
}
var queue = [];
bfsPathNodeArr.map(item => {
this.isTraverseMap[item.key] = true;
item.str += item.key;
if (stop === item.key) {
this.bfsPath[item.str] = item.str.length;
}
Object.keys(this.adjList[item.key]).map(_item => {
if (!this.isTraverseMap[_item]) {
queue.push({
key: _item,
str: item.str
});
}
});
this.bfsPathToSort(queue, stop);
});
}
public dfsPathTo(start: string, stop: string) {
this.isTraverseMap = {};
this.dfsPath = {};
this.dfsPathToSort([{
key: start,
str: ''
}], stop);
this.printPathTo(start, stop, this.dfsPath)
}
}
var graph = new Graph();
var myVertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'];
myVertices.map(item => {
graph.addVertex(item);
});
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('C', 'D');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('E', 'I');
console.log(graph.tostring())
graph.bfs('A');
graph.bfsPathTo('A', 'G')
graph.dfs('A');
graph.dfsPathTo('A', 'G')
双向绑定的基础实现
对象常用的方法
- in：查找原型链和当前对象本身上有没有属性
- hasOwnPeoperty：判断当前属性是否在本身上，不会找原型链
- propertyIsEnumerable：判断是否可枚举
- Object.key：返回所有可枚举属性的数组
- Object.getOwnProperyNames：只会查询对象直接包含的属性，包括不可枚举的
对象的数据属性
- [[Configurable]]：能否把属性修改为访问器属性。默认值为true。
- [[Enumerable]]：能否通过for-in遍历到。默认值为true。
- [[Writable]]：能否修改属性值。默认值为true。
-
[[Value]]：值。默认值为undefined。
// 定义数据属性 Object.defineProperty(personB, “name”, { configurable : false, enumerable : false, writable : false, value : “Karyn” });
对象的访问器属性
- [[Configurable]]：能否把属性修改为访问器属性。默认值为true。
- [[Enumerable]]：能否通过for-in遍历到。默认值为true。
- [[Get]]：在读取该属性值时调用的函数。默认值为undefined。
-
[[Set]]：在写入属性时调用的函数。默认值为undefined。
// 通过 defineProperty 来申明属性 var person = { _name : “karyn”, // 通常我们用下划线开头来表示私有变量 _age: 12, edition : 1 } Object.defineProperty(person, “name”, { get: function(){ return this._name; }, set: function(newValue){ this._name = newValue; this.edition++; } });
// 申明完成之后 defineGetter 扩展 person.defineGetter(“age”, function(){ return this._age; }); person.defineSetter(“age”, function(newValue){ this._age = newValue; });
// 通过 get 和 set 方法设置 var person = { $name : “karyn”, edition : 1, get name(){ console.log(“get”,this.$name); }, set name(value){ this.$name = value; this.edition++; console.log(“set”,this.$name) } }