<浏览器打开页面的过程中发生了什么 Git命令简化笔记>

ES6二叉树的实现

#### 前言
　　二叉树是每个节点最多有两个子树的树结构，听上去，二叉树是一种特殊的树，但实现上，二叉树并不是树。
　　ES6是ECMAScript于2015年推出的新标准，又叫ES2015，虽说是近两年才正式确定的，但以前端的尿性，两年时间，鬼知道你都经历了什么！
　　那二叉树与ES6有什么关系不？并没有，只是用了几个ES6语法，纯属标题的需要～
  
#### 二叉树实例
　　二叉树的分类：完全二叉树，满二叉树，平衡二叉树。
　　本实例不是以上确切的任何一种但却可以变成以上任何一种，从结构上来说，本实例更有广泛性，从功能上来，却不如，因例是一种特殊的场景：首元素作为根节点，小的在左支，大的在右支。其排列与先后顺序有极大的关系。
　　在<a href="https://www.cnblogs.com/tugenhua0707/p/4361051.html" title="https://www.cnblogs.com/tugenhua0707/p/4361051.html" target="_blank" rel="nofollow">https://www.cnblogs.com/tugenhua0707/p/4361051.html</a>已经有JS实现的某种实例了，本例与其结构上是相同的。然而，[西法](http://www.boatsky.com "太空船博客")有另一个想法，不同之处主要不在于ES6重写，而是删除时，该文是使用替代节点的数字，插入到删除节点上，而本文使用的是“指针”的变化。
　　　　　50
　　　/  　　　\
　　24　　　　65
　　/　\　　　/  　\
　18　　37　60　80
　/　\　　\　　　/
4  　　20  　40　75
  
```javascript
//二叉树结点
class TreeNode {
	constructor(n, left, right){
		this.n = n;
		this.left = left;
		this.right = right;
	}
}
//二叉树
class BinaryTree {
	constructor(){
		this.length = 0;
		this.root = null;
        this.arr = [];
	}
	//添加对外入口，首个参数是数组，要求数组里都是数字，如果有不是数字则试图转成数字，如果有任何一个无法强制转成数字，则本操作无效
	addNode(){
		let arr = arguments[0];
		if(arr.length == 0) return false;
		return this.judgeData('_addNode', arr)
	}
	//删除结点
	deleteNode(){
        let arr = arguments[0];
		if(arr.length == 0) return false;
		return this.judgeData('_deleteNode', arr)
	}
    //传值判断，如果全部正确，则全部加入叉树
	judgeData(func, arr){
		let flag = false;
		//任何一个无法转成数字，都会失败
		if(arr.every(n => !Number.isNaN(n))){
			let _this = this;
			arr.map(n => _this[func](n));
			flag = true;
		}
		return flag;
	}
	//添加的真实实现
	_addNode(n){
		n = Number(n);
		let current = this.root;
		let treeNode = new TreeNode(n, null, null);
		if(this.root === null){
			this.root = treeNode;
		}
		else {
			current = this.root;
			while(current){
				let parent = current;
				if(n < current.n){
					current = current.left;
					if(current === null){
                        parent.left = treeNode;
					}
				}
				else {
					current = current.right;
					if(current === null){
                        parent.right = treeNode;
					}
				}
			}
			
		}
		this.length++;
		return treeNode;
	}
	//删除节点的真实实现
	_deleteNode(n){
		n = Number(n);
        if(this.root === null){
			return;
		}
		//查找该节点，删除节点操作比较复杂，为排除找不到被删除的节点的情况，简化代码，先保证该节点是存在的，虽然这样做其实重复了一次查询了，但二叉树的查找效率很高，这是可接受的
		let deleteNode = this.findNode(n);
		if(!deleteNode){
			return;
		}
        //如果删除的是根节点
		if(deleteNode === this.root){
			if(this.root.left === null && this.root.right === null){
                this.root = null;
            }
            else if(this.root.left === null){
                this.root = this.root.right;
            }
            else if(this.root.right === null){
                this.root = this.root.left;
            }
            else {
                let [replaceNode, replacePNode, rp] = this.findLeftTreeMax(deleteNode);
                replacePNode[rp] = null;
                replaceNode.left = this.root.left;
                replaceNode.right = this.root.right;
                this.root = replaceNode;
            }
		}
        else {
            //被删除的父节点，子节点在父节点的位置p，有left,right两种可能
            let [deleteParent, p] = this.findParentNode(deleteNode);
            if(deleteNode.left === null && deleteNode.right === null){
                deleteParent[p] = null;
            }
            else if(deleteNode.left === null){
                deleteParent[p] = deleteNode.right;
            }
            else if(deleteNode.right === null){
                deleteParent[p] = deleteNode.left;
            }
            else {
                //用来替换被删除的节点，父节点，节点在父节点的位置
                let [replaceNode, replacePNode, rp] = this.findLeftTreeMax(deleteNode);
                if(replacePNode === deleteNode){
                    deleteParent[p] = replaceNode;
                }
                else {
                    deleteParent[p] = replaceNode;
                    replacePNode.right = null;
                }
                replacePNode[rp] = null;
                replaceNode.left = deleteNode.left;
                replaceNode.right = deleteNode.right;
            }
        }
        this.length--;
	}
	//查找
	findNode(n){
		let result = null;
		let current = this.root;
		while(current){
			if(n === current.n){
				result = current;
				break;
			}
			else if(n < current.n){
				current = current.left;
			}
			else {
				current = current.right;
			}
		}
		return result;
	}
    //查找父节点
    findParentNode(node){
        let [parent, child, p] = [null, null, null];
        if(this.root !== node){
            parent = this.root;
            if(node.n < parent.n){
                child = parent.left;
                p = 'left';
            }
            else {
                child = parent.right;
                p = 'right';
            }
            while(child){
                if(node.n === child.n){
                    break;
                }
                else if(node.n < child.n){
                    parent = child;
                    child = parent.left;
                    p = 'left';
                }
                else {
                    parent = child;
                    child = parent.right;
                    p = 'right';
                }
            }
        }
        return [parent, p];
    }
	//查找当前有左子树的节点的最大值的节点M，如有A个节点被删除，M是最接近A点之一（还有一个是右子树节点的最小值）
	findLeftTreeMax(topNode){
        let [node, parent, p] = [null, null, null];
		if(this.root === null || topNode.left === null){
			return [node, parent, p];
		}
        parent = topNode;
        node = topNode.left;
        p = 'left';
        while(node.right){
            parent = node;
            node = node.right;
            p = 'right';
        }
        return [node, parent, p];
	}
    //查找最大值
    maxValue(){
        if(this.root !== null){
            return this._findLimit('right');
        }
    }
    //查找最小值
    minValue(){
        if(this.root !== null){
            return this._findLimit('left');
        }
    }
    //实现查找特殊值
    _findLimit(pro){
        let n = this.root.n;
        let current = this.root;
        while(current[pro]){
            current = current[pro];
            n = current.n;
        }
        return n;
    }
    //中序排序,并用数组的形式显示
    sortMiddleToArr(){
        this._sortMiddleToArr(this.root);
        return this.arr;
    }
    //中序方法
    _sortMiddleToArr(node){
        if(node !== null){
            this._sortMiddleToArr(node.left);
            this.arr.push(node.n);
            this._sortMiddleToArr(node.right);
        }
    }
    //打印二叉树对象
	printNode(){
        console.log(JSON.parse(JSON.stringify(this.root)));
    }
}

//测试
var binaryTree = new BinaryTree();
binaryTree.addNode([50, 24, 18, 65, 4, 80, 75, 20, 37, 40, 60]);
binaryTree.printNode();//{n: 50, left: {…}, right: {…}}
console.log(binaryTree.maxValue());//80
console.log(binaryTree.minValue());//4
console.log(binaryTree.sortMiddleToArr());// [4, 18, 20, 24, 37, 40, 50, 60, 65, 75, 80]
binaryTree.deleteNode([50]);
binaryTree.printNode();//{n: 40, left: {…}, right: {…}}

```
　　实现了二叉树的添加，删除，查找，排序等，具体也写了注释，就不多解释了。
难点在于删除，为了简化写法，代码也是累赘了，有时间读者可以自己实现一下增加印象。
　　不知道有没有发现没有，这里把一个数组加入至二叉数，拿到最大值、最小值，从小到大排序（甚至又返回了数组），不正是对应着Math.max.apply(Math, array)，Math.min.apply(Math, array),array.sort((a,b) => a - b)吗？那这二叉树有什么用？
　　在添加删除，该二叉树比数组复杂，但查找，排序之类的操作却远优于数组，比如在100万个元素里找到最大值，需比较约100万次，而该二叉树较理想状态，只需比较log2(100万)次（约20次），并且数据量越大，之间的差距就越惊人。
　　当然缺点也是有的，上述使用对象的形式保存节点，比较占内存，也有人直接用数组表示二叉树，是个好办法，但与本例场景又不太一样了。

如果觉得有帮忙，您可以在本页底部留言。

ES6二叉树的实现

全部留言

我要留言